42 #include "scip/scipdefplugins.h"
45 #define HEUR_NAME "restmaster"
46 #define HEUR_DESC "LNS heuristic for the master problem that fixes some master variables to zero"
47 #define HEUR_DISPCHAR 'P'
48 #define HEUR_PRIORITY 100
50 #define HEUR_FREQOFS 0
51 #define HEUR_MAXDEPTH -1
52 #define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP | SCIP_HEURTIMING_DURINGPRICINGLOOP
53 #define HEUR_USESSUBSCIP TRUE
55 #define DEFAULT_MAXNODES 5000LL
56 #define DEFAULT_MINFIXINGRATE 0.5
57 #define DEFAULT_MINIMPROVE 0.01
58 #define DEFAULT_MINNODES 500LL
59 #define DEFAULT_NODESOFS 500LL
60 #define DEFAULT_NODESQUOT 0.1
61 #define DEFAULT_USELPROWS FALSE
63 #define DEFAULT_COPYCUTS TRUE
66 #define DEFAULT_PBHEUR FALSE
107 SCIP_VAR** restmastervars,
108 SCIP_Real minfixingrate,
114 SCIP_VAR** mastervars;
116 SCIP_Real fixingrate;
122 SCIP_CALL( SCIPgetVarsData(scip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
123 assert(mastervars != NULL);
124 assert(nmastervars >= 0);
129 for( i = 0; i < nmastervars && !pbheur; i++ )
131 SCIP_Real mastersolval;
133 mastersolval = SCIPgetSolVal(scip, NULL, mastervars[i]);
136 if( SCIPisFeasZero(scip, mastersolval) )
138 SCIP_CALL( SCIPchgVarLbGlobal(restmaster, restmastervars[i], 0.0) );
139 SCIP_CALL( SCIPchgVarUbGlobal(restmaster, restmastervars[i], 0.0) );
145 if( fixingcounter == nmastervars )
147 SCIPdebugMessage(
" -> all master variables fixed, not solving problem.\n");
152 fixingrate = fixingcounter / (SCIP_Real)(MAX(nmastervars, 1));
154 SCIPdebugMessage(
" -> %d out of %d (%.2f percent) master variables fixed.\n", fixingcounter, nmastervars, fixingrate * 100.0);
157 if( fixingrate < minfixingrate && !pbheur)
159 SCIPdebugMessage(
" -> not enough variables fixed.\n");
170 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
173 for( i = 0; i < nrows; i++ )
186 if( SCIProwIsLocal(rows[i]) )
190 constant = SCIProwGetConstant(rows[i]);
191 lhs = SCIProwGetLhs(rows[i]) - constant;
192 rhs = SCIProwGetRhs(rows[i]) - constant;
193 vals = SCIProwGetVals(rows[i]);
194 nnonz = SCIProwGetNNonz(rows[i]);
195 cols = SCIProwGetCols(rows[i]);
200 SCIP_CALL( SCIPallocBufferArray(restmaster, &consvars, nnonz) );
201 for( j = 0; j < nnonz; j++ )
202 consvars[j] = restmastervars[SCIPvarGetProbindex(SCIPcolGetVar(cols[j]))];
205 SCIP_CALL( SCIPcreateConsLinear(restmaster, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
206 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
207 SCIP_CALL( SCIPaddCons(restmaster, cons) );
208 SCIP_CALL( SCIPreleaseCons(restmaster, &cons) );
211 SCIPfreeBufferArray(restmaster, &consvars);
225 SCIP_VAR** restmastervars,
227 SCIP_SOL* restmastersol,
232 SCIP_VAR** mastervars;
235 SCIP_Real* restmastervals;
236 SCIP_SOL* newmastersol;
238 assert(origprob != NULL);
239 assert(scip != NULL);
240 assert(restmaster != NULL);
241 assert(restmastervars != NULL);
242 assert(restmastersol != NULL);
245 SCIP_CALL( SCIPgetVarsData(origprob, &vars, &nvars, NULL, NULL, NULL, NULL) );
246 SCIP_CALL( SCIPgetVarsData(scip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
247 assert(nmastervars == SCIPgetNOrigVars(restmaster));
249 SCIP_CALL( SCIPallocBufferArray(scip, &restmastervals, nmastervars) );
252 SCIP_CALL( SCIPgetSolVals(restmaster, restmastersol, nmastervars, restmastervars, restmastervals) );
255 SCIP_CALL( SCIPcreateSol(scip, &newmastersol, heur) );
256 SCIP_CALL( SCIPsetSolVals(scip, newmastersol, nmastervars, mastervars, restmastervals) );
259 SCIP_CALL( SCIPtrySolFree(scip, &newmastersol, TRUE, TRUE, TRUE, TRUE, TRUE, success) );
261 SCIP_CALL( SCIPtrySolFree(scip, &newmastersol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
264 SCIPfreeBufferArray(scip, &restmastervals);
275 #define heurCopyRestmaster NULL
281 SCIP_HEURDATA* heurdata;
283 assert(heur != NULL);
284 assert(scip != NULL);
287 heurdata = SCIPheurGetData(heur);
288 assert(heurdata != NULL);
291 SCIPfreeMemory(scip, &heurdata);
292 SCIPheurSetData(heur, NULL);
302 SCIP_HEURDATA* heurdata;
304 assert(heur != NULL);
305 assert(scip != NULL);
308 heurdata = SCIPheurGetData(heur);
309 assert(heurdata != NULL);
312 heurdata->usednodes = 0;
315 if( heurdata->pbheur )
317 heurdata->maxnodes = INT_MAX;
319 SCIPheurSetTimingmask(heur, SCIP_HEURTIMING_AFTERNODE);
320 SCIPheurSetFreq(heur, 0);
328 #define heurExitRestmaster NULL
332 #define heurInitsolRestmaster NULL
336 #define heurExitsolRestmaster NULL
344 SCIP_HEURDATA* heurdata;
346 SCIP_Real memorylimit;
347 SCIP_Bool discretization;
349 SCIP_Longint nstallnodes;
352 SCIP_HASHMAP* varmapfw;
353 SCIP_VAR** mastervars;
354 SCIP_VAR** restmastervars;
360 SCIP_RETCODE retstat;
363 assert(heur != NULL);
364 assert(scip != NULL);
365 assert(result != NULL);
366 assert(SCIPhasCurrentNodeLP(scip));
370 assert(origprob != NULL);
373 heurdata = SCIPheurGetData(heur);
374 assert(heurdata != NULL);
376 *result = SCIP_DIDNOTRUN;
379 SCIP_CALL( SCIPgetBoolParam(origprob,
"relaxing/gcg/discretization", &discretization) );
380 if( !discretization )
383 *result = SCIP_DELAYED;
386 if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
389 *result = SCIP_DIDNOTRUN;
392 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(origprob));
394 if( !heurdata->pbheur )
397 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
398 nstallnodes -= 100 * SCIPheurGetNCalls(heur);
399 nstallnodes += heurdata->nodesofs;
402 nstallnodes -= heurdata->usednodes;
403 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
407 if( nstallnodes < heurdata->minnodes )
415 SCIP_CALL( SCIPgetRealParam(origprob,
"limits/time", &timelimit) );
416 if( !SCIPisInfinity(origprob, timelimit) )
417 timelimit -= SCIPgetSolvingTime(origprob);
418 SCIP_CALL( SCIPgetRealParam(origprob,
"limits/memory", &memorylimit) );
419 if( !SCIPisInfinity(origprob, memorylimit) )
420 memorylimit -= SCIPgetMemUsed(origprob)/1048576.0;
421 if( timelimit < 10.0 || memorylimit <= 0.0 )
424 if( SCIPisStopped(scip) )
427 SCIPdebugMessage(
"Executing Restricted Master Heuristic ...\n");
429 *result = SCIP_DIDNOTFIND;
432 SCIP_CALL( SCIPgetVarsData(scip, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
433 assert(mastervars != NULL);
434 assert(nmastervars >= 0);
437 SCIP_CALL( SCIPcreate(&restmaster) );
440 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(restmaster), nmastervars) );
441 SCIP_CALL( SCIPallocBufferArray(scip, &restmastervars, nmastervars) );
443 if( heurdata->uselprows )
445 char probname[SCIP_MAXSTRLEN];
448 SCIP_CALL( SCIPincludeDefaultPlugins(restmaster) );
451 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN,
"%s_restricted", SCIPgetProbName(scip));
454 SCIP_CALL( SCIPcreateProb(restmaster, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
457 SCIP_CALL( SCIPcopyVars(scip, restmaster, varmapfw, NULL, NULL, NULL, 0, TRUE) );
465 SCIP_CALL( SCIPcopy(scip, restmaster, varmapfw, NULL,
"restmaster", TRUE, FALSE, FALSE, TRUE, &valid) );
467 if( heurdata->copycuts )
470 SCIP_CALL( SCIPcopyCuts(scip, restmaster, varmapfw, NULL, TRUE, NULL) );
473 SCIPdebugMessage(
"Copying the SCIP instance was %s complete.\n", valid ?
"" :
"not ");
476 for( i = 0; i < nmastervars; i++ )
477 restmastervars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, mastervars[i]);
480 SCIPhashmapFree(&varmapfw);
485 SCIP_CALL(
setupSubproblem(scip, restmaster, restmastervars, heurdata->minfixingrate, heurdata->uselprows, heurdata->pbheur, &success) );
486 SCIPdebugMessage(
"restricted master problem: %d vars, %d cons, success=%u\n", SCIPgetNVars(restmaster), SCIPgetNConss(restmaster), success);
489 SCIP_CALL( SCIPsetBoolParam(restmaster,
"misc/catchctrlc", FALSE) );
492 SCIP_CALL( SCIPsetIntParam(restmaster,
"display/verblevel", 0) );
495 if( heurdata->pbheur )
496 nstallnodes = heurdata->maxnodes;
499 SCIP_CALL( SCIPsetLongintParam(restmaster,
"limits/stallnodes", nstallnodes) );
500 SCIP_CALL( SCIPsetLongintParam(restmaster,
"limits/nodes", heurdata->maxnodes) );
501 SCIP_CALL( SCIPsetRealParam(restmaster,
"limits/time", timelimit) );
502 SCIP_CALL( SCIPsetRealParam(restmaster,
"limits/memory", memorylimit) );
505 if( !heurdata->pbheur )
508 SCIP_CALL( SCIPsetSubscipsOff(restmaster, TRUE) );
510 SCIP_CALL( SCIPsetSeparating(restmaster, SCIP_PARAMSETTING_OFF, TRUE) );
513 SCIP_CALL( SCIPsetPresolving(restmaster, SCIP_PARAMSETTING_FAST, TRUE) );
516 if( SCIPfindNodesel(scip,
"estimate") != NULL )
518 SCIP_CALL( SCIPsetIntParam(restmaster,
"nodeselection/estimate/stdpriority", INT_MAX/4) );
522 if( SCIPfindBranchrule(scip,
"inference") != NULL )
524 SCIP_CALL( SCIPsetIntParam(restmaster,
"branching/inference/priority", INT_MAX/4) );
528 if( !SCIPisParamFixed(restmaster,
"conflict/enable") )
530 SCIP_CALL( SCIPsetBoolParam(restmaster,
"conflict/enable", FALSE) );
537 SCIPdebugMessage(
"restricted master problem not created.\n");
538 *result = SCIP_DIDNOTRUN;
539 SCIPfreeBufferArray(scip, &restmastervars);
540 SCIP_CALL( SCIPfree(&restmaster) );
546 if( SCIPgetNSols(origprob) > 0 )
549 SCIP_Real upperbound;
550 assert(!SCIPisInfinity(origprob,SCIPgetUpperbound(origprob)));
552 upperbound = SCIPgetUpperbound(origprob) - SCIPsumepsilon(origprob);
554 if( !SCIPisInfinity(origprob,-1.0*SCIPgetLowerbound(origprob)) )
556 cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(origprob) + heurdata->minimprove*SCIPgetLowerbound(origprob);
560 if( SCIPgetUpperbound ( origprob ) >= 0 )
561 cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( origprob );
563 cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( origprob );
565 cutoff = MIN(upperbound, cutoff);
566 SCIP_CALL( SCIPsetObjlimit(restmaster, cutoff) );
574 retstat = SCIPpresolve(restmaster);
575 if( retstat != SCIP_OKAY )
577 SCIPwarningMessage(scip,
"Error while presolving subMIP in Restricted Master Heuristic; Restricted Master terminated with code <%d>\n",retstat);
580 SCIP_CALL( SCIPpresolve(restmaster) );
583 SCIPdebugMessage(
"presolved restricted master problem: %d vars, %d cons, success=%u\n", SCIPgetNVars(restmaster), SCIPgetNConss(restmaster), success);
588 if( heurdata->pbheur || ( nmastervars - SCIPgetNVars(restmaster) ) / (SCIP_Real)nmastervars >= heurdata->minfixingrate / 2.0 )
590 SCIP_SOL** restmastersols;
593 SCIPdebugMessage(
"solving restricted master problem: nstallnodes=%"SCIP_LONGINT_FORMAT
", maxnodes=%"SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->maxnodes);
596 retstat = SCIPsolve(restmaster);
597 if( retstat != SCIP_OKAY )
599 SCIPwarningMessage(scip,
"Error while solving subMIP in Restricted Master Heuristic; Restricted Master terminated with code <%d>\n",retstat);
602 SCIP_CALL( SCIPsolve(restmaster) );
605 SCIPdebugMessage(
" -> %d feasible solution(s) found.\n", SCIPgetNSols(restmaster));
610 nrestmastersols = SCIPgetNSols(restmaster);
611 restmastersols = SCIPgetSols(restmaster);
613 for( i = 0; i < nrestmastersols && !success; ++i )
615 SCIP_CALL(
createNewSol(origprob, scip, restmaster, restmastervars, heur, restmastersols[i], &success) );
618 *result = SCIP_FOUNDSOL;
622 SCIPfreeBufferArray(scip, &restmastervars);
623 SCIP_CALL( SCIPfree(&restmaster) );
641 SCIP_HEURDATA* heurdata;
644 SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
654 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/minfixingrate",
655 "minimum percentage of integer variables that have to be fixable ",
658 SCIP_CALL( SCIPaddLongintParam(scip,
"heuristics/"HEUR_NAME"/maxnodes",
659 "maximum number of nodes to regard in the subproblem",
660 &heurdata->maxnodes, TRUE,
DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
662 SCIP_CALL( SCIPaddLongintParam(scip,
"heuristics/"HEUR_NAME"/nodesofs",
663 "number of nodes added to the contingent of the total nodes",
664 &heurdata->nodesofs, FALSE,
DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
666 SCIP_CALL( SCIPaddLongintParam(scip,
"heuristics/"HEUR_NAME"/minnodes",
667 "minimum number of nodes required to start the subproblem",
668 &heurdata->minnodes, TRUE,
DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
670 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/nodesquot",
671 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
674 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/minimprove",
675 "factor by which restricted master should at least improve the incumbent ",
678 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/uselprows",
679 "should subproblem be created out of the rows in the LP rows?",
682 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/copycuts",
683 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
686 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/pbheur",
687 "should the restricted master heuristic be used as price-and-branch heuristic?",