52 #define HEUR_NAME "sdpfracdiving"
53 #define HEUR_DESC "SDP diving heuristic that chooses fixings w.r.t. the fractionalities"
54 #define HEUR_DISPCHAR 'f'
55 #define HEUR_PRIORITY -1003000
57 #define HEUR_FREQOFS 0
58 #define HEUR_MAXDEPTH -1
59 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
60 #define HEUR_USESSUBSCIP FALSE
67 #define DEFAULT_MINRELDEPTH 0.0
68 #define DEFAULT_MAXRELDEPTH 1.0
69 #define DEFAULT_MAXDIVEUBQUOT 0.8
71 #define DEFAULT_MAXDIVEAVGQUOT 0.0
73 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1
74 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0
75 #define DEFAULT_BACKTRACK TRUE
82 SCIP_Real minreldepth;
83 SCIP_Real maxreldepth;
84 SCIP_Real maxdiveubquot;
86 SCIP_Real maxdiveavgquot;
88 SCIP_Real maxdiveubquotnosol;
89 SCIP_Real maxdiveavgquotnosol;
102 assert(scip != NULL);
103 assert(heur != NULL);
104 assert(strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0);
116 SCIP_HEURDATA* heurdata;
118 assert(heur != NULL);
119 assert(strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0);
120 assert(scip != NULL);
123 heurdata = SCIPheurGetData(heur);
124 assert(heurdata != NULL);
125 SCIPfreeMemory(scip, &heurdata);
126 SCIPheurSetData(heur, NULL);
136 SCIP_HEURDATA* heurdata;
138 assert(heur != NULL);
139 assert(strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0);
142 heurdata = SCIPheurGetData(heur);
143 assert(heurdata != NULL);
146 SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
149 heurdata->nsuccess = 0;
159 SCIP_HEURDATA* heurdata;
161 assert(heur != NULL);
162 assert(strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0);
165 heurdata = SCIPheurGetData(heur);
166 assert(heurdata != NULL);
169 SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
180 #if ( (SCIP_VERSION > 321 || SCIP_SUBVERSION > 0) )
181 SCIP_HEURDATA* heurdata;
186 SCIP_Bool bestcandmayrounddown;
187 SCIP_Bool bestcandmayroundup;
188 SCIP_Bool bestcandroundup;
189 SCIP_Bool mayrounddown;
190 SCIP_Bool mayroundup;
192 SCIP_Bool backtracked;
194 SCIP_Real* sdpcandssol;
195 SCIP_Real* sdpcandsfrac;
196 SCIP_Real searchubbound;
197 SCIP_Real searchavgbound;
198 SCIP_Real searchbound;
203 SCIP_Real bestobjgain;
217 assert( heur != NULL );
218 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
219 assert( scip != NULL );
220 assert( result != NULL );
222 *result = SCIP_DELAYED;
225 if ( ! SCIPisRelaxSolValid(scip) )
229 if ( nodeinfeasible )
233 if ( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
236 *result = SCIP_DIDNOTRUN;
239 heurdata = SCIPheurGetData(heur);
240 assert( heurdata != NULL );
243 depth = SCIPgetDepth(scip);
244 maxdepth = SCIPgetMaxDepth(scip);
245 maxdepth = MAX(maxdepth, 30);
246 if ( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
250 vars = SCIPgetVars(scip);
251 nvars = SCIPgetNVars(scip);
252 SCIP_CALL( SCIPallocBufferArray(scip, &sdpcands, nvars) );
253 SCIP_CALL( SCIPallocBufferArray(scip, &sdpcandssol, nvars) );
254 SCIP_CALL( SCIPallocBufferArray(scip, &sdpcandsfrac, nvars) );
257 for (v = 0; v < nvars; ++v)
261 val = SCIPgetRelaxSolVal(scip, vars[v]);
262 frac = SCIPfeasFrac(scip, val);
264 if ( SCIPvarIsIntegral(vars[v]) && ( ! SCIPisFeasZero(scip, frac) ) )
266 sdpcands[nsdpcands] = vars[v];
267 sdpcandssol[nsdpcands] = val;
268 sdpcandsfrac[nsdpcands] = frac;
274 if ( nsdpcands == 0 )
276 SCIPfreeBufferArray(scip, &sdpcandsfrac);
277 SCIPfreeBufferArray(scip, &sdpcandssol);
278 SCIPfreeBufferArray(scip, &sdpcands);
283 if ( SCIPgetNSolsFound(scip) == 0 )
285 if ( heurdata->maxdiveubquotnosol > 0.0 )
286 searchubbound = SCIPgetLowerbound(scip) + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
288 searchubbound = SCIPinfinity(scip);
289 if ( heurdata->maxdiveavgquotnosol > 0.0 )
290 searchavgbound = SCIPgetLowerbound(scip) + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
292 searchavgbound = SCIPinfinity(scip);
296 if ( heurdata->maxdiveubquot > 0.0 )
297 searchubbound = SCIPgetLowerbound(scip) + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
299 searchubbound = SCIPinfinity(scip);
300 if ( heurdata->maxdiveavgquot > 0.0 )
301 searchavgbound = SCIPgetLowerbound(scip) + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
303 searchavgbound = SCIPinfinity(scip);
305 searchbound = MIN(searchubbound, searchavgbound);
306 if ( SCIPisObjIntegral(scip) )
307 searchbound = SCIPceil(scip, searchbound);
310 maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
311 maxdivedepth = MIN(maxdivedepth, maxdepth);
314 *result = SCIP_DIDNOTFIND;
317 SCIP_CALL( SCIPstartProbing(scip) );
320 SCIPenableVarHistory(scip);
323 objval = SCIPgetRelaxSolObj(scip);
325 SCIPdebugMessage(
"(node %"SCIP_LONGINT_FORMAT
") executing SDP fracdiving heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n",
326 SCIPgetNNodes(scip), SCIPgetDepth(scip), nsdpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
334 bestcandmayrounddown = FALSE;
335 bestcandmayroundup = FALSE;
336 startnsdpcands = nsdpcands;
339 while ( ! cutoff && nsdpcands > 0
341 || nsdpcands <= startnsdpcands - divedepth/2
342 || (divedepth < maxdivedepth && objval < searchbound))
343 && ! SCIPisStopped(scip) )
345 SCIP_CALL( SCIPnewProbingNode(scip) );
355 bestobjgain = SCIPinfinity(scip);
356 bestfrac = SCIP_INVALID;
357 bestcandmayrounddown = TRUE;
358 bestcandmayroundup = TRUE;
359 bestcandroundup = FALSE;
360 for (c = 0; c < nsdpcands; ++c)
363 mayrounddown = SCIPvarMayRoundDown(var);
364 mayroundup = SCIPvarMayRoundUp(var);
365 frac = sdpcandsfrac[c];
366 obj = SCIPvarGetObj(var);
367 if ( mayrounddown || mayroundup )
370 if( bestcandmayrounddown || bestcandmayroundup )
377 if ( mayrounddown && mayroundup )
378 roundup = (frac > 0.5);
380 roundup = mayrounddown;
395 if ( !SCIPvarIsBinary(var) )
399 if ( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
402 bestobjgain = objgain;
404 bestcandmayrounddown = mayrounddown;
405 bestcandmayroundup = mayroundup;
406 bestcandroundup = roundup;
426 if ( !SCIPvarIsBinary(var) )
430 if ( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac )
434 bestcandmayrounddown = FALSE;
435 bestcandmayroundup = FALSE;
436 bestcandroundup = roundup;
438 assert( bestfrac < SCIP_INVALID );
441 assert( bestcand != -1 );
444 if ( bestcandmayrounddown || bestcandmayroundup )
449 SCIP_CALL( SCIPlinkRelaxSol(scip, heurdata->sol) );
450 SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
454 SCIPdebugMessage(
"SDP fracdiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
457 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, &success) );
462 SCIPdebugMessage(
" -> solution was feasible and good enough\n");
463 *result = SCIP_FOUNDSOL;
468 var = sdpcands[bestcand];
477 if ( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
479 SCIPdebugMessage(
"Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
480 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), sdpcandssol[bestcand]);
484 if ( SCIPisFeasLT(scip, sdpcandssol[bestcand], SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, sdpcandssol[bestcand], SCIPvarGetUbLocal(var)) )
486 SCIPdebugMessage(
"selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
487 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), sdpcandssol[bestcand]);
489 assert( backtracked );
495 if ( bestcandroundup != backtracked )
498 #ifdef SCIP_MORE_DEBUG
499 SCIPdebugMessage(
" dive %d/%d: var <%s>, round=%u/%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
500 divedepth, maxdivedepth, SCIPvarGetName(var), bestcandmayrounddown, bestcandmayroundup,
501 sdpcandssol[bestcand], SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
502 SCIPfeasCeil(scip, sdpcandssol[bestcand]), SCIPvarGetUbLocal(var));
504 SCIP_CALL( SCIPchgVarLbProbing(scip, var, SCIPfeasCeil(scip, sdpcandssol[bestcand])) );
510 #ifdef SCIP_MORE_DEBUG
511 SCIPdebugMessage(
" dive %d/%d: var <%s>, round=%u/%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
512 divedepth, maxdivedepth, SCIPvarGetName(var), bestcandmayrounddown, bestcandmayroundup,
513 sdpcandssol[bestcand], SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
514 SCIPvarGetLbLocal(var), SCIPfeasFloor(scip, sdpcandssol[bestcand]));
516 SCIP_CALL( SCIPchgVarUbProbing(scip, var, SCIPfeasFloor(scip, sdpcandssol[bestcand])) );
521 SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
524 SCIP_RELAX* relaxsdp;
527 SCIP_CALL( SCIPsolveProbingRelax(scip, &cutoff) );
530 relaxsdp = SCIPfindRelax(scip,
"SDP");
535 SCIPdebugMessage(
"SDP fracdiving heuristic aborted, as we could not solve one of the diving SDPs.\n");
537 SCIPfreeBufferArray(scip, &sdpcandsfrac);
538 SCIPfreeBufferArray(scip, &sdpcandssol);
539 SCIPfreeBufferArray(scip, &sdpcands);
541 *result = SCIP_DIDNOTRUN;
542 SCIP_CALL( SCIPendProbing(scip) );
551 if ( cutoff && ! backtracked && heurdata->backtrack )
553 #ifdef SCIP_MORE_DEBUG
554 SCIPdebugMessage(
" *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
556 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
557 SCIP_CALL( SCIPnewProbingNode(scip) );
570 objval = SCIPgetRelaxSolObj(scip);
573 if ( SCIPisGT(scip, objval, oldobjval) )
577 assert(bestcandroundup || backtracked);
578 SCIP_CALL( SCIPupdateVarPseudocost(scip, sdpcands[bestcand], 1.0 - sdpcandsfrac[bestcand], objval - oldobjval, 1.0) );
582 assert(!bestcandroundup || backtracked);
583 SCIP_CALL( SCIPupdateVarPseudocost(scip, sdpcands[bestcand], 0.0 - sdpcandsfrac[bestcand], objval - oldobjval, 1.0) );
589 for (v = 0; v < nvars; ++v)
593 val = SCIPgetRelaxSolVal(scip, vars[v]);
594 frac = SCIPfeasFrac(scip, val);
596 if ( SCIPvarIsIntegral(vars[v]) && ( ! SCIPisFeasZero(scip, frac) ) )
598 sdpcands[nsdpcands] = vars[v];
599 sdpcandssol[nsdpcands] = val;
600 sdpcandsfrac[nsdpcands] = frac;
605 #ifdef SCIP_MORE_DEBUG
606 SCIPdebugMessage(
" -> objval=%g/%g, nfrac=%d\n", objval, searchbound, nsdpcands);
611 if ( nsdpcands == 0 && !cutoff )
616 SCIP_CALL( SCIPlinkRelaxSol(scip, heurdata->sol) );
617 SCIPdebugMessage(
"SDP fracdiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
620 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, &success) );
625 SCIPdebugMessage(
" -> solution was feasible and good enough\n");
626 *result = SCIP_FOUNDSOL;
631 SCIP_CALL( SCIPendProbing(scip) );
633 if ( *result == SCIP_FOUNDSOL )
634 heurdata->nsuccess++;
636 SCIPdebugMessage(
"SDP fracdiving heuristic finished\n");
638 SCIPfreeBufferArray(scip, &sdpcandsfrac);
639 SCIPfreeBufferArray(scip, &sdpcandssol);
640 SCIPfreeBufferArray(scip, &sdpcands);
645 *result = SCIP_DIDNOTRUN;
661 SCIP_HEURDATA* heurdata;
665 SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
668 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
672 assert( heur != NULL );
675 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopySdpFracdiving) );
676 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSdpFracdiving) );
677 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitSdpFracdiving) );
678 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitSdpFracdiving) );
681 SCIP_CALL( SCIPaddRealParam(scip,
682 "heuristics/sdpfracdiving/minreldepth",
683 "minimal relative depth to start diving",
685 SCIP_CALL( SCIPaddRealParam(scip,
686 "heuristics/sdpfracdiving/maxreldepth",
687 "maximal relative depth to start diving",
689 SCIP_CALL( SCIPaddRealParam(scip,
690 "heuristics/sdpfracdiving/maxdiveubquot",
691 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
693 SCIP_CALL( SCIPaddRealParam(scip,
694 "heuristics/sdpfracdiving/maxdiveavgquot",
695 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
697 SCIP_CALL( SCIPaddRealParam(scip,
698 "heuristics/sdpfracdiving/maxdiveubquotnosol",
699 "maximal UBQUOT when no solution was found yet (0.0: no limit)",
701 SCIP_CALL( SCIPaddRealParam(scip,
702 "heuristics/sdpfracdiving/maxdiveavgquotnosol",
703 "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
705 SCIP_CALL( SCIPaddBoolParam(scip,
706 "heuristics/sdpfracdiving/backtrack",
707 "use one level of backtracking if infeasibility is encountered?",
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define DEFAULT_MAXDIVEUBQUOT
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
static SCIP_DECL_HEUREXIT(heurExitSdpFracdiving)
static SCIP_DECL_HEURINIT(heurInitSdpFracdiving)
SCIP_Bool SCIPrelaxSdpSolvedProbing(SCIP_RELAX *relax)
SDP diving heuristic that chooses fixings w.r.t. the fractionalities.
#define DEFAULT_MINRELDEPTH
SCIP_RETCODE SCIPincludeHeurSdpFracdiving(SCIP *scip)
#define DEFAULT_BACKTRACK
#define DEFAULT_MAXRELDEPTH
SCIP_Bool SCIPrelaxSdpIsFeasible(SCIP_RELAX *relax)
static SCIP_DECL_HEUREXEC(heurExecSdpFracdiving)
static SCIP_DECL_HEURFREE(heurFreeSdpFracdiving)
static SCIP_DECL_HEURCOPY(heurCopySdpFracdiving)
#define DEFAULT_MAXDIVEAVGQUOT