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;
182 SCIP_RELAX* relaxsdp;
187 SCIP_Bool bestcandmayrounddown;
188 SCIP_Bool bestcandmayroundup;
189 SCIP_Bool bestcandroundup;
190 SCIP_Bool mayrounddown;
191 SCIP_Bool mayroundup;
193 SCIP_Bool backtracked;
195 SCIP_Real* sdpcandssol;
196 SCIP_Real* sdpcandsfrac;
197 SCIP_Real searchubbound;
198 SCIP_Real searchavgbound;
199 SCIP_Real searchbound;
204 SCIP_Real bestobjgain;
218 assert( heur != NULL );
219 assert( strcmp(SCIPheurGetName(heur),
HEUR_NAME) == 0 );
220 assert( scip != NULL );
221 assert( result != NULL );
223 *result = SCIP_DELAYED;
225 relaxsdp = SCIPfindRelax(scip,
"SDP");
232 if ( nodeinfeasible )
236 if ( SCIPgetLastDivenode(scip) == SCIPgetNNodes(scip) && SCIPgetDepth(scip) > 0 )
239 *result = SCIP_DIDNOTRUN;
242 heurdata = SCIPheurGetData(heur);
243 assert( heurdata != NULL );
246 depth = SCIPgetDepth(scip);
247 maxdepth = SCIPgetMaxDepth(scip);
248 maxdepth = MAX(maxdepth, 30);
249 if ( depth < heurdata->minreldepth*maxdepth || depth > heurdata->maxreldepth*maxdepth )
253 vars = SCIPgetVars(scip);
254 nvars = SCIPgetNVars(scip);
255 SCIP_CALL( SCIPallocBufferArray(scip, &sdpcands, nvars) );
256 SCIP_CALL( SCIPallocBufferArray(scip, &sdpcandssol, nvars) );
257 SCIP_CALL( SCIPallocBufferArray(scip, &sdpcandsfrac, nvars) );
260 for (v = 0; v < nvars; ++v)
264 val = SCIPgetRelaxSolVal(scip, vars[v]);
265 frac = SCIPfeasFrac(scip, val);
267 if ( SCIPvarIsIntegral(vars[v]) && ( ! SCIPisFeasZero(scip, frac) ) )
269 sdpcands[nsdpcands] = vars[v];
270 sdpcandssol[nsdpcands] = val;
271 sdpcandsfrac[nsdpcands] = frac;
277 if ( nsdpcands == 0 )
279 SCIPfreeBufferArray(scip, &sdpcandsfrac);
280 SCIPfreeBufferArray(scip, &sdpcandssol);
281 SCIPfreeBufferArray(scip, &sdpcands);
286 if ( SCIPgetNSolsFound(scip) == 0 )
288 if ( heurdata->maxdiveubquotnosol > 0.0 )
289 searchubbound = SCIPgetLowerbound(scip) + heurdata->maxdiveubquotnosol * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
291 searchubbound = SCIPinfinity(scip);
292 if ( heurdata->maxdiveavgquotnosol > 0.0 )
293 searchavgbound = SCIPgetLowerbound(scip) + heurdata->maxdiveavgquotnosol * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
295 searchavgbound = SCIPinfinity(scip);
299 if ( heurdata->maxdiveubquot > 0.0 )
300 searchubbound = SCIPgetLowerbound(scip) + heurdata->maxdiveubquot * (SCIPgetCutoffbound(scip) - SCIPgetLowerbound(scip));
302 searchubbound = SCIPinfinity(scip);
303 if ( heurdata->maxdiveavgquot > 0.0 )
304 searchavgbound = SCIPgetLowerbound(scip) + heurdata->maxdiveavgquot * (SCIPgetAvgLowerbound(scip) - SCIPgetLowerbound(scip));
306 searchavgbound = SCIPinfinity(scip);
308 searchbound = MIN(searchubbound, searchavgbound);
309 if ( SCIPisObjIntegral(scip) )
310 searchbound = SCIPceil(scip, searchbound);
313 maxdivedepth = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
314 maxdivedepth = MIN(maxdivedepth, maxdepth);
317 *result = SCIP_DIDNOTFIND;
320 SCIP_CALL( SCIPstartProbing(scip) );
323 SCIPenableVarHistory(scip);
326 objval = SCIPgetRelaxSolObj(scip);
328 SCIPdebugMessage(
"(node %"SCIP_LONGINT_FORMAT
") executing SDP fracdiving heuristic: depth=%d, %d fractionals, dualbound=%g, searchbound=%g\n",
329 SCIPgetNNodes(scip), SCIPgetDepth(scip), nsdpcands, SCIPgetDualbound(scip), SCIPretransformObj(scip, searchbound));
337 bestcandmayrounddown = FALSE;
338 bestcandmayroundup = FALSE;
339 startnsdpcands = nsdpcands;
342 while ( ! cutoff && nsdpcands > 0
344 || nsdpcands <= startnsdpcands - divedepth/2
345 || (divedepth < maxdivedepth && objval < searchbound))
346 && ! SCIPisStopped(scip) )
348 SCIP_CALL( SCIPnewProbingNode(scip) );
358 bestobjgain = SCIPinfinity(scip);
359 bestfrac = SCIP_INVALID;
360 bestcandmayrounddown = TRUE;
361 bestcandmayroundup = TRUE;
362 bestcandroundup = FALSE;
363 for (c = 0; c < nsdpcands; ++c)
366 mayrounddown = SCIPvarMayRoundDown(var);
367 mayroundup = SCIPvarMayRoundUp(var);
368 frac = sdpcandsfrac[c];
369 obj = SCIPvarGetObj(var);
370 if ( mayrounddown || mayroundup )
373 if( bestcandmayrounddown || bestcandmayroundup )
380 if ( mayrounddown && mayroundup )
381 roundup = (frac > 0.5);
383 roundup = mayrounddown;
398 if ( !SCIPvarIsBinary(var) )
402 if ( SCIPisLT(scip, objgain, bestobjgain) || (SCIPisEQ(scip, objgain, bestobjgain) && frac < bestfrac) )
405 bestobjgain = objgain;
407 bestcandmayrounddown = mayrounddown;
408 bestcandmayroundup = mayroundup;
409 bestcandroundup = roundup;
429 if ( !SCIPvarIsBinary(var) )
433 if ( bestcandmayrounddown || bestcandmayroundup || frac < bestfrac )
437 bestcandmayrounddown = FALSE;
438 bestcandmayroundup = FALSE;
439 bestcandroundup = roundup;
441 assert( bestfrac < SCIP_INVALID );
444 assert( bestcand != -1 );
447 if ( bestcandmayrounddown || bestcandmayroundup )
452 SCIP_CALL( SCIPlinkRelaxSol(scip, heurdata->sol) );
453 SCIP_CALL( SCIProundSol(scip, heurdata->sol, &success) );
457 SCIPdebugMessage(
"SDP fracdiving found roundable primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
460 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
465 SCIPdebugMessage(
" -> solution was feasible and good enough\n");
466 *result = SCIP_FOUNDSOL;
471 var = sdpcands[bestcand];
480 if ( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
482 SCIPdebugMessage(
"Selected variable <%s> already fixed to [%g,%g] (solval: %.9f), diving aborted \n",
483 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), sdpcandssol[bestcand]);
487 if ( SCIPisFeasLT(scip, sdpcandssol[bestcand], SCIPvarGetLbLocal(var)) || SCIPisFeasGT(scip, sdpcandssol[bestcand], SCIPvarGetUbLocal(var)) )
489 SCIPdebugMessage(
"selected variable's <%s> solution value is outside the domain [%g,%g] (solval: %.9f), diving aborted\n",
490 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), sdpcandssol[bestcand]);
492 assert( backtracked );
498 if ( bestcandroundup != backtracked )
501 #ifdef SCIP_MORE_DEBUG
502 SCIPdebugMessage(
" dive %d/%d: var <%s>, round=%u/%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
503 divedepth, maxdivedepth, SCIPvarGetName(var), bestcandmayrounddown, bestcandmayroundup,
504 sdpcandssol[bestcand], SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
505 SCIPfeasCeil(scip, sdpcandssol[bestcand]), SCIPvarGetUbLocal(var));
507 SCIP_CALL( SCIPchgVarLbProbing(scip, var, SCIPfeasCeil(scip, sdpcandssol[bestcand])) );
513 #ifdef SCIP_MORE_DEBUG
514 SCIPdebugMessage(
" dive %d/%d: var <%s>, round=%u/%u, sol=%g, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
515 divedepth, maxdivedepth, SCIPvarGetName(var), bestcandmayrounddown, bestcandmayroundup,
516 sdpcandssol[bestcand], SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var),
517 SCIPvarGetLbLocal(var), SCIPfeasFloor(scip, sdpcandssol[bestcand]));
519 SCIP_CALL( SCIPchgVarUbProbing(scip, var, SCIPfeasFloor(scip, sdpcandssol[bestcand])) );
524 SCIP_CALL( SCIPpropagateProbing(scip, 0, &cutoff, NULL) );
529 SCIP_CALL( SCIPsolveProbingRelax(scip, &cutoff) );
534 SCIPdebugMessage(
"SDP fracdiving heuristic aborted, as we could not solve one of the diving SDPs.\n");
536 SCIPfreeBufferArray(scip, &sdpcandsfrac);
537 SCIPfreeBufferArray(scip, &sdpcandssol);
538 SCIPfreeBufferArray(scip, &sdpcands);
540 *result = SCIP_DIDNOTRUN;
541 SCIP_CALL( SCIPendProbing(scip) );
550 if ( cutoff && ! backtracked && heurdata->backtrack )
552 #ifdef SCIP_MORE_DEBUG
553 SCIPdebugMessage(
" *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
555 SCIP_CALL( SCIPbacktrackProbing(scip, SCIPgetProbingDepth(scip)-1) );
556 SCIP_CALL( SCIPnewProbingNode(scip) );
569 objval = SCIPgetRelaxSolObj(scip);
572 if ( SCIPisGT(scip, objval, oldobjval) )
576 assert(bestcandroundup || backtracked);
577 SCIP_CALL( SCIPupdateVarPseudocost(scip, sdpcands[bestcand], 1.0 - sdpcandsfrac[bestcand], objval - oldobjval, 1.0) );
581 assert(!bestcandroundup || backtracked);
582 SCIP_CALL( SCIPupdateVarPseudocost(scip, sdpcands[bestcand], 0.0 - sdpcandsfrac[bestcand], objval - oldobjval, 1.0) );
588 for (v = 0; v < nvars; ++v)
592 val = SCIPgetRelaxSolVal(scip, vars[v]);
593 frac = SCIPfeasFrac(scip, val);
595 if ( SCIPvarIsIntegral(vars[v]) && ( ! SCIPisFeasZero(scip, frac) ) )
597 sdpcands[nsdpcands] = vars[v];
598 sdpcandssol[nsdpcands] = val;
599 sdpcandsfrac[nsdpcands] = frac;
604 #ifdef SCIP_MORE_DEBUG
605 SCIPdebugMessage(
" -> objval=%g/%g, nfrac=%d\n", objval, searchbound, nsdpcands);
610 if ( nsdpcands == 0 && !cutoff )
615 SCIP_CALL( SCIPlinkRelaxSol(scip, heurdata->sol) );
616 SCIPdebugMessage(
"SDP fracdiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(scip, heurdata->sol));
619 SCIP_CALL( SCIPtrySol(scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
624 SCIPdebugMessage(
" -> solution was feasible and good enough\n");
625 *result = SCIP_FOUNDSOL;
630 SCIP_CALL( SCIPendProbing(scip) );
632 if ( *result == SCIP_FOUNDSOL )
633 heurdata->nsuccess++;
635 SCIPdebugMessage(
"SDP fracdiving heuristic finished\n");
637 SCIPfreeBufferArray(scip, &sdpcandsfrac);
638 SCIPfreeBufferArray(scip, &sdpcandssol);
639 SCIPfreeBufferArray(scip, &sdpcands);
644 *result = SCIP_DIDNOTRUN;
660 SCIP_HEURDATA* heurdata;
664 SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
667 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
671 assert( heur != NULL );
674 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopySdpFracdiving) );
675 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeSdpFracdiving) );
676 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitSdpFracdiving) );
677 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitSdpFracdiving) );
680 SCIP_CALL( SCIPaddRealParam(scip,
681 "heuristics/sdpfracdiving/minreldepth",
682 "minimal relative depth to start diving",
684 SCIP_CALL( SCIPaddRealParam(scip,
685 "heuristics/sdpfracdiving/maxreldepth",
686 "maximal relative depth to start diving",
688 SCIP_CALL( SCIPaddRealParam(scip,
689 "heuristics/sdpfracdiving/maxdiveubquot",
690 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
692 SCIP_CALL( SCIPaddRealParam(scip,
693 "heuristics/sdpfracdiving/maxdiveavgquot",
694 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
696 SCIP_CALL( SCIPaddRealParam(scip,
697 "heuristics/sdpfracdiving/maxdiveubquotnosol",
698 "maximal UBQUOT when no solution was found yet (0.0: no limit)",
700 SCIP_CALL( SCIPaddRealParam(scip,
701 "heuristics/sdpfracdiving/maxdiveavgquotnosol",
702 "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
704 SCIP_CALL( SCIPaddBoolParam(scip,
705 "heuristics/sdpfracdiving/backtrack",
706 "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