53 #define PROP_NAME "sdp-obbt"
54 #define PROP_DESC "optimization-based bound tightening for SDPs"
55 #define PROP_PRIORITY -1100000
57 #define PROP_DELAY FALSE
58 #define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP
60 #define DEFAULT_PROPBIN FALSE
61 #define DEFAULT_PROPCONT TRUE
73 long long int lastnode;
74 SCIP_Real sdpsolvergaptol;
83 #if ( (SCIP_VERSION > 321 || SCIP_SUBVERSION > 0) )
85 SCIP_RETCODE addObjCutoff(
91 char rowname[SCIP_MAXSTRLEN];
95 assert( scip != NULL );
96 assert( SCIPinProbing(scip) );
98 SCIPdebugMessage(
"create objective cutoff and add it to the LP-constraints\n");
100 nvars = SCIPgetNVars(scip);
101 vars = SCIPgetVars(scip);
104 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN,
"obbtsdp_objcutoff");
105 SCIP_CALL( SCIPcreateEmptyRowUnspec(scip, &row, rowname, -SCIPinfinity(scip), SCIPgetCutoffbound(scip), FALSE, FALSE, FALSE) );
106 SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
108 for( v = 0; v < nvars; v++ )
110 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[v], SCIPvarGetObj(vars[v])) );
112 SCIP_CALL( SCIPflushRowExtensions(scip, row) );
115 SCIP_CALL( SCIPaddRowProbing(scip, row) );
117 SCIP_CALL( SCIPreleaseRow(scip, &row) );
132 assert( scip != NULL );
133 assert( prop != NULL );
134 assert( strcmp(SCIPpropGetName(prop),
PROP_NAME) == 0 );
147 SCIP_PROPDATA* propdata;
149 propdata = SCIPpropGetData(prop);
150 assert(propdata != NULL);
152 SCIPfreeMemory(scip, &propdata);
153 SCIPpropSetData(prop, NULL);
162 SCIP_PROPDATA* propdata;
164 assert( prop != NULL );
166 propdata = SCIPpropGetData(prop);
168 propdata->lastnode = -1;
177 SCIP_PROPDATA* propdata;
179 assert( prop != NULL );
181 propdata = SCIPpropGetData(prop);
183 SCIP_CALL( SCIPgetRealParam(scip,
"relaxing/SDP/sdpsolvergaptol", &(propdata->sdpsolvergaptol)) );
193 #if ( (SCIP_VERSION > 321 || SCIP_SUBVERSION > 0) )
197 SCIP_PROPDATA* propdata;
200 SCIP_Bool oldobjlimitparam;
201 SCIP_Real probingval;
203 SCIP_RELAX* relaxsdp;
206 SCIP_Real* newbounds;
211 assert( scip != NULL );
212 assert( prop != NULL );
213 assert( result != NULL );
215 *result = SCIP_DIDNOTRUN;
217 SCIPdebugMessage(
"Executing propExecSdpObbt! \n");
220 if ( SCIPisInfinity(scip, SCIPgetCutoffbound(scip)) )
222 SCIPdebugMessage(
"Aborting propExecSdpObbt because of lack of cutoff-bound!\n");
227 if( !SCIPallowObjProp(scip) )
231 if( SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPinRepropagation(scip) || SCIPinProbing(scip) || !SCIPallowObjProp(scip) || !SCIPisRelaxSolValid(scip) )
233 SCIPdebugMessage(
"Aborting propExecSdpObbt because we are in presolving, repropagation, probing mode or no objective "
234 "propagation is allowed or no valid relaxation solution available!\n");
238 vars = SCIPgetVars(scip);
239 nvars = SCIPgetNVars(scip);
240 propdata = SCIPpropGetData(prop);
242 assert( propdata != NULL );
244 if ( SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) == propdata->lastnode )
246 SCIPdebugMessage(
"Not running again for node %lld!\n", propdata->lastnode);
251 propdata->lastnode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
255 SCIP_CALL( SCIPstartProbing(scip) );
256 SCIPdebugMessage(
"start probing\n");
258 SCIP_CALL( addObjCutoff(scip) );
261 SCIP_CALL( SCIPgetBoolParam(scip,
"relaxing/SDP/objlimit", &oldobjlimitparam) );
262 SCIP_CALL( SCIPsetBoolParam(scip,
"relaxing/SDP/objlimit", FALSE) );
265 SCIP_CALL( SCIPallocBufferArray(scip, &newbounds, 2*nvars) );
266 SCIP_CALL( SCIPallocBufferArray(scip, &newboundinds, 2*nvars) );
268 *result = SCIP_DIDNOTFIND;
271 for( v = 0; v < nvars; ++v )
273 SCIP_CALL( SCIPchgVarObjProbing(scip, vars[v], 0.0) );
278 for (v = 0; v < nvars; v++)
281 if ( (( ! propdata->propbin ) && SCIPvarIsBinary(vars[v])) || (( ! propdata->propcont ) && ( ! SCIPvarIsIntegral(vars[v]))) )
283 #ifdef SCIP_MORE_DEBUG
284 if ( SCIPvarIsBinary(vars[v]) )
286 SCIPdebugMessage(
"Skipping binary variable %s\n", SCIPvarGetName(vars[v]));
290 SCIPdebugMessage(
"Skipping continuous variable %s\n", SCIPvarGetName(vars[v]));
297 relaxval = SCIPgetRelaxSolVal(scip, vars[v]);
300 if ( SCIPisFeasGT(scip, relaxval, SCIPvarGetLbLocal(vars[v])) )
303 SCIP_CALL( SCIPchgVarObjProbing(scip, vars[v], 1.0) );
306 SCIP_CALL( SCIPsolveProbingRelax(scip, &cutoff) );
310 relaxsdp = SCIPfindRelax(scip,
"SDP");
314 SCIPdebugMessage(
"Aborting sdp-obbt, as we were unable to solve a probing sdp!\n");
315 if ( *result != SCIP_REDUCEDDOM )
316 *result = SCIP_DIDNOTRUN;
323 SCIPdebugMessage(
"Probing sdp infeasible, so there can't be a better solution for this problem!\n");
324 *result = SCIP_CUTOFF;
333 if ( SCIPisGT(scip, probingval - propdata->sdpsolvergaptol, SCIPvarGetLbLocal(vars[v])) )
336 SCIPdebugMessage(
"Obbt-Sdp tightened lower bound of variable %s from %f to %f !\n",
337 SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), probingval - propdata->sdpsolvergaptol);
339 newbounds[nnewbounds] = probingval;
340 newboundinds[nnewbounds] = -1 * (v+1);
342 *result = SCIP_REDUCEDDOM;
344 #ifdef SCIP_MORE_DEBUG
347 SCIPdebugMessage(
"Obbt-Sdp found lower bound of %f for variable %s, worse than old bound %f !\n",
348 probingval, SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]));
352 #ifdef SCIP_MORE_DEBUG
355 SCIPdebugMessage(
"Skipping obbt for lower bound %f of variable %s, as current relaxation's solution is tight.\n",
356 SCIPvarGetLbLocal(vars[v]), SCIPvarGetName(vars[v]));
361 if ( SCIPisFeasLT(scip, relaxval, SCIPvarGetUbLocal(vars[v])) )
364 SCIP_CALL( SCIPchgVarObjProbing(scip, vars[v], -1.0) );
367 SCIP_CALL( SCIPsolveProbingRelax(scip, &cutoff) );
371 relaxsdp = SCIPfindRelax(scip,
"SDP");
375 SCIPdebugMessage(
"Aborting sdp-obbt, as we were unable to solve a probing sdp!\n");
376 if ( *result != SCIP_REDUCEDDOM )
377 *result = SCIP_DIDNOTRUN;
384 SCIPdebugMessage(
"Probing sdp infeasible, so there can't be a better solution for this problem!\n");
385 *result = SCIP_CUTOFF;
394 if ( SCIPisLT(scip, -probingval + propdata->sdpsolvergaptol, SCIPvarGetUbLocal(vars[v])) )
396 SCIPdebugMessage(
"Obbt-Sdp tightened upper bound of variable %s from %f to %f !\n",
397 SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]), -probingval + propdata->sdpsolvergaptol);
399 newbounds[nnewbounds] = -probingval;
400 newboundinds[nnewbounds] = v + 1;
402 *result = SCIP_REDUCEDDOM;
404 #ifdef SCIP_MORE_DEBUG
407 SCIPdebugMessage(
"Obbt-Sdp found upper bound of %f for variable %s, worse than old bound %f !\n",
408 -probingval, SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]));
412 #ifdef SCIP_MORE_DEBUG
415 SCIPdebugMessage(
"Skipping obbt for upper bound %f of variable %s, as current relaxation's solution is tight.\n",
416 SCIPvarGetUbLocal(vars[v]), SCIPvarGetName(vars[v]));
421 SCIP_CALL( SCIPchgVarObjProbing(scip, vars[v], 0.0) );
424 SCIP_CALL( SCIPendProbing(scip) );
425 SCIPdebugMessage(
"end probing\n");
426 SCIP_CALL( SCIPsetBoolParam(scip,
"relaxing/SDP/objlimit", oldobjlimitparam) );
428 for (i = 0; i < nnewbounds; i++)
430 if ( newboundinds[i] < 0)
432 SCIP_CALL( SCIPchgVarLb(scip, vars[-1 * newboundinds[i] - 1], newbounds[i]) );
436 SCIP_CALL( SCIPchgVarUb(scip, vars[newboundinds[i] - 1], newbounds[i]) );
440 SCIPfreeBufferArray(scip, &newboundinds);
441 SCIPfreeBufferArray(scip, &newbounds);
446 *result = SCIP_DIDNOTRUN;
463 SCIP_PROPDATA* propdata;
468 SCIP_CALL( SCIPallocMemory(scip, &propdata) );
469 propdata->lastnode = -1;
476 propExecSdpObbt, propdata) );
478 assert(prop != NULL);
481 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopySdpObbt) );
482 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeSdpObbt) );
483 SCIP_CALL( SCIPsetPropExit(scip, prop, propExitSdpObbt) );
484 SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolSdpObbt) );
487 SCIP_CALL( SCIPaddBoolParam(scip,
"propagating/" PROP_NAME "/propbin",
488 "Should optimization-based bound tightening be performed for binary variables?",
491 SCIP_CALL( SCIPaddBoolParam(scip,
"propagating/" PROP_NAME "/propcont",
492 "Should optimization-based bound tightening be performed for continuous variables?",
SCIP_RETCODE SCIPincludePropSdpObbt(SCIP *scip)
static SCIP_DECL_PROPEXIT(propExitSdpObbt)
static SCIP_DECL_PROPEXEC(propExecSdpObbt)
static SCIP_DECL_PROPCOPY(propCopySdpObbt)
optimization-based bound tightening propagator for semidefinite programs
SCIP_RETCODE SCIPrelaxSdpRelaxVal(SCIP_RELAX *relax, SCIP_Bool *success, SCIP_Real *objval)
static SCIP_DECL_PROPINITSOL(propInitsolSdpObbt)
static SCIP_DECL_PROPFREE(propFreeSdpObbt)
SCIP_Bool SCIPrelaxSdpSolvedProbing(SCIP_RELAX *relax)
SCIP_Bool SCIPrelaxSdpIsFeasible(SCIP_RELAX *relax)