52 #define PROP_NAME "sdpredcost"
53 #define PROP_DESC "sdp reduced cost strengthening propagator"
54 #define PROP_TIMING (SCIP_PROPTIMING_DURINGLPLOOP | SCIP_PROPTIMING_AFTERLPLOOP)
55 #define PROP_PRIORITY +1000000
57 #define PROP_DELAY FALSE
58 #define DEFAULT_SDPRCBIN TRUE
59 #define DEFAULT_SDPRCINTCONT TRUE
71 SCIP_Bool forintconts;
84 SCIP_Real primallbval,
85 SCIP_Real primalubval,
86 SCIP_Real cutoffbound,
91 assert( scip != NULL );
92 assert( var != NULL );
93 assert( result != NULL );
96 if (SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5)
98 *result = SCIP_DIDNOTRUN;
103 if ( SCIPisGT(scip, primallbval, cutoffbound - relaxval) )
105 SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
106 SCIPdebugMessage(
"Variable %s fixed to zero by reduced cost fixing ! \n", SCIPvarGetName(var));
107 *result = SCIP_REDUCEDDOM;
110 if ( SCIPisGT(scip, primalubval, cutoffbound - relaxval) )
112 *result = SCIP_CUTOFF;
119 if ( SCIPisGT(scip, primalubval, cutoffbound - relaxval) )
121 SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
122 SCIPdebugMessage(
"Variable %s fixed to one by reduced cost fixing ! \n", SCIPvarGetName(var));
123 *result = SCIP_REDUCEDDOM;
127 *result = SCIP_DIDNOTFIND;
146 SCIP_Real primallbval,
147 SCIP_Real primalubval,
148 SCIP_Real cutoffbound,
156 assert( scip != NULL );
157 assert( var != NULL );
158 assert( result != NULL );
160 *result = SCIP_DIDNOTFIND;
163 ub = SCIPisGT(scip, primallbval, 0.0) ? SCIPvarGetLbLocal(var) + (cutoffbound - relaxval) / primallbval : SCIPinfinity(scip);
164 lb = SCIPisGT(scip, primalubval, 0.0) ? SCIPvarGetUbLocal(var) - (cutoffbound - relaxval) / primalubval : -SCIPinfinity(scip);
167 if ( SCIPisInfinity(scip, ub) )
168 ub = SCIPinfinity(scip);
169 else if ( SCIPisInfinity(scip, -ub) )
170 ub = -SCIPinfinity(scip);
171 if ( SCIPisInfinity(scip, lb) )
172 lb = SCIPinfinity(scip);
173 else if ( SCIPisInfinity(scip, -lb) )
174 lb = -SCIPinfinity(scip);
178 if ( SCIPisLT(scip, ub, lb) || SCIPisLT(scip, ub, SCIPvarGetLbLocal(var)) || SCIPisLT(scip, SCIPvarGetUbLocal(var), lb) )
180 SCIPdebugMessage(
"Infeasibility of current node detected by prop_sdpredcost! Updated bounds for variable %s: lb = %f > %f = ub !\n",
181 SCIPvarGetName(var), SCIPisGT(scip, lb, SCIPvarGetLbLocal(var))? lb : SCIPvarGetLbLocal(var),
182 SCIPisLT(scip, ub, SCIPvarGetLbLocal(var)) ? ub : SCIPvarGetUbLocal(var) );
183 *result = SCIP_CUTOFF;
188 if ( SCIPisLT(scip, ub, SCIPvarGetUbLocal(var)) )
190 SCIPdebugMessage(
"Changing upper bound of variable %s from %f to %f because of prop_sdpredcost \n",
191 SCIPvarGetName(var), SCIPvarGetUbLocal(var), ub);
192 SCIP_CALL( SCIPchgVarUb(scip, var, ub) );
193 *result = SCIP_REDUCEDDOM;
197 if ( SCIPisGT(scip, lb, SCIPvarGetLbLocal(var)) )
199 SCIPdebugMessage(
"Changing lower bound of variable %s from %f to %f because of prop_sdpredcost \n",
200 SCIPvarGetName(var), SCIPvarGetLbLocal(var), lb);
201 SCIP_CALL( SCIPchgVarLb(scip, var, lb) );
202 *result = SCIP_REDUCEDDOM;
216 SCIP_RESULT varresult;
217 SCIP_Real cutoffbound;
220 SCIP_PROPDATA* propdata;
223 SCIPdebugMessage(
"Calling propExecSdpredcost \n");
225 assert( scip != NULL );
226 assert( prop != NULL );
227 assert( result != NULL );
229 if ( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING )
232 *result = SCIP_DIDNOTRUN;
236 relax = SCIPfindRelax(scip,
"SDP");
237 assert( relax != NULL );
242 SCIPdebugMessage(
"Stopped propExecRedcost because current SDP-relaxation doesn't belong to the node the propagator was called for!\n");
243 *result = SCIP_DIDNOTRUN;
250 SCIPdebugMessage(
"Stopped propExecRedcost because current SDP-relaxation was solved using a penalty formulation!\n");
251 *result = SCIP_DIDNOTRUN;
258 SCIPdebugMessage(
"Stopped propExecRedcost because SDP-relaxation wasn't properly solved!\n");
259 *result = SCIP_DIDNOTRUN;
263 propdata = SCIPpropGetData(prop);
264 assert( propdata != NULL );
266 *result = SCIP_DIDNOTFIND;
268 nvars = SCIPgetNVars(scip);
269 vars = SCIPgetVars(scip);
271 cutoffbound = SCIPgetCutoffbound(scip);
277 assert( length == nvars );
279 for (v = 0; v < nvars; v++)
281 if ( SCIPvarIsBinary(vars[v]) && propdata->forbins )
283 SCIP_CALL(
sdpRedcostFixingBinary(scip, vars[v], propdata->lbvarvals[v], propdata->ubvarvals[v], cutoffbound, relaxval, &varresult) );
285 if ( varresult == SCIP_REDUCEDDOM )
286 *result = SCIP_REDUCEDDOM;
288 else if ( (! SCIPvarIsBinary(vars[v])) && propdata->forintconts )
290 SCIP_CALL(
sdpRedcostFixingIntCont(scip, vars[v], propdata->lbvarvals[v], propdata->ubvarvals[v], cutoffbound, relaxval, &varresult) );
292 if ( varresult == SCIP_REDUCEDDOM )
293 *result = SCIP_REDUCEDDOM;
304 SCIP_PROPDATA* propdata;
306 propdata = SCIPpropGetData(prop);
307 assert( propdata != NULL );
309 if ( propdata->nvars > 0 )
311 SCIPfreeBlockMemoryArrayNull(scip, &(propdata->lbvarvals), propdata->nvars);
312 SCIPfreeBlockMemoryArrayNull(scip, &(propdata->ubvarvals), propdata->nvars);
315 SCIPfreeMemory(scip, &propdata);
317 SCIPpropSetData(prop, NULL);
326 SCIP_PROPDATA* propdata;
329 propdata = SCIPpropGetData(prop);
330 assert(propdata != NULL);
331 nvars = SCIPgetNVars(scip);
333 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->lbvarvals), nvars) );
334 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(propdata->ubvarvals), nvars) );
335 propdata->nvars = nvars;
344 assert( scip != NULL );
345 assert( prop != NULL );
346 assert( strcmp(SCIPpropGetName(prop),
PROP_NAME) == 0 );
359 SCIP_PROPDATA* propdata = NULL;
363 SCIP_CALL( SCIPallocMemory(scip, &propdata) );
368 propExecSdpredcost, propdata) );
369 assert( prop != NULL );
372 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopySdpredcost) );
373 SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolSdpredcost) );
374 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeSdpredcost) );
377 SCIP_CALL( SCIPaddBoolParam(scip,
"propagating/sdpredcost/forbins",
"should sdp reduced cost fixing be executed for binary variables?",
379 SCIP_CALL( SCIPaddBoolParam(scip,
"propagating/sdpredcost/forintconts",
"should sdp reduced cost fixing be executed for integer and continuous variables?",
static SCIP_DECL_PROPFREE(propFreeSdpredcost)
static SCIP_DECL_PROPINITSOL(propInitsolSdpredcost)
SCIP_RETCODE SCIPrelaxSdpRelaxVal(SCIP_RELAX *relax, SCIP_Bool *success, SCIP_Real *objval)
General interface methods for SDP-preprocessing (mainly fixing variables and removing empty rows/cols...
static SCIP_DECL_PROPEXEC(propExecSdpredcost)
static SCIP_DECL_PROPCOPY(propCopySdpredcost)
long int SCIPrelaxSdpGetSdpNode(SCIP_RELAX *relax)
SCIP_Bool SCIPrelaxSdpSolvedOrig(SCIP_RELAX *relax)
SCIP_RETCODE SCIPrelaxSdpGetPrimalBoundVars(SCIP_RELAX *relax, SCIP_Real *lbvars, SCIP_Real *ubvars, int *arraylength)
reduced cost fixing for SDPs
static SCIP_RETCODE sdpRedcostFixingIntCont(SCIP *scip, SCIP_VAR *var, SCIP_Real primallbval, SCIP_Real primalubval, SCIP_Real cutoffbound, SCIP_Real relaxval, SCIP_RESULT *result)
static SCIP_RETCODE sdpRedcostFixingBinary(SCIP *scip, SCIP_VAR *var, SCIP_Real primallbval, SCIP_Real primalubval, SCIP_Real cutoffbound, SCIP_Real relaxval, SCIP_RESULT *result)
SCIP_RETCODE SCIPincludePropSdpredcost(SCIP *scip)
#define DEFAULT_SDPRCINTCONT