LNS heuristic that tries to delimit the search region to a neighborhood in the constraint graph.
Graph Induced Neighborhood Search (GINS) is a Large Neighborhood Search Heuristic that attempts to improve an incumbent solution by fixing a suitable percentage of integer variables to the incumbent and solving the resulting, smaller and presumably easier sub-MIP.
Its search neighborhoods are based on distances in a bipartite graph \(G\) with the variables and constraints as nodes and an edge between a variable and a constraint, if the variable is part of the constraint. Given an integer \(k\), the \(k\)-neighborhood of a variable \(v\) in \(G\) is the set of variables, whose nodes are connected to \(v\) by a path not longer than \(2 \cdot k\). Intuitively, a judiciously chosen neighborhood size allows to consider a local portion of the overall problem.
An initial variable selection is made by randomly sampling different neighborhoods across the whole main problem. The neighborhood that offers the largest potential for improvement is selected to become the local search neighborhood, while all variables outside the neighborhood are fixed to their incumbent solution values.
GINS also supports a rolling horizon approach, during which several local neighborhoods are considered with increasing distance to the variable selected for the initial sub-problem. The rolling horizon approach ends if no improvement could be found or a sufficient part of the problem component variables has been part of at least one neighborhood.
Definition in file heur_gins.c.
#include <assert.h>
#include <string.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"
#include "scip/heur_gins.h"
#include "scip/pub_misc.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "gins" |
#define | HEUR_DESC "gins works on k-neighborhood in a variable-constraint graph" |
#define | HEUR_DISPCHAR 'K' |
#define | HEUR_PRIORITY -1103000 |
#define | HEUR_FREQ 20 |
#define | HEUR_FREQOFS 8 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
#define | HEUR_USESSUBSCIP TRUE |
#define | DEFAULT_NODESOFS 500 |
#define | DEFAULT_MAXNODES 5000 |
#define | DEFAULT_MINIMPROVE 0.01 |
#define | DEFAULT_MINNODES 50 |
#define | DEFAULT_MINFIXINGRATE 0.66 |
#define | DEFAULT_NODESQUOT 0.15 |
#define | DEFAULT_NWAITINGNODES 100 |
#define | DEFAULT_USELPROWS FALSE |
#define | DEFAULT_COPYCUTS TRUE |
#define | DEFAULT_BESTSOLLIMIT 3 |
#define | DEFAULT_FIXCONTVARS FALSE |
#define | DEFAULT_POTENTIAL 'r' |
#define | DEFAULT_MAXDISTANCE 3 |
#define | DEFAULT_RANDSEED 71 |
#define | DEFAULT_RELAXDENSECONSS FALSE |
#define | DEFAULT_USEROLLINGHORIZON TRUE |
#define | DEFAULT_ROLLHORIZONLIMFAC 0.4 |
Typedefs | |
typedef struct RollingHorizon | ROLLINGHORIZON |
typedef struct SolveLimits | SOLVELIMITS |
Functions | |
static SCIP_RETCODE | rollingHorizonCreate (SCIP *scip, ROLLINGHORIZON **rollinghorizon) |
static SCIP_RETCODE | rollingHorizonFree (SCIP *scip, ROLLINGHORIZON **rollinghorizon) |
static SCIP_Bool | rollingHorizonRunAgain (SCIP *scip, ROLLINGHORIZON *rollinghorizon, SCIP_HEURDATA *heurdata) |
static void | rollingHorizonStoreDistances (SCIP *scip, ROLLINGHORIZON *rollinghorizon, int *distances) |
static SCIP_Real | getPotential (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, SCIP_VAR **vars, int nvars) |
static SCIP_Bool | isVariableInNeighborhood (SCIP_VAR *var, int *distances, int maxdistance) |
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_RETCODE | determineMaxDistance (SCIP *scip, SCIP_HEURDATA *heurdata, int *distances, int *choosevardistance) |
static SCIP_Real | heurdataAvgDiscreteNeighborhoodSize (SCIP_HEURDATA *heurdata) |
static SCIP_RETCODE | selectInitialVariable (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VGRAPH *vargraph, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance) |
static SCIP_RETCODE | selectNextVariable (SCIP *scip, SCIP_HEURDATA *heurdata, ROLLINGHORIZON *rollinghorizon, 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, SCIP_Bool *success) |
static SCIP_RETCODE | createNewSol (SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success) |
static SCIP_RETCODE | setLimits (SCIP *subscip, SOLVELIMITS *solvelimits) |
static SCIP_RETCODE | setupSubScip (SCIP *scip, SCIP *subscip, SOLVELIMITS *solvelimits, SCIP_HEUR *heur) |
static SCIP_RETCODE | determineLimits (SCIP *scip, SCIP_HEUR *heur, SOLVELIMITS *solvelimits, SCIP_Bool *runagain) |
static void | updateFailureStatistic (SCIP *scip, SCIP_HEURDATA *heurdata) |
static | SCIP_DECL_HEURCOPY (heurCopyGins) |
static | SCIP_DECL_HEURFREE (heurFreeGins) |
static | SCIP_DECL_HEURINIT (heurInitGins) |
static | SCIP_DECL_HEUREXIT (heurExitGins) |
static | SCIP_DECL_HEUREXEC (heurExecGins) |
SCIP_RETCODE | SCIPincludeHeurGins (SCIP *scip) |
#define HEUR_NAME "gins" |
Definition at line 49 of file heur_gins.c.
Referenced by updateFailureStatistic().
#define HEUR_DESC "gins works on k-neighborhood in a variable-constraint graph" |
Definition at line 50 of file heur_gins.c.
#define HEUR_DISPCHAR 'K' |
Definition at line 51 of file heur_gins.c.
#define HEUR_PRIORITY -1103000 |
Definition at line 52 of file heur_gins.c.
#define HEUR_FREQ 20 |
Definition at line 53 of file heur_gins.c.
#define HEUR_FREQOFS 8 |
Definition at line 54 of file heur_gins.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 55 of file heur_gins.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 56 of file heur_gins.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 57 of file heur_gins.c.
#define DEFAULT_NODESOFS 500 |
number of nodes added to the contingent of the total nodes
Definition at line 59 of file heur_gins.c.
#define DEFAULT_MAXNODES 5000 |
maximum number of nodes to regard in the subproblem
Definition at line 60 of file heur_gins.c.
#define DEFAULT_MINIMPROVE 0.01 |
factor by which Gins should at least improve the incumbent
Definition at line 61 of file heur_gins.c.
#define DEFAULT_MINNODES 50 |
minimum number of nodes to regard in the subproblem
Definition at line 62 of file heur_gins.c.
#define DEFAULT_MINFIXINGRATE 0.66 |
minimum percentage of integer variables that have to be fixed
Definition at line 63 of file heur_gins.c.
#define DEFAULT_NODESQUOT 0.15 |
subproblem nodes in relation to nodes of the original problem
Definition at line 64 of file heur_gins.c.
#define DEFAULT_NWAITINGNODES 100 |
number of nodes without incumbent change that heuristic should wait
Definition at line 65 of file heur_gins.c.
#define DEFAULT_USELPROWS FALSE |
should subproblem be created out of the rows in the LP rows, < otherwise, the copy constructors of the constraints handlers are used
Definition at line 66 of file heur_gins.c.
#define DEFAULT_COPYCUTS TRUE |
if DEFAULT_USELPROWS is FALSE, then should all active cuts from the < cutpool of the original scip be copied to constraints of the subscip
Definition at line 69 of file heur_gins.c.
#define DEFAULT_BESTSOLLIMIT 3 |
limit on number of improving incumbent solutions in sub-CIP
Definition at line 72 of file heur_gins.c.
#define DEFAULT_FIXCONTVARS FALSE |
should continuous variables outside the neighborhoods get fixed?
Definition at line 73 of file heur_gins.c.
#define DEFAULT_POTENTIAL 'r' |
the reference point to compute the neighborhood potential: (r)oot or (p)seudo solution
Definition at line 74 of file heur_gins.c.
#define DEFAULT_MAXDISTANCE 3 |
maximum distance to selected variable to enter the subproblem, or -1 to select the distance that best approximates the minimum fixing rate from below
Definition at line 75 of file heur_gins.c.
#define DEFAULT_RANDSEED 71 |
Definition at line 78 of file heur_gins.c.
#define DEFAULT_RELAXDENSECONSS FALSE |
should dense constraints (at least as dense as 1 - minfixingrate) be ignored by connectivity graph?
Definition at line 79 of file heur_gins.c.
#define DEFAULT_USEROLLINGHORIZON TRUE |
should the heuristic solve a sequence of sub-MIP's around the first selected variable
Definition at line 82 of file heur_gins.c.
#define DEFAULT_ROLLHORIZONLIMFAC 0.4 |
limiting percentage for variables already used in sub-SCIPs to terminate rolling horizon approach
Definition at line 83 of file heur_gins.c.
typedef struct RollingHorizon ROLLINGHORIZON |
Definition at line 113 of file heur_gins.c.
typedef struct SolveLimits SOLVELIMITS |
Definition at line 165 of file heur_gins.c.
|
static |
create a rolling horizon data structure
scip | SCIP data structure |
rollinghorizon | pointer to rolling horizon data structure |
Definition at line 202 of file heur_gins.c.
|
static |
free a rolling horizon data structure
scip | SCIP data structure |
rollinghorizon | pointer to rolling horizon data structure |
Definition at line 226 of file heur_gins.c.
|
static |
is there potential to run another iteration of the rolling horizon approach?
scip | SCIP data structure |
rollinghorizon | rolling horizon data structure |
heurdata | heuristic data |
Definition at line 249 of file heur_gins.c.
References RollingHorizon::distances, RollingHorizon::nnonreachable, RollingHorizon::nused, rollingHorizonStoreDistances(), SCIPgetNBinVars(), and SCIPgetNIntVars().
Referenced by selectNextVariable().
|
static |
store the distances from the selected variable permanently for the rolling horizon approach
scip | SCIP data structure |
rollinghorizon | rolling horizon data structure |
distances | breadth-first distances indexed by Probindex of variables |
Definition at line 266 of file heur_gins.c.
References BMScopyMemoryArray, RollingHorizon::distances, RollingHorizon::distancessize, getPotential(), RollingHorizon::lastdistance, RollingHorizon::nnonreachable, and SCIP_Real.
Referenced by determineVariableFixings(), and rollingHorizonRunAgain().
|
static |
get the potential of a subset of variables (distance to a reference point such as the pseudo-solution or root LP solution)
scip | SCIP data structure |
heurdata | heuristic data |
sol | solution |
vars | variable array |
nvars | length of variable array |
Definition at line 289 of file heur_gins.c.
References RollingHorizon::distances, isVariableInNeighborhood(), REALABS, SCIP_Bool, SCIP_Real, SCIPerrorMessage, SCIPgetSolVal(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetRootSol(), and SCIPvarGetUbGlobal().
Referenced by rollingHorizonStoreDistances(), and selectInitialVariable().
|
static |
is the variable in the current neighborhood which is given by the breadth-first distances from a central variable?
var | problem variable |
distances | breadth-first distances indexed by Probindex of variables |
maxdistance | maximum distance (inclusive) to be considered for neighborhoods |
Definition at line 354 of file heur_gins.c.
References fixNonNeighborhoodVariables(), and SCIPvarGetProbindex().
Referenced by getPotential(), and selectInitialVariable().
|
static |
fixes variables in subproblem based on long breadth-first distances in variable graph
scip | SCIP data structure |
heurdata | heuristic data |
rollinghorizon | rolling horizon data structure to save relevant information, or NULL if not needed |
sol | solution in main SCIP for fixing values |
vars | variables in the main SCIP |
fixedvars | buffer to store variables that should be fixed |
fixedvals | buffer to store fixing values for fixed variables |
distances | breadth-first distances indexed by Probindex of variables |
maxdistance | maximum distance (inclusive) to be considered for neighborhoods |
nfixings | pointer to store number of fixed variables |
Definition at line 370 of file heur_gins.c.
References determineMaxDistance(), RollingHorizon::distances, RollingHorizon::lastmaxdistance, RollingHorizon::niterations, RollingHorizon::nused, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPgetVarsData(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, and RollingHorizon::used.
Referenced by determineVariableFixings(), and isVariableInNeighborhood().
|
static |
determine the maximum allowed distance to stay within the restriction to fix at least minfixingrate many non neighborhood variables
scip | SCIP data structure |
heurdata | heuristic data |
distances | breadth-first distances indexed by Probindex of variables |
choosevardistance | pointer to store the computed maximum distance |
Definition at line 443 of file heur_gins.c.
References heurdataAvgDiscreteNeighborhoodSize(), MAX, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetVarsData(), SCIPsortedvecFindInt(), and SCIPsortInt().
Referenced by fixNonNeighborhoodVariables(), selectInitialVariable(), and selectNextVariable().
|
static |
gets the average size of a discrete neighborhood over all variables tested
heurdata | heuristic data |
Definition at line 499 of file heur_gins.c.
Referenced by determineMaxDistance(), and selectInitialVariable().
|
static |
select a good starting variable at the first iteration of a rolling horizon approach
scip | SCIP data structure |
heurdata | heuristic data |
vargraph | variable graph data structure to work on |
distances | breadth-first distances indexed by Probindex of variables |
selvar | pointer to store the selected variable |
selvarmaxdistance | maximal distance k to consider for selected variable neighborhood |
Definition at line 508 of file heur_gins.c.
References determineMaxDistance(), RollingHorizon::distances, getPotential(), heurdataAvgDiscreteNeighborhoodSize(), isVariableInNeighborhood(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPallocBufferArray, SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetVarsData(), SCIPisPositive(), SCIPrandomGetInt(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvariablegraphBreadthFirst(), SCIPvarIsActive(), SCIPvarIsIntegral(), and selectNextVariable().
Referenced by determineVariableFixings().
|
static |
select the next variable using the rolling horizon
scip | SCIP data structure |
heurdata | heuristic data |
rollinghorizon | rolling horizon data structure to save relevant information, or NULL if not needed |
distances | breadth-first distances indexed by Probindex of variables |
selvar | pointer to store the selected variable |
selvarmaxdistance | maximal distance k to consider for selected variable neighborhood |
Definition at line 698 of file heur_gins.c.
References determineMaxDistance(), determineVariableFixings(), RollingHorizon::distances, RollingHorizon::lastdistance, RollingHorizon::lastmaxdistance, RollingHorizon::nused, rollingHorizonRunAgain(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetVarsData(), SCIPvarGetProbindex(), SCIPvariablegraphBreadthFirst(), TRUE, RollingHorizon::used, and RollingHorizon::variablegraph.
Referenced by determineVariableFixings(), and selectInitialVariable().
|
static |
determines the graph-induced variable fixings
scip | original SCIP data structure |
fixedvars | buffer to store variables that should be fixed |
fixedvals | buffer to store fixing values for fixed variables |
nfixings | pointer to store the number of fixed variables |
heurdata | heuristic data |
rollinghorizon | rolling horizon data structure to save relevant information, or NULL if not needed |
success | used to store whether the creation of the subproblem worked |
Definition at line 775 of file heur_gins.c.
References createNewSol(), RollingHorizon::distances, FALSE, fixNonNeighborhoodVariables(), RollingHorizon::lastmaxdistance, RollingHorizon::niterations, rollingHorizonStoreDistances(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetVarsData(), SCIPvarGetName(), SCIPvariablegraphBreadthFirst(), SCIPvariableGraphCreate(), SCIPvariableGraphFree(), selectInitialVariable(), selectNextVariable(), TRUE, and RollingHorizon::variablegraph.
Referenced by selectNextVariable().
|
static |
creates a new solution for the original problem by copying the solution of the subproblem
scip | original SCIP data structure |
subscip | SCIP structure of the subproblem |
subvars | the variables of the subproblem |
heur | gins heuristic structure |
subsol | solution of the subproblem |
success | used to store whether new solution was found or not |
Definition at line 890 of file heur_gins.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateSol(), SCIPfreeBufferArray, SCIPgetNOrigVars(), SCIPgetSolVals(), SCIPgetVarsData(), SCIPsetSolVals(), SCIPtrySolFree(), setLimits(), and TRUE.
Referenced by determineVariableFixings().
|
static |
set sub-SCIP solving limits
subscip | SCIP data structure |
solvelimits | pointer to solving limits data structure |
Definition at line 936 of file heur_gins.c.
Referenced by createNewSol(), and setupSubScip().
|
static |
set up the sub-SCIP
scip | SCIP data structure |
subscip | sub-SCIP data structure |
solvelimits | pointer to solving limits data structure |
heur | this heuristic |
Definition at line 953 of file heur_gins.c.
References determineLimits(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIPfindBranchrule(), SCIPfindConshdlr(), SCIPfindNodesel(), SCIPgetLowerbound(), SCIPgetUpperbound(), SCIPheurGetData(), SCIPisInfinity(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsumepsilon(), setLimits(), and TRUE.
|
static |
determine limits for a sub-SCIP
scip | SCIP data structure |
heur | this heuristic |
solvelimits | pointer to solving limits data structure |
runagain | can we solve another sub-SCIP with these limits |
Definition at line 1053 of file heur_gins.c.
References FALSE, SolveLimits::memorylimit, SolveLimits::nodelimit, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNNodes(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPisInfinity(), SolveLimits::timelimit, and updateFailureStatistic().
Referenced by setupSubScip().
|
static |
updates heurdata after a run of GINS
scip | original SCIP data structure |
heurdata | primal heuristic data |
Definition at line 1108 of file heur_gins.c.
References HEUR_NAME, MAX, SCIP_DECL_HEURCOPY(), SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPheurGetName(), and SCIPverbMessage().
Referenced by determineLimits().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 1155 of file heur_gins.c.
Referenced by updateFailureStatistic().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 1169 of file heur_gins.c.
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 1189 of file heur_gins.c.
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 1222 of file heur_gins.c.
|
static |
execution method of primal heuristic
Definition at line 1250 of file heur_gins.c.