43 #include "scip/scipdefplugins.h"
44 #include "scip/cons_linear.h"
47 #define HEUR_NAME "gcgrens"
48 #define HEUR_DESC "LNS exploring fractional neighborhood of relaxation's optimum"
49 #define HEUR_DISPCHAR 'E'
50 #define HEUR_PRIORITY -1100000
52 #define HEUR_FREQOFS 0
53 #define HEUR_MAXDEPTH -1
54 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
55 #define HEUR_USESSUBSCIP TRUE
58 #define DEFAULT_BINARYBOUNDS TRUE
59 #define DEFAULT_MAXNODES 5000LL
60 #define DEFAULT_MINFIXINGRATE 0.5
61 #define DEFAULT_MINIMPROVE 0.01
62 #define DEFAULT_MINNODES 500LL
63 #define DEFAULT_NODESOFS 500LL
64 #define DEFAULT_NODESQUOT 0.1
65 #define DEFAULT_USELPROWS FALSE
67 #define DEFAULT_COPYCUTS TRUE
70 #define DEFAULT_ADDALLSOLS FALSE
95 SCIP_Longint nfixfails;
97 SCIP_Real avgzerorate;
98 SCIP_Longint totalsols;
101 SCIP_Real subsciptime;
102 SCIP_Real bestprimalbd;
117 SCIP_Real minfixingrate,
118 SCIP_Bool binarybounds,
120 SCIP_Real* intfixingrate,
121 SCIP_Real* zerofixingrate,
134 assert(scip != NULL);
135 assert(subscip != NULL);
136 assert(subvars != NULL);
138 assert(0.0 <= minfixingrate && minfixingrate <= 1.0);
141 SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
147 for( i = 0; i < nbinvars + nintvars; i++ )
154 lpsolval = SCIPgetRelaxSolVal(scip, vars[i]);
156 if( SCIPisFeasIntegral(scip, lpsolval) )
161 lb = SCIPfloor(scip, lpsolval+0.5);
164 if( SCIPisZero(scip, lb) )
167 else if( binarybounds )
170 lb = SCIPfeasFloor(scip,lpsolval);
171 ub = SCIPfeasCeil(scip,lpsolval);
176 lb = SCIPvarGetLbGlobal(vars[i]);
177 ub = SCIPvarGetUbGlobal(vars[i]);
181 SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], lb) );
182 SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], ub) );
186 if( fixingcounter == nbinvars + nintvars )
188 *intfixingrate = 1.0;
189 *zerofixingrate = 1.0;
195 *intfixingrate = fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
196 *zerofixingrate = (SCIP_Real)zerocounter / MAX((SCIP_Real)fixingcounter, 1.0);
200 if( *intfixingrate < minfixingrate )
203 SCIPstatisticPrintf(
"gcgrens statistic: fixed only %5.2f ( %5.2f zero) integer variables --> abort \n", *intfixingrate, *zerofixingrate);
213 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
216 for( i = 0; i < nrows; i++ )
229 if( SCIProwIsLocal(rows[i]) )
233 constant = SCIProwGetConstant(rows[i]);
234 lhs = SCIProwGetLhs(rows[i]) - constant;
235 rhs = SCIProwGetRhs(rows[i]) - constant;
236 vals = SCIProwGetVals(rows[i]);
237 nnonz = SCIProwGetNNonz(rows[i]);
238 cols = SCIProwGetCols(rows[i]);
243 SCIP_CALL( SCIPallocBufferArray(subscip, &consvars, nnonz) );
244 for( j = 0; j < nnonz; j++ )
245 consvars[j] = subvars[SCIPvarGetProbindex(SCIPcolGetVar(cols[j]))];
248 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
249 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
250 SCIP_CALL( SCIPaddCons(subscip, cons) );
251 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
254 SCIPfreeBufferArray(subscip, &consvars);
274 #ifdef SCIP_STATISTIC
275 SCIP_HEURDATA* heurdata;
279 SCIP_Real* subsolvals;
282 assert(scip != NULL);
283 assert(subscip != NULL);
284 assert(subvars != NULL);
285 assert(subsol != NULL);
287 #ifdef SCIP_STATISTIC
289 heurdata = SCIPheurGetData(heur);
290 assert( heurdata != NULL );
294 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
299 assert(nvars <= SCIPgetNOrigVars(subscip));
301 SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
304 SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
307 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
308 SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
311 #ifdef SCIP_STATISTIC
312 if( !*success || heurdata->addallsols )
314 SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
316 #ifdef SCIP_STATISTIC
317 if( SCIPgetSolTransObj(scip, newsol) < heurdata->bestprimalbd )
318 heurdata->bestprimalbd = SCIPgetSolTransObj(scip, newsol);
320 SCIPstatisticPrintf(
"gcgrens statistic: Solution %13.6e found at node %"SCIP_LONGINT_FORMAT
"\n",
321 SCIPgetSolTransObj(scip, newsol), SCIPsolGetNodenum(subsol));
324 SCIP_CALL( SCIPfreeSol(scip, &newsol) );
326 SCIPfreeBufferArray(scip, &subsolvals);
336 SCIP_Real minfixingrate,
337 SCIP_Real minimprove,
338 SCIP_Longint maxnodes,
339 SCIP_Longint nstallnodes,
340 SCIP_Bool binarybounds,
345 SCIP_HASHMAP* varmapfw;
348 SCIP_HEURDATA* heurdata;
351 SCIP_Real memorylimit;
352 SCIP_Real allfixingrate;
353 SCIP_Real intfixingrate;
354 SCIP_Real zerofixingrate;
360 SCIP_RETCODE retcode;
362 assert(scip != NULL);
363 assert(heur != NULL);
364 assert(result != NULL);
366 assert(maxnodes >= 0);
367 assert(nstallnodes >= 0);
369 assert(0.0 <= minfixingrate && minfixingrate <= 1.0);
370 assert(0.0 <= minimprove && minimprove <= 1.0);
373 heurdata = SCIPheurGetData(heur);
374 assert(heurdata != NULL);
379 SCIP_CALL( SCIPgetRealParam(scip,
"limits/time", &timelimit) );
380 if( !SCIPisInfinity(scip, timelimit) )
381 timelimit -= SCIPgetSolvingTime(scip);
382 SCIP_CALL( SCIPgetRealParam(scip,
"limits/memory", &memorylimit) );
385 if( !SCIPisInfinity(scip, memorylimit) )
387 memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
388 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
392 if( timelimit <= 0.0 || memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
395 *result = SCIP_DIDNOTFIND;
398 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
401 SCIP_CALL( SCIPcreate(&subscip) );
404 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
405 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
410 char probname[SCIP_MAXSTRLEN];
413 SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
416 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN,
"%s_gcgrenssub", SCIPgetProbName(scip));
419 SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
422 SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, NULL, NULL, 0, TRUE) );
431 SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL,
"gcgrens", TRUE, FALSE, FALSE, TRUE, &valid) );
433 if( heurdata->copycuts )
436 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) );
439 SCIPdebugMessage(
"Copying the SCIP instance was %s complete.\n", valid ?
"" :
"not ");
442 for( i = 0; i < nvars; i++ )
443 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
446 SCIPhashmapFree(&varmapfw);
448 SCIPstatisticPrintf(
"gcgrens statistic: called at node %"SCIP_LONGINT_FORMAT
"\n", SCIPgetNNodes(scip));
451 SCIP_CALL(
createSubproblem(scip, subscip, subvars, minfixingrate, binarybounds, uselprows, &intfixingrate, &zerofixingrate, &success) );
452 SCIPdebugMessage(
"RENS subproblem: %d vars, %d cons, success=%u\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), success);
455 SCIP_CALL( SCIPsetBoolParam(subscip,
"misc/catchctrlc", FALSE) );
458 SCIP_CALL( SCIPsetIntParam(subscip,
"display/verblevel", 0) );
461 SCIP_CALL( SCIPsetLongintParam(subscip,
"limits/stallnodes", nstallnodes) );
462 SCIP_CALL( SCIPsetLongintParam(subscip,
"limits/nodes", maxnodes) );
463 SCIP_CALL( SCIPsetRealParam(subscip,
"limits/time", timelimit) );
464 SCIP_CALL( SCIPsetRealParam(subscip,
"limits/memory", memorylimit) );
467 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
470 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
473 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
476 if( SCIPfindNodesel(subscip,
"estimate") != NULL && !SCIPisParamFixed(subscip,
"nodeselection/estimate/stdpriority") )
478 SCIP_CALL( SCIPsetIntParam(subscip,
"nodeselection/estimate/stdpriority", INT_MAX/4) );
482 if( SCIPfindBranchrule(subscip,
"inference") != NULL && !SCIPisParamFixed(subscip,
"branching/inference/priority") )
484 SCIP_CALL( SCIPsetIntParam(subscip,
"branching/inference/priority", INT_MAX/4) );
488 if( !SCIPisParamFixed(subscip,
"conflict/enable") )
490 SCIP_CALL( SCIPsetBoolParam(subscip,
"conflict/enable", FALSE) );
495 SCIP_CALL( SCIPsetIntParam(subscip,
"display/verblevel", 5) );
496 SCIP_CALL( SCIPsetIntParam(subscip,
"display/freq", 100000000) );
499 #ifdef SCIP_STATISTIC
500 heurdata->avgfixrate += intfixingrate;
501 heurdata->avgzerorate += zerofixingrate;
507 *result = SCIP_DIDNOTRUN;
508 SCIPfreeBufferArray(scip, &subvars);
509 SCIP_CALL( SCIPfree(&subscip) );
510 #ifdef SCIP_STATISTIC
511 ++heurdata->nfixfails;
517 if( SCIPgetNSols(scip) > 0 )
520 SCIP_Real upperbound;
521 assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
523 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
525 if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
527 cutoff = (1-minimprove)*SCIPgetUpperbound(scip) + minimprove*SCIPgetLowerbound(scip);
531 if( SCIPgetUpperbound ( scip ) >= 0 )
532 cutoff = ( 1 - minimprove ) * SCIPgetUpperbound ( scip );
534 cutoff = ( 1 + minimprove ) * SCIPgetUpperbound ( scip );
536 cutoff = MIN(upperbound, cutoff);
537 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
540 retcode = SCIPpresolve(subscip);
545 if( retcode != SCIP_OKAY )
548 SCIP_CALL( retcode );
550 SCIPwarningMessage(scip,
"Error while presolving subproblem in GCG RENS heuristic; sub-SCIP terminated with code <%d>\n",retcode);
553 SCIPfreeBufferArray(scip, &subvars);
554 SCIP_CALL( SCIPfree(&subscip) );
558 SCIPdebugMessage(
"GCG RENS presolved subproblem: %d vars, %d cons, success=%u\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), success);
560 allfixingrate = (SCIPgetNOrigVars(subscip) - SCIPgetNVars(subscip)) / (SCIP_Real)SCIPgetNOrigVars(subscip);
563 allfixingrate = MAX(allfixingrate, 0.0);
568 if( allfixingrate >= minfixingrate / 2.0 )
574 SCIPdebugMessage(
"solving subproblem: nstallnodes=%"SCIP_LONGINT_FORMAT
", maxnodes=%"SCIP_LONGINT_FORMAT
"\n", nstallnodes, maxnodes);
575 retcode = SCIPsolve(subscip);
580 if( retcode != SCIP_OKAY )
583 SCIP_CALL( retcode );
585 SCIPwarningMessage(scip,
"Error while solving subproblem in GCG RENS heuristic; sub-SCIP terminated with code <%d>\n",retcode);
588 #ifdef SCIP_STATISTIC
589 heurdata->usednodes += SCIPgetNNodes(subscip);
590 heurdata->subsciptime += SCIPgetTotalTime(subscip);
596 nsubsols = SCIPgetNSols(subscip);
597 subsols = SCIPgetSols(subscip);
599 #ifdef SCIP_STATISTIC
600 heurdata->totalsols += nsubsols;
601 for( i = 0; i < nsubsols; ++i )
603 for( i = 0; i < nsubsols && (!success || heurdata->addallsols); ++i )
606 SCIP_CALL(
createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
608 *result = SCIP_FOUNDSOL;
611 SCIPstatisticPrintf(
"gcgrens statistic: fixed %6.3f integer variables ( %6.3f zero), %6.3f all variables, needed %6.1f sec (SCIP time: %6.1f sec), %"SCIP_LONGINT_FORMAT
" nodes, found %d solutions, solution %10.4f found at node %"SCIP_LONGINT_FORMAT
"\n",
612 intfixingrate, zerofixingrate, allfixingrate, SCIPgetSolvingTime(subscip), SCIPgetSolvingTime(scip), SCIPgetNNodes(subscip), nsubsols,
613 success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip), nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 );
617 SCIPstatisticPrintf(
"gcgrens statistic: fixed only %6.3f integer variables ( %6.3f zero), %6.3f all variables --> abort \n", intfixingrate, zerofixingrate, allfixingrate);
621 SCIPfreeBufferArray(scip, &subvars);
622 SCIP_CALL( SCIPfree(&subscip) );
635 SCIP_HEURDATA* heurdata;
637 assert( heur != NULL );
638 assert( scip != NULL );
641 heurdata = SCIPheurGetData(heur);
642 assert( heurdata != NULL );
645 SCIPfreeMemory(scip, &heurdata);
646 SCIPheurSetData(heur, NULL);
656 SCIP_HEURDATA* heurdata;
658 assert( heur != NULL );
659 assert( scip != NULL );
662 heurdata = SCIPheurGetData(heur);
663 assert( heurdata != NULL );
666 heurdata->usednodes = 0;
671 #ifdef SCIP_STATISTIC
676 SCIP_HEURDATA* heurdata;
678 assert(heur != NULL);
679 assert(scip != NULL);
682 heurdata = SCIPheurGetData(heur);
683 assert(heurdata != NULL);
686 heurdata->avgfixrate = 0.0;
687 heurdata->avgzerorate = 0.0;
688 heurdata->totalsols = 0;
689 heurdata->subsciptime = 0.0;
690 heurdata->bestprimalbd = SCIPinfinity(scip);
699 SCIP_HEURDATA* heurdata;
702 assert(heur != NULL);
703 assert(scip != NULL);
706 heurdata = SCIPheurGetData(heur);
707 assert(heurdata != NULL);
709 ncalls = SCIPheurGetNCalls(heur);
710 heurdata->avgfixrate /= MAX((SCIP_Real)ncalls, 1.0);
711 heurdata->avgzerorate /= MAX((SCIP_Real)ncalls, 1.0);
714 SCIPstatisticPrintf(
"LNS Statistics -- %s:\n", SCIPheurGetName(heur));
715 SCIPstatisticPrintf(
"Calls : %13"SCIP_LONGINT_FORMAT
"\n", ncalls);
716 SCIPstatisticPrintf(
"Failed Fixings : %13"SCIP_LONGINT_FORMAT
"\n", heurdata->nfixfails);
717 SCIPstatisticPrintf(
"Sols : %13"SCIP_LONGINT_FORMAT
"\n", SCIPheurGetNSolsFound(heur));
718 SCIPstatisticPrintf(
"Improving Sols : %13"SCIP_LONGINT_FORMAT
"\n", SCIPheurGetNBestSolsFound(heur));
719 SCIPstatisticPrintf(
"Total Sols : %13"SCIP_LONGINT_FORMAT
"\n", heurdata->totalsols);
720 SCIPstatisticPrintf(
"subSCIP time : %13.2f\n", heurdata->subsciptime);
721 SCIPstatisticPrintf(
"subSCIP nodes : %13"SCIP_LONGINT_FORMAT
"\n", heurdata->usednodes);
722 SCIPstatisticPrintf(
"Avg. fixing rate : %13.2f\n", 100.0 * heurdata->avgfixrate);
723 SCIPstatisticPrintf(
"Avg. zero rate : %13.2f\n", 100.0 * heurdata->avgzerorate);
724 SCIPstatisticPrintf(
"Best primal bd. :");
725 if( SCIPisInfinity(scip, heurdata->bestprimalbd) )
726 SCIPstatisticPrintf(
" infinity\n");
728 SCIPstatisticPrintf(
" %13.6e\n", heurdata->bestprimalbd);
729 SCIPstatisticPrintf(
"\n");
741 SCIP_HEURDATA* heurdata;
742 SCIP_Longint nstallnodes;
744 assert( heur != NULL );
745 assert( scip != NULL );
746 assert( result != NULL );
750 assert( masterprob != NULL);
753 heurdata = SCIPheurGetData(heur);
754 assert( heurdata != NULL );
756 *result = SCIP_DELAYED;
761 if( !SCIPisRelaxSolValid(scip) )
763 SCIPdebugMessage(
"skipping GCG RENS: invalid relaxation solution\n");
768 if( SCIPgetStage(masterprob) > SCIP_STAGE_SOLVING || SCIPgetLPSolstat(masterprob) != SCIP_LPSOLSTAT_OPTIMAL )
771 *result = SCIP_DIDNOTRUN;
774 if( SCIPgetNExternBranchCands(scip) == 0 )
777 *result = SCIP_DIDNOTRUN;
780 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
783 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
784 nstallnodes -= 100 * SCIPheurGetNCalls(heur);
785 nstallnodes += heurdata->nodesofs;
788 nstallnodes -= heurdata->usednodes;
789 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
792 if( nstallnodes < heurdata->minnodes )
794 SCIPdebugMessage(
"skipping RENS: nstallnodes=%"SCIP_LONGINT_FORMAT
", minnodes=%"SCIP_LONGINT_FORMAT
"\n", nstallnodes, heurdata->minnodes);
798 if( SCIPisStopped(scip) )
801 SCIP_CALL(
GCGapplyGcgrens(scip, heur, result, heurdata->minfixingrate, heurdata->minimprove,
802 heurdata->maxnodes, nstallnodes, heurdata->binarybounds, heurdata->uselprows) );
818 SCIP_HEURDATA* heurdata;
822 SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
825 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
829 assert(heur != NULL);
832 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGcgrens) );
833 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGcgrens) );
834 #ifdef SCIP_STATISTIC
835 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolGcgrens) );
836 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolGcgrens) );
841 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/minfixingrate",
842 "minimum percentage of integer variables that have to be fixable",
845 SCIP_CALL( SCIPaddLongintParam(scip,
"heuristics/"HEUR_NAME"/maxnodes",
846 "maximum number of nodes to regard in the subproblem",
847 &heurdata->maxnodes, TRUE,
DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
849 SCIP_CALL( SCIPaddLongintParam(scip,
"heuristics/"HEUR_NAME"/nodesofs",
850 "number of nodes added to the contingent of the total nodes",
851 &heurdata->nodesofs, FALSE,
DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
853 SCIP_CALL( SCIPaddLongintParam(scip,
"heuristics/"HEUR_NAME"/minnodes",
854 "minimum number of nodes required to start the subproblem",
855 &heurdata->minnodes, TRUE,
DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
857 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/nodesquot",
858 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
861 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/minimprove",
862 "factor by which RENS should at least improve the incumbent",
865 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/binarybounds",
866 "should general integers get binary bounds [floor(.),ceil(.)] ?",
869 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/uselprows",
870 "should subproblem be created out of the rows in the LP rows?",
873 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/copycuts",
874 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
877 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/addallsols",
878 "should all subproblem solutions be added to the original SCIP?",