81#define HEUR_NAME "gins"
82#define HEUR_DESC "gins works on k-neighborhood in a variable-constraint graph"
83#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
84#define HEUR_PRIORITY -1103000
87#define HEUR_MAXDEPTH -1
88#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
89#define HEUR_USESSUBSCIP TRUE
91#define DEFAULT_NODESOFS 500
92#define DEFAULT_MAXNODES 5000
93#define DEFAULT_MINIMPROVE 0.01
94#define DEFAULT_MINNODES 50
95#define DEFAULT_MINFIXINGRATE 0.66
96#define DEFAULT_NODESQUOT 0.15
97#define DEFAULT_NWAITINGNODES 100
98#define DEFAULT_USELPROWS FALSE
100#define DEFAULT_COPYCUTS TRUE
102#define DEFAULT_BESTSOLLIMIT 3
103#define DEFAULT_FIXCONTVARS FALSE
104#define DEFAULT_POTENTIAL 'r'
105#define DEFAULT_MAXDISTANCE 3
107#define DEFAULT_RANDSEED 71
108#define DEFAULT_RELAXDENSECONSS FALSE
110#define DEFAULT_USEROLLINGHORIZON TRUE
111#define DEFAULT_ROLLHORIZONLIMFAC 0.4
113#define DEFAULT_USEDECOMP TRUE
114#define DEFAULT_USEDECOMPROLLHORIZON FALSE
115#define DEFAULT_USESELFALLBACK TRUE
116#define DEFAULT_OVERLAP 0.0
117#define DEFAULT_CONSECUTIVEBLOCKS TRUE
204 int sumneighborhoodvars;
205 int sumdiscneighborhoodvars;
220 int nrelaxedconstraints;
255 if( nfixings < fixthreshold )
257 SCIPdebugMsg(
scip,
"Fixed %d < %d variables in gins heuristic, stopping\n", nfixings, fixthreshold);
263 SCIPdebugMsg(
scip,
"Fixed enough (%d >= %d) variables in gins heuristic\n", nfixings, fixthreshold);
326 referencepoint = 0.0;
335 potential += objdelta;
350 assert(leftborder <= rightborder);
378 decomphorizonptr = *decomphorizon;
379 decomphorizonptr->
decomp = decomp;
380 decomphorizonptr->
memsize = memsize = nblocks + 1;
415 if( *decomphorizon ==
NULL )
418 decomphorizonptr = *decomphorizon;
432 *decomphorizon =
NULL;
459 return decomphorizon->
init;
478 assert(ind1 < decomphorizon->nblocks);
479 assert(ind2 < decomphorizon->nblocks);
496 else if( decomphorizon->
suitable[ind2] )
508 if( potentialbysize1 > potentialbysize2 )
510 else if( potentialbysize2 > potentialbysize1 )
555 decomphorizon->
vars = varscopy;
562 while( currblockstart <
nvars )
569 assert(blockpos < decomphorizon->memsize);
571 blocklabel = varlabels[currblockstart];
572 currblockend = currblockstart;
583 while( currblockend <
nvars && varlabels[currblockend] == blocklabel );
586 nfixedvars =
nvars - (currblockend - currblockstart);
588 nfixedvars =
nvars - ncontvarsscip - ndiscretevars;
592 decomphorizon->
suitable[blockpos] = suitable;
594 decomphorizon->
varblockend[blockpos] = currblockend;
595 decomphorizon->
nvars[blockpos] = currblockend - currblockstart;
598 currblockstart = currblockend;
599 nstblblocks += (suitable ? 1 : 0);
605 decomphorizon->
nblocks = blockpos;
614 SCIPdebugMsg(
scip,
"Initialized decomposition horizon for %d blocks (%d suitable)\n",
674 SCIPdebugMsg(
scip,
"New potential based sorting with trailing block: 0 (label %d, potential %.4g)\n",
675 decomphorizon->blocklabels[decomphorizon->blockindices[0]], decomphorizon->potential[decomphorizon->blockindices[0]]);
681 b1 = linkvarsexist ? 0 : -1;
684 intervalpotential = 0.0;
686 withlinkvars =
FALSE;
688 while( b1 < decomphorizon->nblocks - 1 )
698 intervalpotential = 0.0;
699 withlinkvars =
FALSE;
708 assert(nintervalvars < maxblocksize);
709 intervalpotential = decomphorizon->
potential[blockindb1];
710 withlinkvars =
FALSE;
717 assert(b1 > (linkvarsexist ? 1 : 0));
721 intervalpotential -= decomphorizon->
potential[prevblockind];
725 if( ! withlinkvars && linkvarsexist && decomphorizon->
ndiscretevars[0] + decomphorizon->
ndiscretevars[blockindb1] < maxblocksize )
733 withlinkvars =
FALSE;
739 while( ++b2 < decomphorizon->nblocks )
743 if( ! decomphorizon->
suitable[blockindb2] || nintervalvars + decomphorizon->
ndiscretevars[blockindb2] >= maxblocksize )
747 intervalpotential += decomphorizon->
potential[blockindb2];
751 if( intervalpotential > maxpotential )
754 maxpotential = intervalpotential;
758 SCIPdebugMsg(
scip,
"Potential based selection chooses interval starting from block %d with potential %.1g\n",
759 bestpos, maxpotential);
775 assert(blockpos < decomphorizon->nblocks);
778 (decomphorizon->
overlapinterval[0] <= blockpos && blockpos <= decomphorizon->overlapinterval[1]));
791 int* blockintervalstart,
792 int* blockintervalend,
817 assert(! found || (firstpos >= 0 && firstpos < decomphorizon->nblocks));
826 pos = (firstpos + 1) % decomphorizon->
nblocks;
828 while( pos < decomphorizon->nblocks &&
833 if( pos == decomphorizon->
nblocks )
836 while( pos < firstpos &&
850 *blockintervalstart = pos;
851 *blockintervalend = pos;
857 *fixlinkvars = decomphorizon->
ndiscretevars[0] + ndiscretevars > maxblocksize;
861 if( !(*fixlinkvars) )
867 *blockintervalend = pos;
877 *blockintervalstart = *blockintervalend = -1;
878 *nextblocklabel = -100;
893 return decomphorizon->
vars;
911 (*rollinghorizon)->distancessize = size;
912 (*rollinghorizon)->variablegraph =
NULL;
913 (*rollinghorizon)->lastdistance = -1;
914 (*rollinghorizon)->niterations = 0;
915 (*rollinghorizon)->nused = 0;
946 (*taboolist)->memsize = initialsize;
962 if( *taboolist ==
NULL )
1033 assert(k <= taboolist->ntaboolabels);
1059 if( *rollinghorizon ==
NULL )
1062 if( (*rollinghorizon)->variablegraph !=
NULL )
1086 return (rollinghorizon->
nused < maxnused);
1104 if( distances[
i] == -1 )
1119 assert(maxdistance >= 0);
1178 for(
i = 0;
i < nvarstofix;
i++ )
1181 if( distances[
i] == -1 || distances[
i] > maxdistance )
1190 fixedvars[*nfixings] =
vars[
i];
1191 fixedvals[*nfixings] = fixval;
1197 ++rollinghorizon->
nused;
1202 if( rollinghorizon !=
NULL )
1219 int* choosevardistance
1223 int nrelevantdistances;
1248 criticalidx = zeropos + (int)((1.0 -
heurdata->minfixingrate) * nrelevantdistances);
1249 criticalidx =
MIN(criticalidx, nrelevantdistances - 1);
1252 *choosevardistance = distancescopy[criticalidx];
1258 if( criticalidx != nrelevantdistances - 1 && distancescopy[criticalidx + 1] == *choosevardistance )
1259 (*choosevardistance)--;
1262 heurdata->maxseendistance =
MAX(
heurdata->maxseendistance, distancescopy[nrelevantdistances - 1]);
1286 int label = labels[start];
1297 while( end < nlabels && labels[end] == label );
1311 int* selvarmaxdistance
1353 int nblockstokeep = 3;
1355 int ntaboolistelems;
1361 nblockstokeep =
MIN(nblockstokeep, nblocks - 1);
1362 nblockstokeep =
MIN(nblockstokeep,
MAX(1, ntaboolistelems - 1));
1363 nblockstokeep =
MAX(nblockstokeep, 0);
1368 SCIPdebugMsg(
scip,
"Resetting taboo list, keeping %d elements\n", nblockstokeep);
1369 if( nblockstokeep > 0 )
1372 int* taboolistlastk;
1379 for( e = 0; e < nblockstokeep; ++e )
1386 else if( ntaboolistelems > 0 )
1396 if(
heurdata->allblocksunsuitable )
1398 SCIPdebugMsg(
scip,
"Skip initial variable selection because all blocks are unsuitable for solution %d\n",
1416 bestpotential = 0.0;
1420 while( currblockstart <
nvars )
1424 int label = varlabels[currblockstart];
1428 currblockend = currblockstart +
countLabel(varlabels, currblockstart,
nvars);
1433 if( cntmessages++ < 3 )
1436 currblockstart += currblockend;
1447 for( v = currblockstart; v < currblockend; ++v )
1450 discvaridxs[ndiscblockvars++] = v;
1454 if( ndiscblockvars > 0 )
1458 if( potential > bestpotential )
1460 bestpotential = potential;
1467 currblockstart += currblockend;
1471 if( bestvaridx >= 0 )
1473 *selvar = varscopy[bestvaridx];
1482 SCIPdebugMsg(
scip,
"Could not find suitable block for variable selection.\n");
1488 if( *selvar !=
NULL )
1491 heurdata->maxdistance == -1 ? INT_MAX :
heurdata->maxdistance, INT_MAX, INT_MAX) );
1496 if( *selvarmaxdistance == 0 )
1523 int* selvarmaxdistance
1533 int nintegralvarsleft;
1534 int nintegralvarsbound;
1561 maxdistance = (
heurdata->maxdistance == - 1 ? INT_MAX :
heurdata->maxdistance);
1567 for( v = nintegralvarsleft - 1; v >= 0; --v )
1571 varscopy[v] = varscopy[nintegralvarsleft - 1];
1572 --nintegralvarsleft;
1578 searchlimit =
MIN(searchlimit, 10);
1581 while( nsearched < searchlimit && nintegralvarsleft > 0 )
1585 int neighborhoodsize;
1586 int ndiscvarsneighborhood;
1587 int choosevardistance;
1595 choosevar = varscopy[idx];
1600 varscopy[idx] = varscopy[nintegralvarsleft - 1];
1601 --nintegralvarsleft;
1609 SCIPdebugMsg(
scip,
"No active variable left to perform breadth-first search\n");
1624 choosevardistance =
heurdata->maxdistance;
1631 ndiscvarsneighborhood = 0;
1632 neighborhoodsize = 0;
1635 for( v =
nvars - 1; v >= 0; --v )
1643 neighborhood[neighborhoodsize++] = currvar;
1647 ++ndiscvarsneighborhood;
1652 if( ndiscvarsneighborhood >= nintegralvarsbound || ndiscvarsneighborhood <= 1 )
1654 SCIPdebugMsg(
scip,
"Too many or too few discrete variables in neighboorhood: %d (%d)\n",
1663 if( potential > maxpotential )
1665 maxpotential = potential;
1666 *selvar = choosevar;
1667 *selvarmaxdistance = choosevardistance;
1672 for( v = nintegralvarsleft - 1; v >= 0; --v )
1679 varscopy[v] = varscopy[nintegralvarsleft - 1];
1680 --nintegralvarsleft;
1684 heurdata->sumdiscneighborhoodvars += ndiscvarsneighborhood;
1685 heurdata->sumneighborhoodvars += neighborhoodsize;
1697 SCIPdebugMsg(
scip,
"Stopping with maxpotential %15.9f and selected variable %s\n",
1713 int* selvarmaxdistance
1720 int minunuseddistance;
1736 minunuseddistance = INT_MAX;
1742 && rollinghorizon->
distances[
i] < minunuseddistance && ! rollinghorizon->
used[
i] )
1744 minunuseddistance = rollinghorizon->
distances[
i];
1750 if( *selvar ==
NULL )
1752 *selvarmaxdistance = 0;
1762 if( *selvarmaxdistance == 0 )
1765 rollinghorizon->
nused++;
1774 assert(*selvarmaxdistance <= rollinghorizon->lastmaxdistance);
1794 int nvarsstartofinterval;
1808 overlapcomplement = 1.0;
1810 overlapcomplement = 1.0 -
heurdata->overlap;
1814 for(
b = blockstartpos;
b <= blockendpos; ++
b )
1817 nvarsstartofinterval = 0;
1819 for( solstamppos = blockstartpos; solstamppos <= blockendpos; ++solstamppos )
1824 if( nvarsstartofinterval >= overlapcomplement * nvarsinterval )
1828 SCIPdebugMsg(
scip,
"Blocks %d (label %d)-- %d (label %d) marked with incumbent solution\n",
1871 &currblockstart, &currblockend, &currblocklabel, &fixlinkvars);
1885 int startblockposs[] = {fixlinkvars ? 0 : 1, currblockend + 1};
1886 int endblockposs[] = {currblockstart, decomphorizon->
nblocks};
1890 SCIPdebugMsg(
scip,
"Fix %s variables (%scluding linking variables) except blocks %d (label %d) -- %d (label %d)\n",
1891 heurdata->fixcontvars ?
"all" :
"discrete",
1892 fixlinkvars ?
"in" :
"ex",
1902 for( p = 0; p < 2; ++p )
1905 for(
b = startblockposs[p];
b < endblockposs[p]; ++
b )
1908 int varstartpos = blockind == 0 ? 0 : decomphorizon->
varblockend[blockind - 1];
1909 int varendpos = decomphorizon->
varblockend[blockind];
1912 for( v = varstartpos; v < varendpos; ++v )
1925 fixedvars[*nfixings] =
var;
1926 fixedvals[*nfixings] = fixval;
1954 currdecomp = ndecomps;
1956 while( --currdecomp >= 0 )
1959 return decomps[currdecomp];
1987 int selvarmaxdistance;
1995 selvarmaxdistance = 0;
2000 if( decomphorizon !=
NULL )
2005 if( *success || !
heurdata->useselfallback )
2012 if( rollinghorizon !=
NULL )
2043 if(
heurdata->usedecomprollhorizon )
2046 if( decomp !=
NULL )
2049 distances, &selvar, &selvarmaxdistance) );
2051 userandomselection = (selvar ==
NULL &&
heurdata->useselfallback);
2055 assert(selvar ==
NULL || !userandomselection);
2059 if( userandomselection )
2065 if( selvar !=
NULL && rollinghorizon !=
NULL )
2079 assert(selvar ==
NULL || selvarmaxdistance > 0);
2080 if( selvar ==
NULL )
2086 SCIPdebugMsg(
scip,
"Selected variable <%s> as central variable for a <%d>-neighborhood\n",
2091 selvarmaxdistance, nfixings) );
2097 if( rollinghorizon ==
NULL )
2248 confidence = confidence / (confidence + 5.0);
2387 printHistogram(
scip,
heurdata->consvarshist,
"Constraint density histogram");
2388 printHistogram(
scip,
heurdata->conscontvarshist,
"Constraint continuous density histogram");
2389 printHistogram(
scip,
heurdata->consdiscvarshist,
"Constraint discrete density histogram");
2475 rollinghorizon =
NULL;
2481 decomphorizon =
heurdata->decomphorizon;
2483 if( decomphorizon ==
NULL &&
heurdata->userollinghorizon )
2574 runagain = success && (newincumbent != oldincumbent) &&
heurdata->userollinghorizon;
2580 if( rollinghorizon !=
NULL )
2582 else if( decomphorizon !=
NULL )
2639 "number of nodes added to the contingent of the total nodes",
2643 "maximum number of nodes to regard in the subproblem",
2647 "minimum number of nodes required to start the subproblem",
2651 "number of nodes without incumbent change that heuristic should wait",
2655 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
2659 "percentage of integer variables that have to be fixed",
2663 "factor by which " HEUR_NAME " should at least improve the incumbent",
2667 "should subproblem be created out of the rows in the LP rows?",
2671 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
2675 "should continuous variables outside the neighborhoods be fixed?",
2679 "limit on number of improving incumbent solutions in sub-CIP",
2683 "maximum distance to selected variable to enter the subproblem, or -1 to select the distance "
2684 "that best approximates the minimum fixing rate from below",
2688 "the reference point to compute the neighborhood potential: (r)oot, (l)ocal lp, or (p)seudo solution",
2692 "should the heuristic solve a sequence of sub-MIP's around the first selected variable",
2696 "should dense constraints (at least as dense as 1 - minfixingrate) be ignored by connectivity graph?",
2700 "limiting percentage for variables already used in sub-SCIPs to terminate rolling horizon approach",
2704 "overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block",
2708 "should user decompositions be considered, if available?",
2712 "should user decompositions be considered for initial selection in rolling horizon, if available?",
2716 "should random initial variable selection be used if decomposition was not successful?",
2720 "should blocks be treated consecutively (sorted by ascending label?)",
#define SCIP_CALL_ABORT(x)
#define SCIP_LONGINT_FORMAT
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
int SCIPdecompGetNBlocks(SCIP_DECOMP *decomp)
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
SCIP_Bool SCIPdecompIsOriginal(SCIP_DECOMP *decomp)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
int SCIPgetNImplVars(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
int SCIPgetNVars(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
int SCIPgetNBinVars(SCIP *scip)
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
SCIP_RETCODE SCIPincludeHeurGins(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
int SCIPgetNSols(SCIP *scip)
SCIP_Bool SCIPsolIsOriginal(SCIP_SOL *sol)
int SCIPsolGetIndex(SCIP_SOL *sol)
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNTotalNodes(SCIP *scip)
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPvariableGraphFree(SCIP *scip, SCIP_VGRAPH **vargraph)
SCIP_RETCODE SCIPvariablegraphBreadthFirst(SCIP *scip, SCIP_VGRAPH *vargraph, SCIP_VAR **startvars, int nstartvars, int *distances, int maxdistance, int maxvars, int maxbinintvars)
SCIP_RETCODE SCIPvariableGraphCreate(SCIP *scip, SCIP_VGRAPH **vargraph, SCIP_Bool relaxdenseconss, SCIP_Real relaxdensity, int *nrelaxedconstraints)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
int SCIPvarGetProbindex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
void SCIPsortInt(int *intarray, int len)
SCIPfreeRandom(scip, &heurdata->randnumgen)
#define DEFAULT_NODESQUOT
struct SolveLimits SOLVELIMITS
#define DEFAULT_MINIMPROVE
#define DEFAULT_NWAITINGNODES
#define DEFAULT_MINFIXINGRATE
#define DEFAULT_USELPROWS
#define DEFAULT_BESTSOLLIMIT
#define DEFAULT_RELAXDENSECONSS
static SCIP_Bool decompHorizonBlockUsedRecently(SCIP *scip, DECOMPHORIZON *decomphorizon, int blockpos)
#define DEFAULT_FIXCONTVARS
static void tabooListReset(TABOOLIST *taboolist)
static void freeTabooList(SCIP *scip, TABOOLIST **taboolist)
static SCIP_Bool checkFixingrate(SCIP *scip, SCIP_HEURDATA *heurdata, int nfixings)
static SCIP_RETCODE setLimits(SCIP *sourcescip, SCIP *subscip, SOLVELIMITS *solvelimits)
#define DEFAULT_POTENTIAL
static SCIP_RETCODE selectNextVariable(SCIP *scip, SCIP_HEURDATA *heurdata, ROLLINGHORIZON *rollinghorizon, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
static int countLabel(int *labels, int start, int nlabels)
static SCIP_RETCODE fixNonNeighborhoodVariables(SCIP *scip, SCIP_HEURDATA *heurdata, ROLLINGHORIZON *rollinghorizon, SCIP_SOL *sol, SCIP_VAR **vars, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *distances, int maxdistance, int *nfixings)
static SCIP_Real heurdataAvgDiscreteNeighborhoodSize(SCIP_HEURDATA *heurdata)
static SCIP_RETCODE createTabooList(SCIP *scip, TABOOLIST **taboolist, int initialsize)
static SCIP_RETCODE decompHorizonInitialize(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata)
#define DEFAULT_MAXDISTANCE
static SCIP_Bool isVariableInNeighborhood(SCIP_VAR *var, int *distances, int maxdistance)
static SCIP_Bool decompHorizonNext(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, int maxblocksize, int *blockintervalstart, int *blockintervalend, int *nextblocklabel, SCIP_Bool *fixlinkvars)
#define DEFAULT_USESELFALLBACK
static void decompHorizonSetOverlapInterval(DECOMPHORIZON *decomphorizon, int leftborder, int rightborder)
static SCIP_RETCODE setupSubScip(SCIP *scip, SCIP *subscip, SOLVELIMITS *solvelimits, SCIP_HEUR *heur)
static SCIP_Bool decompHorizonIsInitialized(DECOMPHORIZON *decomphorizon)
#define DEFAULT_ROLLHORIZONLIMFAC
static void decompHorizonFree(SCIP *scip, DECOMPHORIZON **decomphorizon)
static SCIP_RETCODE selectInitialVariableRandomly(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VGRAPH *vargraph, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
static SCIP_RETCODE determineVariableFixings(SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixings, SCIP_HEURDATA *heurdata, ROLLINGHORIZON *rollinghorizon, DECOMPHORIZON *decomphorizon, SCIP_Bool *success)
static SCIP_RETCODE rollingHorizonCreate(SCIP *scip, ROLLINGHORIZON **rollinghorizon)
struct DecompHorizon DECOMPHORIZON
static void rollingHorizonStoreDistances(ROLLINGHORIZON *rollinghorizon, int *distances)
static SCIP_RETCODE selectInitialVariableDecomposition(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_DECOMP *decomp, SCIP_VGRAPH *vargraph, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
static SCIP_Bool decompHorizonRunAgain(SCIP *scip, DECOMPHORIZON *decomphorizon)
static SCIP_RETCODE determineLimits(SCIP *scip, SCIP_HEUR *heur, SOLVELIMITS *solvelimits, SCIP_Bool *runagain)
static SCIP_RETCODE decompHorizonCreate(SCIP *scip, DECOMPHORIZON **decomphorizon, SCIP_DECOMP *decomp)
static SCIP_RETCODE determineVariableFixingsDecomp(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixings, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
static SCIP_RETCODE determineMaxDistance(SCIP *scip, SCIP_HEURDATA *heurdata, int *distances, int *choosevardistance)
static SCIP_Bool rollingHorizonRunAgain(SCIP *scip, ROLLINGHORIZON *rollinghorizon, SCIP_HEURDATA *heurdata)
static SCIP_Bool tabooListFind(TABOOLIST *taboolist, int elem)
static int decompHorizonGetFirstPosBestPotential(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, int maxblocksize)
static void updateFailureStatistic(SCIP *scip, SCIP_HEURDATA *heurdata)
#define DEFAULT_USEROLLINGHORIZON
#define DEFAULT_USEDECOMP
#define DEFAULT_CONSECUTIVEBLOCKS
static SCIP_VAR ** decomphorizonGetVars(DECOMPHORIZON *decomphorizon)
static void rollingHorizonFree(SCIP *scip, ROLLINGHORIZON **rollinghorizon)
struct TabooList TABOOLIST
static void decompHorizonMarkInterval(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, int blockstartpos, int blockendpos)
static SCIP_DECOMP * chooseDecomp(SCIP *scip)
static SCIP_Real getPotential(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, SCIP_VAR **vars, int nvars)
static int taboolistgetNElems(TABOOLIST *taboolist)
struct RollingHorizon ROLLINGHORIZON
#define DEFAULT_USEDECOMPROLLHORIZON
static int * tabooListGetLastK(TABOOLIST *taboolist, int k)
static SCIP_RETCODE tabooListAdd(SCIP *scip, TABOOLIST *taboolist, int elem)
static SCIP_Real getFixVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
LNS heuristic that tries to delimit the search region to a neighborhood in the constraint graph.
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
assert(minobj< SCIPgetCutoffbound(scip))
methods commonly used by primal heuristics
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
public methods for decompositions
public methods for primal heuristics
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for primal CIP solutions
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for decompositions
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for message handling
public methods for node selector plugins
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for random numbers
public methods for solutions
public methods for querying solving statistics
public methods for timing
SCIP_VGRAPH * variablegraph
SCIP_Longint stallnodelimit
#define SCIP_DECOMP_LINKVAR
struct SCIP_Decomp SCIP_DECOMP
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_VGraph SCIP_VGRAPH
struct SCIP_HeurData SCIP_HEURDATA
struct SCIP_Heur SCIP_HEUR
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXITSOL(x)
#define SCIP_DECL_HEUREXEC(x)
struct SCIP_HashMap SCIP_HASHMAP
#define SCIP_DECL_SORTINDCOMP(x)
struct SCIP_RandNumGen SCIP_RANDNUMGEN
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STATUS_STALLNODELIMIT
@ SCIP_VARTYPE_CONTINUOUS