heur_gins.c
Go to the documentation of this file.
27 * @brief LNS heuristic that tries to delimit the search region to a neighborhood in the constraint graph
30 * Graph Induced Neighborhood Search (GINS) is a Large Neighborhood Search Heuristic that attempts to improve
31 * an incumbent solution by fixing a suitable percentage of integer variables to the incumbent and
34 * Its search neighborhoods are based on distances in a bipartite graph \f$G\f$ with the variables and constraints as nodes
36 * Given an integer \f$k\f$, the \f$k\f$-neighborhood of a variable \f$v\f$ in \f$G\f$ is the set of variables, whose nodes
37 * are connected to \f$v\f$ by a path not longer than \f$2 \cdot k\f$. Intuitively, a judiciously chosen neighborhood size
40 * An initial variable selection is made by randomly sampling different neighborhoods across the whole main problem.
41 * The neighborhood that offers the largest potential for improvement is selected to become the local search neighborhood,
44 * GINS also supports a rolling horizon approach, during which several local neighborhoods are considered
45 * with increasing distance to the variable selected for the initial sub-problem. The rolling horizon approach ends
46 * if no improvement could be found or a sufficient part of the problem component variables has been part of
50/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
93#define DEFAULT_MINIMPROVE 0.01 /**< factor by which Gins should at least improve the incumbent */
95#define DEFAULT_MINFIXINGRATE 0.66 /**< minimum percentage of integer variables that have to be fixed */
96#define DEFAULT_NODESQUOT 0.15 /**< subproblem nodes in relation to nodes of the original problem */
97#define DEFAULT_NWAITINGNODES 100 /**< number of nodes without incumbent change that heuristic should wait */
100#define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the
102#define DEFAULT_BESTSOLLIMIT 3 /**< limit on number of improving incumbent solutions in sub-CIP */
103#define DEFAULT_FIXCONTVARS FALSE /**< should continuous variables outside the neighborhoods get fixed? */
104#define DEFAULT_POTENTIAL 'r' /**< the reference point to compute the neighborhood potential: (r)oot, (l)ocal lp, or (p)seudo solution */
105#define DEFAULT_MAXDISTANCE 3 /**< maximum distance to selected variable to enter the subproblem, or -1 to
108#define DEFAULT_RELAXDENSECONSS FALSE /**< should dense constraints (at least as dense as 1 - minfixingrate) be
110#define DEFAULT_USEROLLINGHORIZON TRUE /**< should the heuristic solve a sequence of sub-MIP's around the first selected variable */
111#define DEFAULT_ROLLHORIZONLIMFAC 0.4 /**< limiting percentage for variables already used in sub-SCIPs to terminate rolling
114#define DEFAULT_USEDECOMPROLLHORIZON FALSE /**< should user decompositions be considered for initial selection in rolling horizon, if available? */
115#define DEFAULT_USESELFALLBACK TRUE /**< should random initial variable selection be used if decomposition was not successful? */
116#define DEFAULT_OVERLAP 0.0 /**< overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block */
117#define DEFAULT_CONSECUTIVEBLOCKS TRUE /**< should blocks be treated consecutively (sorted by ascending label?) */
124/** rolling horizon data structure to control multiple LNS heuristic runs away from an original source variable */
127 SCIP_VGRAPH* variablegraph; /**< variable graph data structure for breadth-first-search neighborhoods */
151 int* blocklabels; /**< sorted block labels of all variable blocks that satisfy the requirements */
152 int* varblockend; /**< block end indices in sorted variables array (position of first variable of next block) */
155 int* nvars; /**< number of variables (including continuous and implicit integers) in each block */
158 int lastblockpos; /**< last remembered block position (in block indices, i.e., regarding sorting) */
159 int nblocks; /**< the number of available variable blocks, only available after initialization */
185 SCIP_Real overlap; /**< overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block */
190 SCIP_Real rollhorizonlimfac; /**< limiting percentage for variables already used in sub-SCIPs to terminate
199 SCIP_Bool allblocksunsuitable; /**< remember if all blocks are unsuitable w.r.t. the current incumbent solution */
205 int sumdiscneighborhoodvars; /**< neighborhood discrete variables sum over all seen neighboorhoods */
209 SCIP_Bool consecutiveblocks; /**< should blocks be treated consecutively (sorted by ascending label?) */
210 SCIP_Bool relaxdenseconss; /**< should dense constraints (at least as dense as 1 - minfixingrate) be
212 SCIP_Bool userollinghorizon; /**< should the heuristic solve a sequence of sub-MIP's around the first
215 SCIP_Bool usedecomprollhorizon;/**< should user decompositions be considered for initial selection in rolling horizon, if available? */
216 SCIP_Bool useselfallback; /**< should random initial variable selection be used if decomposition was not successful? */
222 SCIP_Longint nextnodenumber; /**< the next node number at which the heuristic should be called again */
223 SCIP_Longint targetnodes; /**< number of target nodes, slightly increasing if (stall) node limit is hit */
230 SCIP_Longint stallnodelimit; /**< limit on the number of stall nodes (nodes after last incumbent) */
250 fixthreshold = (int)(heurdata->minfixingrate * (heurdata->fixcontvars ? nvars : (nbinvars + nintvars)));
252 /* compare actual number of fixings to limit; if we fixed not enough variables we terminate here;
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);
269/** get the potential of a subset of variables (distance to a reference point such as the pseudo-solution or root
392 decomphorizonptr->lastblockpos = INT_MIN; /* cannot use -1 because this is defined for linking variables */
504 potentialbysize1 = decomphorizon->potential[ind1] / (SCIP_Real)(MAX(decomphorizon->ndiscretevars[ind1], 1.0));
505 potentialbysize2 = decomphorizon->potential[ind2] / (SCIP_Real)(MAX(decomphorizon->ndiscretevars[ind2], 1.0));
517/** initialize decomposition horizon data structure by setting up data structures and analyzing blocks */
590 suitable = nfixedvars > heurdata->minfixingrate * (heurdata->fixcontvars ? nvars : nvars - ncontvarsscip);
671 SCIPsortInd(decomphorizon->blockindices, sortIndCompDecompHorizon, (void*)decomphorizon, decomphorizon->nblocks);
673 /* best potential block is now at the front (actual block position is retrieved from blockindices */
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]]);
725 if( ! withlinkvars && linkvarsexist && decomphorizon->ndiscretevars[0] + decomphorizon->ndiscretevars[blockindb1] < maxblocksize )
731 else if( withlinkvars && decomphorizon->ndiscretevars[0] + decomphorizon->ndiscretevars[blockindb1] >= maxblocksize )
743 if( ! decomphorizon->suitable[blockindb2] || nintervalvars + decomphorizon->ndiscretevars[blockindb2] >= maxblocksize )
758 SCIPdebugMsg(scip, "Potential based selection chooses interval starting from block %d with potential %.1g\n",
777 return (decomphorizon->lastsolblock[decomphorizon->blockindices[blockpos]] == SCIPgetBestSol(scip) ||
778 (decomphorizon->overlapinterval[0] <= blockpos && blockpos <= decomphorizon->overlapinterval[1]));
814 /* get the last block position that was used by the heuristic. Search for it, and continue with the next block. */
823 firstpos = decompHorizonGetFirstPosBestPotential(scip, decomphorizon, heurdata, maxblocksize) - 1;
829 (! decomphorizon->suitable[decomphorizon->blockindices[pos]] || decomphorizon->blocklabels[decomphorizon->blockindices[pos]] == SCIP_DECOMP_LINKVAR ||
837 (! decomphorizon->suitable[decomphorizon->blockindices[pos]] || decomphorizon->blocklabels[decomphorizon->blockindices[pos]] == SCIP_DECOMP_LINKVAR ||
842 assert(pos == firstpos || (0 <= pos && decomphorizon->nblocks > pos && (decomphorizon->suitable[decomphorizon->blockindices[pos]] || pos == 0)));
846 if( pos != firstpos && decomphorizon->suitable[decomphorizon->blockindices[pos]] && !decompHorizonBlockUsedRecently(scip, decomphorizon, pos) )
865 while( ++pos < decomphorizon->nblocks && decomphorizon->suitable[decomphorizon->blockindices[pos]] && ndiscretevars + decomphorizon->ndiscretevars[decomphorizon->blockindices[pos]] < maxblocksize )
986 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &taboolist->taboolabels, taboolist->memsize, newsize) );
987 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &taboolist->sortedlabels, taboolist->memsize, newsize) );
1067 SCIPfreeBlockMemoryArray(scip, &(*rollinghorizon)->distances, (*rollinghorizon)->distancessize);
1080 int maxnused = (int)(heurdata->rollhorizonlimfac * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip)
1083 /* run again if a certain percentage of the reachable variables (in the same connected component)
1089/** store the distances from the selected variable permanently for the rolling horizon approach */
1109/** is the variable in the current neighborhood which is given by the breadth-first distances from a central variable? */
1122 return (distances[SCIPvarGetProbindex(var)] != -1 && distances[SCIPvarGetProbindex(var)] <= maxdistance);
1142 /* due to dual reductions, it may happen that the solution value is not in the variable's domain anymore */
1156 ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
1211/** determine the maximum allowed distance to stay within the restriction to fix at least minfixingrate many non
1234 /* copy the relevant distances of either the discrete or all problem variables and sort them */
1238 /* distances can be infinite in the case of multiple connected components; therefore, search for the index of the
1239 * zero entry, which is the unique representative of the chosen variable in the sorted distances
1247 /* determine the critical index to look for an appropriate neighborhood distance, starting from the zero position */
1251 /* determine the maximum breadth-first distance such that the neighborhood size stays small enough (below 1-minfixingrate)*/
1254 /* we set the distance to exactly the distance at the critical index. If the distance at critical index is not the
1255 * last one before the distance increases, we decrease the choosevardistance such that the entire neighborhood
1258 if( criticalidx != nrelevantdistances - 1 && distancescopy[criticalidx + 1] == *choosevardistance )
1262 heurdata->maxseendistance = MAX(heurdata->maxseendistance, distancescopy[nrelevantdistances - 1]);
1311 int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */
1340 /* create a taboo list for recently used block labels at the first initial variable selection */
1358 /* keep the last 3 blocks except for border cases of very coarse decomposition, or too few taboo elements */
1398 SCIPdebugMsg(scip, "Skip initial variable selection because all blocks are unsuitable for solution %d\n",
1449 if( SCIPvarGetType(varscopy[v]) == SCIP_VARTYPE_BINARY || SCIPvarGetType(varscopy[v]) == SCIP_VARTYPE_INTEGER )
1456 potential = getPotential(scip, heurdata, sol, &(varscopy[currblockstart]), currblockend - currblockstart);
1478 SCIPdebugMsg(scip, "Select initial variable <%s> from block <%d>\n", SCIPvarGetName(*selvar), varlabels[bestvaridx]);
1487 /* use the variable constraint graph to compute distances to all other variables, and store the selvarmaxdistance */
1495 /* maximum distance is 0, i.e., even the size of the 1-neighborhood of this variable exceeds the fixing rate */
1523 int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */
1558 /* maximum distance from selected variable for breadth-first search (if set to -1, we compute an exhaustive breadth-first
1577 searchlimit = heurdata->nneighborhoods < 10 ? 5 : (int)(nintegralvarsleft / heurdataAvgDiscreteNeighborhoodSize(heurdata));
1580 /* multi variable potential: choose different disjoint neighborhoods, compare their potential */
1619 SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, &choosevar, 1, distances, maxdistance, INT_MAX, INT_MAX) );
1621 /* use either automatic or user-defined max-distance for neighborhood in variable constraint graph */
1651 /* check if neighborhood contains too many integer variables in order to satisfy the minimum fixing rate */
1671 /* sort neighborhood variables to the end so that this neighborhood is not considered in further samples */
1710 ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
1713 int* selvarmaxdistance /**< maximal distance k to consider for selected variable neighborhood */
1757 SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, rollinghorizon->variablegraph, selvar, 1, distances, *selvarmaxdistance, INT_MAX, INT_MAX) );
1769 while( rollingHorizonRunAgain(scip, rollinghorizon, heurdata) && (*selvar == NULL || *selvarmaxdistance == 0) );
1782/** mark some of the blocks between currblockstart and currblockend as recently used, depending on overlap */
1803 * we mark all blocks of the current interval; we hence avoid to rerun on a subset of the current subproblem
1804 * in the next iteration; we achieve this by setting the overlap to 0.0, (its complement to 1.0)
1807 if( blockendpos == decomphorizon->nblocks - 1 || ! decomphorizon->suitable[decomphorizon->blockindices[blockendpos + 1]] )
1822 nvarsstartofinterval += decomphorizon->ndiscretevars[decomphorizon->blockindices[solstamppos]];
1867 maxblocksize = (int)((1.0 - heurdata->minfixingrate) * (SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip))) - 1;
1890 SCIPdebugMsg(scip, "Fix %s variables (%scluding linking variables) except blocks %d (label %d) -- %d (label %d)\n",
1898 /* iterate over the two blocks left and right of the selected consecutive interval and fix all variables
1900 * 0, ... b, ... ,[currblockstart, ..., currblockend], currblockend + 1, ..., decomphorizon->nblocks - 1
1904 /* iterate over all blocks and fix those outside of the blocks interval that defines the current subproblem */
1942/** choose a decomposition from the store or return NULL if none exists/no decomposition was suitable */
1952 /* TODO coming soon: better selection than last nontrivial decomposition that has been input */
1973 ROLLINGHORIZON* rollinghorizon, /**< rolling horizon data structure to save relevant information, or NULL if not needed */
2002 SCIP_CALL( determineVariableFixingsDecomp(scip, decomphorizon, fixedvars, fixedvals, nfixings, heurdata, success) );
2018 SCIP_CALL( SCIPvariableGraphCreate(scip, &rollinghorizon->variablegraph, heurdata->relaxdenseconss, 1.0 - heurdata->minfixingrate, &heurdata->nrelaxedconstraints) );
2029 SCIP_CALL( SCIPvariableGraphCreate(scip, &vargraph, heurdata->relaxdenseconss, 1.0 - heurdata->minfixingrate, &heurdata->nrelaxedconstraints) );
2056 /* use random variable selection as fallback strategy, if no user decomposition is available, or the
2061 SCIP_CALL( selectInitialVariableRandomly(scip, heurdata, vargraph, distances, &selvar, &selvarmaxdistance) );
2068 SCIP_CALL( SCIPvariablegraphBreadthFirst(scip, vargraph, &selvar, 1, distances, INT_MAX, INT_MAX, INT_MAX) );
2076 SCIP_CALL( selectNextVariable(scip, heurdata, rollinghorizon, distances, &selvar, &selvarmaxdistance) );
2090 SCIP_CALL( fixNonNeighborhoodVariables(scip, heurdata, rollinghorizon, sol, vars, fixedvars, fixedvals, distances,
2162 if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
2168 if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
2173 /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
2249 maxnnodesr *= 1.0 + confidence * 2.0 * (SCIPheurGetNBestSolsFound(heur)+1.0)/(heurdata->nsubmips + 1.0);
2273 /* increase number of failures, calculate next node at which GINS should be called and update actual solutions */
2350/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2363 /* it is likely that the decomposition information changes between runs, we recreate the decomposition horizon */
2384 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Avg Neighborhood size: %.1f Avg. discrete neighboorhood vars: %.1f\n",
2386 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Gins: Max seen distance %d\n", heurdata->maxseendistance);
2413 DECOMPHORIZON* decomphorizon; /* data structure for processing multiple blocks of a decomposition */
2439 /* in case of many unsuccessful calls, the nextnodenumber is increased to prevent us from running too often */
2449 if( SCIPgetNNodes(scip) - SCIPgetSolNodenum(scip,SCIPgetBestSol(scip)) < heurdata->nwaitingnodes )
2494 SCIP_CALL( determineVariableFixings(scip, fixedvars, fixedvals, &nfixedvars, heurdata, rollinghorizon, decomphorizon, &success) );
2518 SCIP_CALL( SCIPcopyLargeNeighborhoodSearch(scip, subscip, varmapfw, "gins", fixedvars, fixedvals, nfixedvars,
2534 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
2538 SCIPdebugMsg(scip, "GINS subscip stats: %.2f sec., %" SCIP_LONGINT_FORMAT " nodes, status:%d\n",
2541 /* increase target nodes if a (stall) node limit was reached; this will immediately affect the next run */
2542 if( SCIPgetStatus(subscip) == SCIP_STATUS_NODELIMIT || SCIPgetStatus(subscip) == SCIP_STATUS_STALLNODELIMIT )
2549 SCIPdebugMsg(scip, "New target nodes after stalling: %" SCIP_LONGINT_FORMAT "\n", heurdata->targetnodes);
2559 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
2660 &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, SCIPsumepsilon(scip), 1.0-SCIPsumepsilon(scip), NULL, NULL) );
2671 "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
2688 "the reference point to compute the neighborhood potential: (r)oot, (l)ocal lp, or (p)seudo solution",
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",
2712 "should user decompositions be considered for initial selection in rolling horizon, if available?",
SCIP_RETCODE SCIPtranslateSubSols(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_Bool *success, int *solindex)
Definition: scip_copy.c:1448
SCIP_RETCODE SCIPcheckCopyLimits(SCIP *sourcescip, SCIP_Bool *success)
Definition: scip_copy.c:3253
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition: scip_copy.c:1265
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3296
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:263
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:149
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition: scip_prob.c:1422
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
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)
Definition: scip_param.c:167
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)
Definition: scip_param.c:83
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
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)
Definition: scip_param.c:139
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:904
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:953
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:661
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)
Definition: scip_param.c:57
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:979
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:242
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
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)
Definition: scip_heur.c:117
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition: heur.c:1599
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:234
SCIP_Longint SCIPgetSolNodenum(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1513
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
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)
Definition: heuristics.c:951
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
void SCIPvariableGraphFree(SCIP *scip, SCIP_VGRAPH **vargraph)
Definition: heur.c:2035
SCIP_RETCODE SCIPvariablegraphBreadthFirst(SCIP *scip, SCIP_VGRAPH *vargraph, SCIP_VAR **startvars, int nstartvars, int *distances, int maxdistance, int maxvars, int maxbinintvars)
Definition: heur.c:1690
SCIP_RETCODE SCIPvariableGraphCreate(SCIP *scip, SCIP_VGRAPH **vargraph, SCIP_Bool relaxdenseconss, SCIP_Real relaxdensity, int *nrelaxedconstraints)
Definition: heur.c:1997
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:79
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10108
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:56
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)
static SCIP_Bool decompHorizonBlockUsedRecently(SCIP *scip, DECOMPHORIZON *decomphorizon, int blockpos)
Definition: heur_gins.c:766
static void freeTabooList(SCIP *scip, TABOOLIST **taboolist)
Definition: heur_gins.c:954
static SCIP_Bool checkFixingrate(SCIP *scip, SCIP_HEURDATA *heurdata, int nfixings)
Definition: heur_gins.c:240
static SCIP_RETCODE setLimits(SCIP *sourcescip, SCIP *subscip, SOLVELIMITS *solvelimits)
Definition: heur_gins.c:2105
static SCIP_RETCODE selectNextVariable(SCIP *scip, SCIP_HEURDATA *heurdata, ROLLINGHORIZON *rollinghorizon, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
Definition: heur_gins.c:1707
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)
Definition: heur_gins.c:1153
static SCIP_Real heurdataAvgDiscreteNeighborhoodSize(SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:1271
static SCIP_RETCODE createTabooList(SCIP *scip, TABOOLIST **taboolist, int initialsize)
Definition: heur_gins.c:933
static SCIP_RETCODE decompHorizonInitialize(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:519
static SCIP_Bool isVariableInNeighborhood(SCIP_VAR *var, int *distances, int maxdistance)
Definition: heur_gins.c:1111
static SCIP_Bool decompHorizonNext(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, int maxblocksize, int *blockintervalstart, int *blockintervalend, int *nextblocklabel, SCIP_Bool *fixlinkvars)
Definition: heur_gins.c:786
static void decompHorizonSetOverlapInterval(DECOMPHORIZON *decomphorizon, int leftborder, int rightborder)
Definition: heur_gins.c:343
static SCIP_RETCODE setupSubScip(SCIP *scip, SCIP *subscip, SOLVELIMITS *solvelimits, SCIP_HEUR *heur)
Definition: heur_gins.c:2128
static SCIP_Bool decompHorizonIsInitialized(DECOMPHORIZON *decomphorizon)
Definition: heur_gins.c:453
static void decompHorizonFree(SCIP *scip, DECOMPHORIZON **decomphorizon)
Definition: heur_gins.c:404
static SCIP_RETCODE selectInitialVariableRandomly(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VGRAPH *vargraph, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
Definition: heur_gins.c:1517
static SCIP_RETCODE determineVariableFixings(SCIP *scip, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixings, SCIP_HEURDATA *heurdata, ROLLINGHORIZON *rollinghorizon, DECOMPHORIZON *decomphorizon, SCIP_Bool *success)
Definition: heur_gins.c:1967
static SCIP_RETCODE rollingHorizonCreate(SCIP *scip, ROLLINGHORIZON **rollinghorizon)
Definition: heur_gins.c:898
static void rollingHorizonStoreDistances(ROLLINGHORIZON *rollinghorizon, int *distances)
Definition: heur_gins.c:1091
static SCIP_RETCODE selectInitialVariableDecomposition(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_DECOMP *decomp, SCIP_VGRAPH *vargraph, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance)
Definition: heur_gins.c:1304
static SCIP_Bool decompHorizonRunAgain(SCIP *scip, DECOMPHORIZON *decomphorizon)
Definition: heur_gins.c:437
static SCIP_RETCODE determineLimits(SCIP *scip, SCIP_HEUR *heur, SOLVELIMITS *solvelimits, SCIP_Bool *runagain)
Definition: heur_gins.c:2217
static SCIP_RETCODE decompHorizonCreate(SCIP *scip, DECOMPHORIZON **decomphorizon, SCIP_DECOMP *decomp)
Definition: heur_gins.c:358
static SCIP_RETCODE determineVariableFixingsDecomp(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixings, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
Definition: heur_gins.c:1838
static SCIP_RETCODE determineMaxDistance(SCIP *scip, SCIP_HEURDATA *heurdata, int *distances, int *choosevardistance)
Definition: heur_gins.c:1215
static SCIP_Bool rollingHorizonRunAgain(SCIP *scip, ROLLINGHORIZON *rollinghorizon, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:1074
static SCIP_Bool tabooListFind(TABOOLIST *taboolist, int elem)
Definition: heur_gins.c:1002
static SCIP_DECL_SORTINDCOMP(sortIndCompDecompHorizon)
Definition: heur_gins.c:469
static int decompHorizonGetFirstPosBestPotential(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, int maxblocksize)
Definition: heur_gins.c:627
static void updateFailureStatistic(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_gins.c:2268
static SCIP_VAR ** decomphorizonGetVars(DECOMPHORIZON *decomphorizon)
Definition: heur_gins.c:886
static void rollingHorizonFree(SCIP *scip, ROLLINGHORIZON **rollinghorizon)
Definition: heur_gins.c:1050
static void decompHorizonMarkInterval(SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, int blockstartpos, int blockendpos)
Definition: heur_gins.c:1784
static SCIP_Real getPotential(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, SCIP_VAR **vars, int nvars)
Definition: heur_gins.c:273
static int * tabooListGetLastK(TABOOLIST *taboolist, int k)
Definition: heur_gins.c:1027
static SCIP_RETCODE tabooListAdd(SCIP *scip, TABOOLIST *taboolist, int elem)
Definition: heur_gins.c:972
static SCIP_Real getFixVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: heur_gins.c:1127
LNS heuristic that tries to delimit the search region to a neighborhood in the constraint graph.
methods commonly used by primal heuristics
memory allocation routines
Definition: objbenders.h:44
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
general public methods
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 solving methods
public methods for querying solving statistics
public methods for timing
Definition: heur_gins.c:146
Definition: heur_gins.c:126
Definition: struct_dcmp.h:45
Definition: struct_misc.h:138
Definition: struct_heur.h:98
Definition: struct_misc.h:269
Definition: struct_sol.h:74
Definition: struct_heur.h:134
Definition: struct_var.h:208
Definition: struct_scip.h:70
Definition: heur_alns.c:492
Definition: heur_gins.c:169