59 #define PROP_NAME "sdpredcost" 60 #define PROP_DESC "sdp reduced cost strengthening propagator" 61 #define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP 62 #define PROP_PRIORITY +1000000 64 #define PROP_DELAY FALSE 65 #define DEFAULT_SDPRCBIN TRUE 66 #define DEFAULT_SDPRCINTCONT TRUE 78 SCIP_Bool forintconts;
91 SCIP_Real primallbval,
92 SCIP_Real primalubval,
93 SCIP_Real cutoffbound,
98 assert( scip != NULL );
99 assert( var != NULL );
100 assert( result != NULL );
103 if (SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5)
105 *result = SCIP_DIDNOTRUN;
110 if ( SCIPisGT(scip, primallbval, cutoffbound - relaxval) )
112 SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
113 SCIPdebugMsg(scip,
"Variable %s fixed to zero by reduced cost fixing ! \n", SCIPvarGetName(var));
114 *result = SCIP_REDUCEDDOM;
117 if ( SCIPisGT(scip, primalubval, cutoffbound - relaxval) )
119 *result = SCIP_CUTOFF;
126 if ( SCIPisGT(scip, primalubval, cutoffbound - relaxval) )
128 SCIP_CALL( SCIPchgVarLb(scip, var, 1.0) );
129 SCIPdebugMsg(scip,
"Variable %s fixed to one by reduced cost fixing ! \n", SCIPvarGetName(var));
130 *result = SCIP_REDUCEDDOM;
134 *result = SCIP_DIDNOTFIND;
153 SCIP_Real primallbval,
154 SCIP_Real primalubval,
155 SCIP_Real cutoffbound,
163 assert( scip != NULL );
164 assert( var != NULL );
165 assert( result != NULL );
167 *result = SCIP_DIDNOTFIND;
170 ub = SCIPisGT(scip, primallbval, 0.0) ? SCIPvarGetLbLocal(var) + (cutoffbound - relaxval) / primallbval : SCIPinfinity(scip);
171 lb = SCIPisGT(scip, primalubval, 0.0) ? SCIPvarGetUbLocal(var) - (cutoffbound - relaxval) / primalubval : -SCIPinfinity(scip);
174 if ( SCIPisInfinity(scip, ub) )
175 ub = SCIPinfinity(scip);
176 else if ( SCIPisInfinity(scip, -ub) )
177 ub = -SCIPinfinity(scip);
178 if ( SCIPisInfinity(scip, lb) )
179 lb = SCIPinfinity(scip);
180 else if ( SCIPisInfinity(scip, -lb) )
181 lb = -SCIPinfinity(scip);
184 if ( SCIPisFeasLT(scip, ub, lb) || SCIPisFeasLT(scip, ub, SCIPvarGetLbLocal(var)) || SCIPisFeasLT(scip, SCIPvarGetUbLocal(var), lb) )
186 SCIPdebugMsg(scip,
"Infeasibility of current node detected by prop_sdpredcost! Updated bounds for variable %s: lb = %f > %f = ub !\n",
187 SCIPvarGetName(var), SCIPisFeasGT(scip, lb, SCIPvarGetLbLocal(var))? lb : SCIPvarGetLbLocal(var),
188 SCIPisFeasLT(scip, ub, SCIPvarGetLbLocal(var)) ? ub : SCIPvarGetUbLocal(var) );
189 *result = SCIP_CUTOFF;
194 if ( SCIPisFeasLT(scip, ub, SCIPvarGetUbLocal(var)) )
196 SCIPdebugMsg(scip,
"Changing upper bound of variable %s from %f to %f because of prop_sdpredcost \n",
197 SCIPvarGetName(var), SCIPvarGetUbLocal(var), ub);
198 SCIP_CALL( SCIPchgVarUb(scip, var, ub) );
199 *result = SCIP_REDUCEDDOM;
203 if ( SCIPisFeasGT(scip, lb, SCIPvarGetLbLocal(var)) )
205 SCIPdebugMsg(scip,
"Changing lower bound of variable %s from %f to %f because of prop_sdpredcost \n",
206 SCIPvarGetName(var), SCIPvarGetLbLocal(var), lb);
207 SCIP_CALL( SCIPchgVarLb(scip, var, lb) );
208 *result = SCIP_REDUCEDDOM;
222 SCIP_RESULT varresult;
223 SCIP_Real cutoffbound;
226 SCIP_PROPDATA* propdata;
229 SCIPdebugMsg(
scip,
"Calling propExecSdpredcost \n");
231 assert(
scip != NULL );
232 assert( prop != NULL );
233 assert( result != NULL );
236 #if ( SCIP_VERSION >= 700 || (SCIP_VERSION >= 602 && SCIP_SUBVERSION > 0) ) 237 if( ! SCIPallowWeakDualReds(
scip) )
240 if( ! SCIPallowObjProp(
scip) )
244 if ( SCIPgetStage(
scip) == SCIP_STAGE_PRESOLVING )
247 *result = SCIP_DIDNOTRUN;
251 relax = SCIPfindRelax(
scip,
"SDP");
252 assert( relax != NULL );
257 SCIPdebugMsg(
scip,
"Stopped propExecRedcost because current SDP-relaxation doesn't belong to the node the propagator was called for!\n");
258 *result = SCIP_DIDNOTRUN;
265 SCIPdebugMsg(
scip,
"Stopped propExecRedcost because current SDP-relaxation was solved using a penalty formulation!\n");
266 *result = SCIP_DIDNOTRUN;
273 SCIPdebugMsg(
scip,
"Stopped propExecRedcost because SDP-relaxation wasn't properly solved!\n");
274 *result = SCIP_DIDNOTRUN;
278 propdata = SCIPpropGetData(prop);
279 assert( propdata != NULL );
281 *result = SCIP_DIDNOTFIND;
283 nvars = SCIPgetNVars(
scip);
284 vars = SCIPgetVars(
scip);
286 cutoffbound = SCIPgetCutoffbound(
scip);
292 assert( length == nvars );
294 for (v = 0; v < nvars; v++)
296 if ( SCIPvarIsBinary(vars[v]) && propdata->forbins )
298 SCIP_CALL(
sdpRedcostFixingBinary(
scip, vars[v], propdata->lbvarvals[v], propdata->ubvarvals[v], cutoffbound, relaxval, &varresult) );
300 if ( varresult == SCIP_REDUCEDDOM )
301 *result = SCIP_REDUCEDDOM;
303 else if ( (! SCIPvarIsBinary(vars[v])) && propdata->forintconts )
305 SCIP_CALL(
sdpRedcostFixingIntCont(
scip, vars[v], propdata->lbvarvals[v], propdata->ubvarvals[v], cutoffbound, relaxval, &varresult) );
307 if ( varresult == SCIP_REDUCEDDOM )
308 *result = SCIP_REDUCEDDOM;
319 SCIP_PROPDATA* propdata;
321 propdata = SCIPpropGetData(prop);
322 assert( propdata != NULL );
323 SCIPfreeMemory(
scip, &propdata);
325 SCIPpropSetData(prop, NULL);
334 SCIP_PROPDATA* propdata;
336 propdata = SCIPpropGetData(prop);
337 assert(propdata != NULL);
339 propdata->nvars = SCIPgetNVars(
scip);
340 SCIP_CALL( SCIPallocBlockMemoryArray(
scip, &(propdata->lbvarvals), propdata->nvars) );
341 SCIP_CALL( SCIPallocBlockMemoryArray(
scip, &(propdata->ubvarvals), propdata->nvars) );
350 SCIP_PROPDATA* propdata;
352 propdata = SCIPpropGetData(prop);
353 assert( propdata != NULL );
355 SCIPfreeBlockMemoryArrayNull(
scip, &(propdata->lbvarvals), propdata->nvars);
356 SCIPfreeBlockMemoryArrayNull(
scip, &(propdata->ubvarvals), propdata->nvars);
365 assert(
scip != NULL );
366 assert( prop != NULL );
367 assert( strcmp(SCIPpropGetName(prop),
PROP_NAME) == 0 );
380 SCIP_PROPDATA* propdata = NULL;
384 SCIP_CALL( SCIPallocMemory(scip, &propdata) );
386 propdata->lbvarvals = NULL;
387 propdata->ubvarvals = NULL;
391 propExecSdpredcost, propdata) );
392 assert( prop != NULL );
395 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopySdpredcost) );
396 SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolSdpredcost) );
397 SCIP_CALL( SCIPsetPropExitsol(scip, prop, propExitsolSdpredcost) );
398 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeSdpredcost) );
401 SCIP_CALL( SCIPaddBoolParam(scip,
"propagating/sdpredcost/forbins",
"Should SDP reduced cost fixing be executed for binary variables?",
403 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 / dual 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_DECL_PROPEXITSOL(propExitsolSdpredcost)
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