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;
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 SCIPdebugMsg(
scip,
"(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 SCIPdebugMsg(
scip,
"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 SCIPdebugMsg(
scip,
" -> solution was feasible and good enough\n");
466 *result = SCIP_FOUNDSOL;
471 var = sdpcands[bestcand];
480 if ( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
482 SCIPdebugMsg(
scip,
"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 SCIPdebugMsg(
scip,
"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 SCIPdebugMsg(
scip,
" 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 SCIPdebugMsg(
scip,
" 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) );
528 SCIP_CALL( SCIPsolveProbingRelax(
scip, &cutoff) );
533 SCIPdebugMsg(
scip,
"SDP fracdiving heuristic aborted, as we could not solve one of the diving SDPs.\n");
535 SCIPfreeBufferArray(
scip, &sdpcandsfrac);
536 SCIPfreeBufferArray(
scip, &sdpcandssol);
537 SCIPfreeBufferArray(
scip, &sdpcands);
539 *result = SCIP_DIDNOTRUN;
540 SCIP_CALL( SCIPendProbing(
scip) );
549 if ( cutoff && ! backtracked && heurdata->backtrack )
551 #ifdef SCIP_MORE_DEBUG 552 SCIPdebugMsg(
scip,
" *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(
scip));
554 SCIP_CALL( SCIPbacktrackProbing(
scip, SCIPgetProbingDepth(
scip)-1) );
555 SCIP_CALL( SCIPnewProbingNode(
scip) );
568 objval = SCIPgetRelaxSolObj(
scip);
571 if ( SCIPisGT(
scip, objval, oldobjval) )
575 assert(bestcandroundup || backtracked);
576 SCIP_CALL( SCIPupdateVarPseudocost(
scip, sdpcands[bestcand], 1.0 - sdpcandsfrac[bestcand], objval - oldobjval, 1.0) );
580 assert(!bestcandroundup || backtracked);
581 SCIP_CALL( SCIPupdateVarPseudocost(
scip, sdpcands[bestcand], 0.0 - sdpcandsfrac[bestcand], objval - oldobjval, 1.0) );
587 for (v = 0; v < nvars; ++v)
591 val = SCIPgetRelaxSolVal(
scip, vars[v]);
592 frac = SCIPfeasFrac(
scip, val);
594 if ( SCIPvarIsIntegral(vars[v]) && ( ! SCIPisFeasZero(
scip, frac) ) )
596 sdpcands[nsdpcands] = vars[v];
597 sdpcandssol[nsdpcands] = val;
598 sdpcandsfrac[nsdpcands] = frac;
603 #ifdef SCIP_MORE_DEBUG 604 SCIPdebugMsg(
scip,
" -> objval=%g/%g, nfrac=%d\n", objval, searchbound, nsdpcands);
609 if ( nsdpcands == 0 && !cutoff )
614 SCIP_CALL( SCIPlinkRelaxSol(
scip, heurdata->sol) );
615 SCIPdebugMsg(
scip,
"SDP fracdiving found primal solution: obj=%g\n", SCIPgetSolOrigObj(
scip, heurdata->sol));
618 SCIP_CALL( SCIPtrySol(
scip, heurdata->sol, FALSE, FALSE, FALSE, FALSE, FALSE, &success) );
623 SCIPdebugMsg(
scip,
" -> solution was feasible and good enough\n");
624 *result = SCIP_FOUNDSOL;
629 SCIP_CALL( SCIPendProbing(
scip) );
631 if ( *result == SCIP_FOUNDSOL )
632 heurdata->nsuccess++;
634 SCIPdebugMsg(
scip,
"SDP fracdiving heuristic finished\n");
636 SCIPfreeBufferArray(
scip, &sdpcandsfrac);
637 SCIPfreeBufferArray(
scip, &sdpcandssol);
638 SCIPfreeBufferArray(
scip, &sdpcands);
643 *result = SCIP_DIDNOTRUN;
659 SCIP_HEURDATA* heurdata;
663 SCIP_CALL( SCIPallocMemory(
scip, &heurdata) );
666 SCIP_CALL( SCIPincludeHeurBasic(
scip, &heur,
670 assert( heur != NULL );
673 SCIP_CALL( SCIPsetHeurCopy(
scip, heur, heurCopySdpFracdiving) );
674 SCIP_CALL( SCIPsetHeurFree(
scip, heur, heurFreeSdpFracdiving) );
675 SCIP_CALL( SCIPsetHeurInit(
scip, heur, heurInitSdpFracdiving) );
676 SCIP_CALL( SCIPsetHeurExit(
scip, heur, heurExitSdpFracdiving) );
679 SCIP_CALL( SCIPaddRealParam(
scip,
680 "heuristics/sdpfracdiving/minreldepth",
681 "minimal relative depth to start diving",
683 SCIP_CALL( SCIPaddRealParam(
scip,
684 "heuristics/sdpfracdiving/maxreldepth",
685 "maximal relative depth to start diving",
687 SCIP_CALL( SCIPaddRealParam(
scip,
688 "heuristics/sdpfracdiving/maxdiveubquot",
689 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
691 SCIP_CALL( SCIPaddRealParam(
scip,
692 "heuristics/sdpfracdiving/maxdiveavgquot",
693 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
695 SCIP_CALL( SCIPaddRealParam(
scip,
696 "heuristics/sdpfracdiving/maxdiveubquotnosol",
697 "maximal UBQUOT when no solution was found yet (0.0: no limit)",
699 SCIP_CALL( SCIPaddRealParam(
scip,
700 "heuristics/sdpfracdiving/maxdiveavgquotnosol",
701 "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
703 SCIP_CALL( SCIPaddBoolParam(
scip,
704 "heuristics/sdpfracdiving/backtrack",
705 "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