42 #include "scip/scipdefplugins.h"
43 #include "scip/cons_linear.h"
45 #define HEUR_NAME "gcgrins"
46 #define HEUR_DESC "relaxation induced neighborhood search by Danna, Rothberg, and Le Pape"
47 #define HEUR_DISPCHAR 'N'
48 #define HEUR_PRIORITY -1101000
50 #define HEUR_FREQOFS 5
51 #define HEUR_MAXDEPTH -1
52 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
53 #define HEUR_USESSUBSCIP TRUE
55 #define DEFAULT_NODESOFS 500
56 #define DEFAULT_MAXNODES 5000
57 #define DEFAULT_MINNODES 500
58 #define DEFAULT_MINIMPROVE 0.01
59 #define DEFAULT_MINFIXINGRATE 0.0
60 #define DEFAULT_NODESQUOT 0.1
61 #define DEFAULT_NWAITINGNODES 200
62 #define DEFAULT_USELPROWS FALSE
64 #define DEFAULT_COPYCUTS TRUE
89 SCIP_Longint nfixfails;
91 SCIP_Real avgzerorate;
92 SCIP_Longint totalsols;
95 SCIP_Real subsciptime;
96 SCIP_Real bestprimalbd;
110 SCIP_Real minfixingrate,
112 SCIP_Real* intfixingrate,
113 SCIP_Real* zerofixingrate,
130 assert(scip != NULL);
131 assert(subscip != NULL);
132 assert(subvars != NULL);
134 assert(0.0 <= minfixingrate && minfixingrate <= 1.0);
137 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
138 bestsol = SCIPgetBestSol(scip);
139 assert(bestsol != NULL);
145 for( i = 0; i < nbinvars + nintvars; i++ )
151 lpsolval = SCIPgetRelaxSolVal(scip, vars[i]);
152 solval = SCIPgetSolVal(scip, bestsol, vars[i]);
155 if( SCIPisFeasEQ(scip, lpsolval, solval) )
158 SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], solval) );
159 SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], solval) );
161 if( SCIPisZero(scip, solval) )
167 if( fixingcounter == nbinvars + nintvars )
169 *intfixingrate = 1.0;
170 *zerofixingrate = 1.0;
176 *intfixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
177 *zerofixingrate = (SCIP_Real)zerocounter / MAX((SCIP_Real)fixingcounter, 1.0);
181 if( *intfixingrate < minfixingrate )
184 SCIPstatisticPrintf(
"gcgrins statistic: fixed only %5.2f ( %5.2f zero) integer variables --> abort \n", *intfixingrate, *zerofixingrate);
191 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
194 for( i = 0; i < nrows; i++ )
207 if( SCIProwIsLocal(rows[i]) )
211 constant = SCIProwGetConstant(rows[i]);
212 lhs = SCIProwGetLhs(rows[i]) - constant;
213 rhs = SCIProwGetRhs(rows[i]) - constant;
214 vals = SCIProwGetVals(rows[i]);
215 nnonz = SCIProwGetNNonz(rows[i]);
216 cols = SCIProwGetCols(rows[i]);
218 assert( lhs <= rhs );
221 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nnonz) );
222 for( j = 0; j < nnonz; j++ )
223 consvars[j] = subvars[SCIPvarGetProbindex(SCIPcolGetVar(cols[j]))];
226 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
227 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
228 SCIP_CALL( SCIPaddCons(subscip, cons) );
229 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
232 SCIPfreeBufferArray(scip, &consvars);
252 #ifdef SCIP_STATISTIC
253 SCIP_HEURDATA* heurdata;
257 SCIP_Real* subsolvals;
260 assert(scip != NULL);
261 assert(subscip != NULL);
262 assert(subvars != NULL);
263 assert(subsol != NULL);
265 #ifdef SCIP_STATISTIC
267 heurdata = SCIPheurGetData(heur);
268 assert( heurdata != NULL );
272 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
276 assert(nvars <= SCIPgetNOrigVars(subscip));
278 SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
281 SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
284 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
285 SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
288 SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
290 #ifdef SCIP_STATISTIC
293 if( SCIPgetSolTransObj(scip, newsol) < heurdata->bestprimalbd )
294 heurdata->bestprimalbd = SCIPgetSolTransObj(scip, newsol);
298 SCIP_CALL( SCIPfreeSol(scip, &newsol) );
300 SCIPfreeBufferArray(scip, &subsolvals);
313 SCIP_HEURDATA* heurdata;
315 assert(heur != NULL);
316 assert(scip != NULL);
319 heurdata = SCIPheurGetData(heur);
320 assert(heurdata != NULL);
323 SCIPfreeMemory(scip, &heurdata);
324 SCIPheurSetData(heur, NULL);
334 SCIP_HEURDATA* heurdata;
336 assert(heur != NULL);
337 assert(scip != NULL);
340 heurdata = SCIPheurGetData(heur);
341 assert(heurdata != NULL);
344 heurdata->usednodes = 0;
349 #ifdef SCIP_STATISTIC
354 SCIP_HEURDATA* heurdata;
356 assert(heur != NULL);
357 assert(scip != NULL);
360 heurdata = SCIPheurGetData(heur);
361 assert(heurdata != NULL);
364 heurdata->avgfixrate = 0.0;
365 heurdata->avgzerorate = 0.0;
366 heurdata->totalsols = 0;
367 heurdata->subsciptime = 0.0;
368 heurdata->bestprimalbd = SCIPinfinity(scip);
377 SCIP_HEURDATA* heurdata;
380 assert(heur != NULL);
381 assert(scip != NULL);
384 heurdata = SCIPheurGetData(heur);
385 assert(heurdata != NULL);
387 ncalls = SCIPheurGetNCalls(heur);
388 heurdata->avgfixrate /= MAX((SCIP_Real)ncalls, 1.0);
389 heurdata->avgzerorate /= MAX((SCIP_Real)ncalls, 1.0);
392 SCIPstatisticPrintf(
"LNS Statistics -- %s:\n", SCIPheurGetName(heur));
393 SCIPstatisticPrintf(
"Calls : %13"SCIP_LONGINT_FORMAT
"\n", ncalls);
394 SCIPstatisticPrintf(
"Failed Fixings : %13"SCIP_LONGINT_FORMAT
"\n", heurdata->nfixfails);
395 SCIPstatisticPrintf(
"Sols : %13"SCIP_LONGINT_FORMAT
"\n", SCIPheurGetNSolsFound(heur));
396 SCIPstatisticPrintf(
"Improving Sols : %13"SCIP_LONGINT_FORMAT
"\n", SCIPheurGetNBestSolsFound(heur));
397 SCIPstatisticPrintf(
"Total Sols : %13"SCIP_LONGINT_FORMAT
"\n", heurdata->totalsols);
398 SCIPstatisticPrintf(
"subSCIP time : %13.2f\n", heurdata->subsciptime);
399 SCIPstatisticPrintf(
"subSCIP nodes : %13"SCIP_LONGINT_FORMAT
"\n", heurdata->usednodes);
400 SCIPstatisticPrintf(
"Avg. fixing rate : %13.2f\n", 100.0 * heurdata->avgfixrate);
401 SCIPstatisticPrintf(
"Avg. zero rate : %13.2f\n", 100.0 * heurdata->avgzerorate);
402 SCIPstatisticPrintf(
"Best primal bd. :");
403 if( SCIPisInfinity(scip, heurdata->bestprimalbd) )
404 SCIPstatisticPrintf(
" infinity\n");
406 SCIPstatisticPrintf(
" %13.6e\n", heurdata->bestprimalbd);
407 SCIPstatisticPrintf(
"\n");
418 SCIP_Longint nstallnodes;
421 SCIP_HEURDATA* heurdata;
425 SCIP_HASHMAP* varmapfw;
428 SCIP_Real memorylimit;
430 SCIP_Real upperbound;
431 SCIP_Real allfixingrate;
432 SCIP_Real intfixingrate;
433 SCIP_Real zerofixingrate;
441 SCIP_RETCODE retcode;
443 assert(heur != NULL);
444 assert(scip != NULL);
445 assert(result != NULL);
449 assert(masterprob != NULL);
452 heurdata = SCIPheurGetData(heur);
453 assert(heurdata != NULL);
455 *result = SCIP_DELAYED;
460 if( !SCIPisRelaxSolValid(scip) )
462 SCIPdebugMessage(
"skipping GCG RINS: invalid relaxation solution\n");
467 if( SCIPgetNSols(scip) <= 0 )
471 if( SCIPgetStage(masterprob) > SCIP_STAGE_SOLVING || SCIPgetLPSolstat(masterprob) != SCIP_LPSOLSTAT_OPTIMAL )
475 assert(SCIPgetBestSol(scip) != NULL);
476 if( SCIPsolGetOrigin(SCIPgetBestSol(scip)) == SCIP_SOLORIGIN_ORIGINAL )
480 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes )
483 *result = SCIP_DIDNOTRUN;
488 SCIP_CALL( SCIPgetRealParam(scip,
"limits/time", &timelimit) );
489 if( !SCIPisInfinity(scip, timelimit) )
490 timelimit -= SCIPgetSolvingTime(scip);
491 SCIP_CALL( SCIPgetRealParam(scip,
"limits/memory", &memorylimit) );
494 if( !SCIPisInfinity(scip, memorylimit) )
496 memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
497 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
501 if( timelimit <= 0.0 || memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
505 nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
508 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur) + 1.0));
509 nstallnodes -= 100 * SCIPheurGetNCalls(heur);
510 nstallnodes += heurdata->nodesofs;
513 nstallnodes -= heurdata->usednodes;
514 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
517 if( nstallnodes < heurdata->minnodes )
520 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
523 if( nbinvars == 0 && nintvars == 0 )
526 if( SCIPisStopped(scip) )
529 *result = SCIP_DIDNOTFIND;
532 SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
533 SCIP_CALL( SCIPcreate(&subscip) );
536 SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
538 if( heurdata->uselprows )
540 char probname[SCIP_MAXSTRLEN];
543 SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
546 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN,
"%s_gcgrinssub", SCIPgetProbName(scip));
549 SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
552 SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, NULL, NULL, 0, TRUE) );
559 SCIP_CALL( SCIPcopy(scip, subscip, varmapfw, NULL,
"gcgrins", TRUE, FALSE, FALSE, TRUE, &valid) );
561 if( heurdata->copycuts )
564 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) );
567 SCIPdebugMessage(
"Copying the SCIP instance was %s complete.\n", valid ?
"" :
"not ");
570 for( i = 0; i < nvars; i++ )
571 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
574 SCIPhashmapFree(&varmapfw);
578 SCIPstatisticPrintf(
"gcgrins statistic: called at node %"SCIP_LONGINT_FORMAT
"\n", SCIPgetNNodes(scip));
581 SCIP_CALL(
createSubproblem(scip, subscip, subvars, heurdata->minfixingrate, heurdata->uselprows, &intfixingrate, &zerofixingrate, &success) );
582 SCIPdebugMessage(
"RINS subproblem: %d vars, %d cons, success=%u\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), success);
584 #ifdef SCIP_STATISTIC
585 heurdata->avgfixrate += intfixingrate;
586 heurdata->avgzerorate += zerofixingrate;
591 *result = SCIP_DIDNOTRUN;
592 #ifdef SCIP_STATISTIC
593 ++heurdata->nfixfails;
599 SCIP_CALL( SCIPsetIntParam(subscip,
"display/verblevel", 0) );
602 SCIP_CALL( SCIPsetLongintParam(subscip,
"limits/nodes", nstallnodes) );
603 SCIP_CALL( SCIPsetIntParam(subscip,
"limits/bestsol", 3) );
604 SCIP_CALL( SCIPsetRealParam(subscip,
"limits/time", timelimit) );
605 SCIP_CALL( SCIPsetRealParam(subscip,
"limits/memory", memorylimit) );
608 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
611 SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
614 SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
617 if( SCIPfindNodesel(subscip,
"estimate") != NULL && !SCIPisParamFixed(subscip,
"nodeselection/estimate/stdpriority") )
619 SCIP_CALL( SCIPsetIntParam(subscip,
"nodeselection/estimate/stdpriority", INT_MAX/4) );
623 if( SCIPfindBranchrule(subscip,
"inference") != NULL && !SCIPisParamFixed(subscip,
"branching/inference/priority") )
625 SCIP_CALL( SCIPsetIntParam(subscip,
"branching/inference/priority", INT_MAX/4) );
629 if( !SCIPisParamFixed(subscip,
"conflict/enable") )
631 SCIP_CALL( SCIPsetBoolParam(subscip,
"conflict/enable", FALSE) );
635 assert(!SCIPisInfinity(scip,SCIPgetUpperbound(scip)));
637 upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
638 if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
640 cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip);
644 if( SCIPgetUpperbound ( scip ) >= 0 )
645 cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( scip );
647 cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( scip );
649 cutoff = MIN(upperbound, cutoff );
650 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
653 retcode = SCIPpresolve(subscip);
658 if( retcode != SCIP_OKAY )
661 SCIP_CALL( retcode );
663 SCIPwarningMessage(scip,
"Error while presolving subproblem in GCG RINS heuristic; sub-SCIP terminated with code <%d>\n",retcode);
667 SCIPdebugMessage(
"GCG RINS presolved subproblem: %d vars, %d cons, success=%u\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), success);
669 allfixingrate = (SCIPgetNOrigVars(subscip) - SCIPgetNVars(subscip)) / (SCIP_Real)SCIPgetNOrigVars(subscip);
672 allfixingrate = MAX(allfixingrate, 0.0);
677 if( allfixingrate >= heurdata->minfixingrate / 2.0 )
683 retcode = SCIPsolve(subscip);
688 if( retcode != SCIP_OKAY )
691 SCIP_CALL( retcode );
693 SCIPwarningMessage(scip,
"Error while solving subproblem in GCG RINS heuristic; sub-SCIP terminated with code <%d>\n",retcode);
696 #ifdef SCIP_STATISTIC
697 heurdata->usednodes += SCIPgetNNodes(subscip);
698 heurdata->subsciptime += SCIPgetTotalTime(subscip);
704 nsubsols = SCIPgetNSols(subscip);
705 subsols = SCIPgetSols(subscip);
706 #ifdef SCIP_STATISTIC
707 heurdata->totalsols += nsubsols;
710 for( i = 0; i < nsubsols && !success; ++i )
712 SCIP_CALL(
createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
714 *result = SCIP_FOUNDSOL;
717 SCIPstatisticPrintf(
"gcgrins 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",
718 intfixingrate, zerofixingrate, allfixingrate, SCIPgetSolvingTime(subscip), SCIPgetSolvingTime(scip), SCIPgetNNodes(subscip), nsubsols,
719 success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip), nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 );
723 SCIPstatisticPrintf(
"gcgrins statistic: fixed only %6.3f integer variables ( %6.3f zero), %6.3f all variables --> abort \n", intfixingrate, zerofixingrate, allfixingrate);
728 SCIPfreeBufferArray(scip, &subvars);
729 SCIP_CALL( SCIPfree(&subscip) );
743 SCIP_HEURDATA* heurdata;
747 SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
750 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
754 assert(heur != NULL);
757 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeGcgrins) );
758 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitGcgrins) );
759 #ifdef SCIP_STATISTIC
760 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolGcgrins) );
761 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolGcgrins) );
765 SCIP_CALL( SCIPaddIntParam(scip,
"heuristics/"HEUR_NAME"/nodesofs",
766 "number of nodes added to the contingent of the total nodes",
769 SCIP_CALL( SCIPaddIntParam(scip,
"heuristics/"HEUR_NAME"/maxnodes",
770 "maximum number of nodes to regard in the subproblem",
773 SCIP_CALL( SCIPaddIntParam(scip,
"heuristics/"HEUR_NAME"/minnodes",
774 "minimum number of nodes required to start the subproblem",
777 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/nodesquot",
778 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
781 SCIP_CALL( SCIPaddIntParam(scip,
"heuristics/"HEUR_NAME"/nwaitingnodes",
782 "number of nodes without incumbent change that heuristic should wait",
785 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/minimprove",
786 "factor by which "HEUR_NAME" should at least improve the incumbent",
789 SCIP_CALL( SCIPaddRealParam(scip,
"heuristics/"HEUR_NAME"/minfixingrate",
790 "minimum percentage of integer variables that have to be fixed",
793 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/uselprows",
794 "should subproblem be created out of the rows in the LP rows?",
797 SCIP_CALL( SCIPaddBoolParam(scip,
"heuristics/"HEUR_NAME"/copycuts",
798 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",