Detailed Description
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 "blockmemshell/memory.h"
#include "scip/heur_gins.h"
#include "scip/heuristics.h"
#include "scip/pub_dcmp.h"
#include "scip/pub_heur.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_dcmp.h"
#include "scip/scip_general.h"
#include "scip/scip_heur.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nodesel.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solve.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | RollingHorizon |
struct | DecompHorizon |
struct | TabooList |
struct | SolveLimits |
Typedefs | |
typedef struct RollingHorizon | ROLLINGHORIZON |
typedef struct DecompHorizon | DECOMPHORIZON |
typedef struct TabooList | TABOOLIST |
typedef struct SolveLimits | SOLVELIMITS |
Functions | |
static SCIP_Bool | checkFixingrate (SCIP *scip, SCIP_HEURDATA *heurdata, int nfixings) |
static SCIP_Real | getPotential (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, SCIP_VAR **vars, int nvars) |
static void | decompHorizonSetOverlapInterval (DECOMPHORIZON *decomphorizon, int leftborder, int rightborder) |
static SCIP_RETCODE | decompHorizonCreate (SCIP *scip, DECOMPHORIZON **decomphorizon, SCIP_DECOMP *decomp) |
static void | decompHorizonFree (SCIP *scip, DECOMPHORIZON **decomphorizon) |
static SCIP_Bool | decompHorizonRunAgain (SCIP *scip, DECOMPHORIZON *decomphorizon) |
static SCIP_Bool | decompHorizonIsInitialized (DECOMPHORIZON *decomphorizon) |
static | SCIP_DECL_SORTINDCOMP (sortIndCompDecompHorizon) |
static SCIP_RETCODE | decompHorizonInitialize (SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata) |
static int | decompHorizonGetFirstPosBestPotential (SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, int maxblocksize) |
static SCIP_Bool | decompHorizonBlockUsedRecently (SCIP *scip, DECOMPHORIZON *decomphorizon, int blockpos) |
static SCIP_Bool | decompHorizonNext (SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, int maxblocksize, int *blockintervalstart, int *blockintervalend, int *nextblocklabel, SCIP_Bool *fixlinkvars) |
static SCIP_VAR ** | decomphorizonGetVars (DECOMPHORIZON *decomphorizon) |
static SCIP_RETCODE | rollingHorizonCreate (SCIP *scip, ROLLINGHORIZON **rollinghorizon) |
static void | tabooListReset (TABOOLIST *taboolist) |
static SCIP_RETCODE | createTabooList (SCIP *scip, TABOOLIST **taboolist, int initialsize) |
static void | freeTabooList (SCIP *scip, TABOOLIST **taboolist) |
static SCIP_RETCODE | tabooListAdd (SCIP *scip, TABOOLIST *taboolist, int elem) |
static SCIP_Bool | tabooListFind (TABOOLIST *taboolist, int elem) |
static int * | tabooListGetLastK (TABOOLIST *taboolist, int k) |
static int | taboolistgetNElems (TABOOLIST *taboolist) |
static void | rollingHorizonFree (SCIP *scip, ROLLINGHORIZON **rollinghorizon) |
static SCIP_Bool | rollingHorizonRunAgain (SCIP *scip, ROLLINGHORIZON *rollinghorizon, SCIP_HEURDATA *heurdata) |
static void | rollingHorizonStoreDistances (ROLLINGHORIZON *rollinghorizon, int *distances) |
static SCIP_Bool | isVariableInNeighborhood (SCIP_VAR *var, int *distances, int maxdistance) |
static SCIP_Real | getFixVal (SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var) |
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 int | countLabel (int *labels, int start, int nlabels) |
static SCIP_RETCODE | selectInitialVariableDecomposition (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_DECOMP *decomp, SCIP_VGRAPH *vargraph, int *distances, SCIP_VAR **selvar, int *selvarmaxdistance) |
static SCIP_RETCODE | selectInitialVariableRandomly (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 void | decompHorizonMarkInterval (SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_HEURDATA *heurdata, SCIP_SOL *sol, int blockstartpos, int blockendpos) |
static SCIP_RETCODE | determineVariableFixingsDecomp (SCIP *scip, DECOMPHORIZON *decomphorizon, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int *nfixings, SCIP_HEURDATA *heurdata, SCIP_Bool *success) |
static SCIP_DECOMP * | chooseDecomp (SCIP *scip) |
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 | setLimits (SCIP *sourcescip, 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_HEUREXITSOL (heurExitsolGins) |
static | SCIP_DECL_HEUREXIT (heurExitGins) |
static | SCIP_DECL_HEUREXEC (heurExecGins) |
SCIP_RETCODE | SCIPincludeHeurGins (SCIP *scip) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "gins" |
Definition at line 81 of file heur_gins.c.
Referenced by updateFailureStatistic().
◆ HEUR_DESC
#define HEUR_DESC "gins works on k-neighborhood in a variable-constraint graph" |
Definition at line 82 of file heur_gins.c.
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 83 of file heur_gins.c.
◆ HEUR_PRIORITY
#define HEUR_PRIORITY -1103000 |
Definition at line 84 of file heur_gins.c.
◆ HEUR_FREQ
#define HEUR_FREQ 20 |
Definition at line 85 of file heur_gins.c.
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 8 |
Definition at line 86 of file heur_gins.c.
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 87 of file heur_gins.c.
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 88 of file heur_gins.c.
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 89 of file heur_gins.c.
◆ DEFAULT_NODESOFS
#define DEFAULT_NODESOFS 500 |
number of nodes added to the contingent of the total nodes
Definition at line 91 of file heur_gins.c.
◆ DEFAULT_MAXNODES
#define DEFAULT_MAXNODES 5000 |
maximum number of nodes to regard in the subproblem
Definition at line 92 of file heur_gins.c.
◆ DEFAULT_MINIMPROVE
#define DEFAULT_MINIMPROVE 0.01 |
factor by which Gins should at least improve the incumbent
Definition at line 93 of file heur_gins.c.
◆ DEFAULT_MINNODES
#define DEFAULT_MINNODES 50 |
minimum number of nodes to regard in the subproblem
Definition at line 94 of file heur_gins.c.
◆ DEFAULT_MINFIXINGRATE
#define DEFAULT_MINFIXINGRATE 0.66 |
minimum percentage of integer variables that have to be fixed
Definition at line 95 of file heur_gins.c.
◆ DEFAULT_NODESQUOT
#define DEFAULT_NODESQUOT 0.15 |
subproblem nodes in relation to nodes of the original problem
Definition at line 96 of file heur_gins.c.
◆ DEFAULT_NWAITINGNODES
#define DEFAULT_NWAITINGNODES 100 |
number of nodes without incumbent change that heuristic should wait
Definition at line 97 of file heur_gins.c.
◆ DEFAULT_USELPROWS
#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 98 of file heur_gins.c.
◆ DEFAULT_COPYCUTS
#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 101 of file heur_gins.c.
◆ DEFAULT_BESTSOLLIMIT
#define DEFAULT_BESTSOLLIMIT 3 |
limit on number of improving incumbent solutions in sub-CIP
Definition at line 104 of file heur_gins.c.
◆ DEFAULT_FIXCONTVARS
#define DEFAULT_FIXCONTVARS FALSE |
should continuous variables outside the neighborhoods get fixed?
Definition at line 105 of file heur_gins.c.
◆ DEFAULT_POTENTIAL
#define DEFAULT_POTENTIAL 'r' |
the reference point to compute the neighborhood potential: (r)oot, (l)ocal lp, or (p)seudo solution
Definition at line 106 of file heur_gins.c.
◆ DEFAULT_MAXDISTANCE
#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 107 of file heur_gins.c.
◆ DEFAULT_RANDSEED
#define DEFAULT_RANDSEED 71 |
Definition at line 110 of file heur_gins.c.
◆ DEFAULT_RELAXDENSECONSS
#define DEFAULT_RELAXDENSECONSS FALSE |
should dense constraints (at least as dense as 1 - minfixingrate) be ignored by connectivity graph?
Definition at line 111 of file heur_gins.c.
◆ DEFAULT_USEROLLINGHORIZON
#define DEFAULT_USEROLLINGHORIZON TRUE |
should the heuristic solve a sequence of sub-MIP's around the first selected variable
Definition at line 114 of file heur_gins.c.
◆ DEFAULT_ROLLHORIZONLIMFAC
#define DEFAULT_ROLLHORIZONLIMFAC 0.4 |
limiting percentage for variables already used in sub-SCIPs to terminate rolling horizon approach
Definition at line 115 of file heur_gins.c.
◆ DEFAULT_USEDECOMP
#define DEFAULT_USEDECOMP TRUE |
should user decompositions be considered, if available?
Definition at line 118 of file heur_gins.c.
◆ DEFAULT_USEDECOMPROLLHORIZON
#define DEFAULT_USEDECOMPROLLHORIZON FALSE |
should user decompositions be considered for initial selection in rolling horizon, if available?
Definition at line 119 of file heur_gins.c.
◆ DEFAULT_USESELFALLBACK
#define DEFAULT_USESELFALLBACK TRUE |
should random initial variable selection be used if decomposition was not successful?
Definition at line 120 of file heur_gins.c.
◆ DEFAULT_OVERLAP
#define DEFAULT_OVERLAP 0.0 |
overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block
Definition at line 121 of file heur_gins.c.
◆ DEFAULT_CONSECUTIVEBLOCKS
#define DEFAULT_CONSECUTIVEBLOCKS TRUE |
should blocks be treated consecutively (sorted by ascending label?)
Definition at line 122 of file heur_gins.c.
Typedef Documentation
◆ ROLLINGHORIZON
typedef struct RollingHorizon ROLLINGHORIZON |
Definition at line 147 of file heur_gins.c.
◆ DECOMPHORIZON
typedef struct DecompHorizon DECOMPHORIZON |
Definition at line 170 of file heur_gins.c.
◆ TABOOLIST
Definition at line 181 of file heur_gins.c.
◆ SOLVELIMITS
typedef struct SolveLimits SOLVELIMITS |
Definition at line 237 of file heur_gins.c.
Function Documentation
◆ checkFixingrate()
|
static |
check if enough fixings have been found
- Parameters
-
scip SCIP data structure heurdata heuristic data nfixings actual number of fixings
Definition at line 245 of file heur_gins.c.
References FALSE, getPotential(), SCIP_Real, SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNVars(), and TRUE.
Referenced by determineVariableFixings(), and determineVariableFixingsDecomp().
◆ getPotential()
|
static |
get the potential of a subset of variables (distance to a reference point such as the pseudo-solution or root LP solution)
- Parameters
-
scip SCIP data structure heurdata heuristic data sol solution vars variable array nvars length of variable array
Definition at line 278 of file heur_gins.c.
References decompHorizonSetOverlapInterval(), NULL, REALABS, SCIP_Real, SCIPerrorMessage, SCIPgetSolVal(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetRootSol(), and SCIPvarGetUbGlobal().
Referenced by checkFixingrate(), decompHorizonGetFirstPosBestPotential(), selectInitialVariableDecomposition(), and selectInitialVariableRandomly().
◆ decompHorizonSetOverlapInterval()
|
static |
(re)set overlap interval of decomposition horizon
- Parameters
-
decomphorizon decomposition horizon data structure leftborder left interval border rightborder right interval border
Definition at line 348 of file heur_gins.c.
References decompHorizonCreate(), NULL, and DecompHorizon::overlapinterval.
Referenced by decompHorizonInitialize(), decompHorizonMarkInterval(), and getPotential().
◆ decompHorizonCreate()
|
static |
create a decomp horizon data structure
- Parameters
-
scip SCIP data structure decomphorizon pointer to store decomposition horizon decomp decomposition in transformed space
Definition at line 363 of file heur_gins.c.
References DecompHorizon::blockindices, DecompHorizon::blocklabels, DecompHorizon::decomp, decompHorizonFree(), FALSE, DecompHorizon::init, DecompHorizon::lastblockpos, DecompHorizon::lastsolblock, DecompHorizon::memsize, DecompHorizon::ndiscretevars, NULL, DecompHorizon::nvars, DecompHorizon::potential, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemoryArray, SCIPdecompGetNBlocks(), DecompHorizon::suitable, DecompHorizon::varblockend, DecompHorizon::vars, and DecompHorizon::varsmemsize.
Referenced by decompHorizonSetOverlapInterval().
◆ decompHorizonFree()
|
static |
free a decomp horizon data structure
- Parameters
-
scip SCIP data structure decomphorizon pointer to decomposition horizon that should be freed
Definition at line 409 of file heur_gins.c.
Referenced by decompHorizonCreate().
◆ decompHorizonRunAgain()
|
static |
check if another run should be performed within the current decomposition horizon
- Parameters
-
scip SCIP data structure decomphorizon decomposition horizon data structure
Definition at line 442 of file heur_gins.c.
◆ decompHorizonIsInitialized()
|
static |
return TRUE if the decomposition horizon has already been initialized, FALSE otherwise
- Parameters
-
decomphorizon decomposition horizon data structure
Definition at line 458 of file heur_gins.c.
References SCIP_Real.
Referenced by determineVariableFixingsDecomp().
◆ SCIP_DECL_SORTINDCOMP()
|
static |
compares two block indices result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value
0: ind2 comes after (is worse than) ind2
Definition at line 474 of file heur_gins.c.
◆ decompHorizonInitialize()
|
static |
initialize decomposition horizon data structure by setting up data structures and analyzing blocks
- Parameters
-
scip SCIP data structure decomphorizon decomposition horizon data structure heurdata heuristic data structure
Definition at line 524 of file heur_gins.c.
References b, DecompHorizon::blockindices, DecompHorizon::blocklabels, DecompHorizon::decomp, decompHorizonGetFirstPosBestPotential(), decompHorizonSetOverlapInterval(), DecompHorizon::init, DecompHorizon::nblocks, DecompHorizon::ndiscretevars, DecompHorizon::nsuitableblocks, NULL, DecompHorizon::nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_IMPLINT, SCIPallocBufferArray, SCIPdebugMsg, SCIPdecompGetVarsLabels(), SCIPdecompIsOriginal(), SCIPduplicateBlockMemoryArray, SCIPfreeBufferArray, SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNVars(), SCIPgetVars(), SCIPsortIntPtr(), SCIPvarGetType(), DecompHorizon::suitable, TRUE, DecompHorizon::varblockend, DecompHorizon::vars, and DecompHorizon::varsmemsize.
Referenced by determineVariableFixingsDecomp().
◆ decompHorizonGetFirstPosBestPotential()
|
static |
get the first block position of the consecutive interval with the highest potential
- Parameters
-
scip SCIP data structure decomphorizon decomposition horizon data structure heurdata heuristic data maxblocksize maximum block size in number of variables
Definition at line 632 of file heur_gins.c.
References b, DecompHorizon::blockindices, DecompHorizon::blocklabels, decompHorizonBlockUsedRecently(), FALSE, getPotential(), DecompHorizon::nblocks, DecompHorizon::ndiscretevars, NULL, DecompHorizon::nvars, DecompHorizon::potential, SCIP_Bool, SCIP_DECOMP_LINKVAR, SCIP_Real, SCIP_REAL_MIN, SCIPdebugMsg, SCIPgetBestSol(), SCIPsortInd(), DecompHorizon::suitable, TRUE, DecompHorizon::varblockend, and DecompHorizon::vars.
Referenced by decompHorizonInitialize(), and decompHorizonNext().
◆ decompHorizonBlockUsedRecently()
|
static |
has this block been used too recently?
- Parameters
-
scip SCIP data structure decomphorizon decomposition horizon data structure blockpos position of block
Definition at line 771 of file heur_gins.c.
References DecompHorizon::blockindices, decompHorizonNext(), DecompHorizon::lastsolblock, NULL, DecompHorizon::overlapinterval, SCIP_Bool, and SCIPgetBestSol().
Referenced by decompHorizonGetFirstPosBestPotential(), and decompHorizonNext().
◆ decompHorizonNext()
|
static |
query the start and end of the next suitable block after the last lastblockused
- Returns
- TRUE if next suitable block could be found, otherwise FALSE
- Parameters
-
scip SCIP data structure decomphorizon decomposition horizon data structure heurdata heuristic data maxblocksize maximum block size in number of variables blockintervalstart pointer to store position of first block of interval blockintervalend pointer to store position of last block of interval nextblocklabel pointer to store label of the next suitable block fixlinkvars should the linking variables be fixed, as well?
Definition at line 791 of file heur_gins.c.
References DecompHorizon::blockindices, DecompHorizon::blocklabels, decompHorizonBlockUsedRecently(), decompHorizonGetFirstPosBestPotential(), decomphorizonGetVars(), FALSE, DecompHorizon::init, DecompHorizon::lastblockpos, DecompHorizon::lastsolblock, DecompHorizon::nblocks, DecompHorizon::ndiscretevars, DecompHorizon::nsuitableblocks, NULL, SCIP_Bool, SCIP_DECOMP_LINKVAR, SCIPgetBestSol(), DecompHorizon::suitable, and TRUE.
Referenced by decompHorizonBlockUsedRecently(), and determineVariableFixingsDecomp().
◆ decomphorizonGetVars()
|
static |
get the variables of this decomposition horizon
- Parameters
-
decomphorizon decomposition horizon data structure
Definition at line 891 of file heur_gins.c.
Referenced by decompHorizonNext(), and determineVariableFixingsDecomp().
◆ rollingHorizonCreate()
|
static |
create a rolling horizon data structure
- Parameters
-
scip SCIP data structure rollinghorizon pointer to rolling horizon data structure
Definition at line 903 of file heur_gins.c.
◆ tabooListReset()
|
static |
reset a taboo list
- Parameters
-
taboolist taboo list data structure
Definition at line 928 of file heur_gins.c.
Referenced by createTabooList(), and selectInitialVariableDecomposition().
◆ createTabooList()
|
static |
create a taboo list data structure
- Parameters
-
scip SCIP data structure taboolist pointer to store taboo list data structure initialsize initial storage capacity of taboo list
Definition at line 938 of file heur_gins.c.
References freeTabooList(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and tabooListReset().
Referenced by selectInitialVariableDecomposition().
◆ freeTabooList()
free a taboo list data structure
- Parameters
-
scip SCIP data structure taboolist pointer to taboo list data structure that should be freed
Definition at line 959 of file heur_gins.c.
Referenced by createTabooList().
◆ tabooListAdd()
|
static |
add an element to the taboo list
- Parameters
-
scip SCIP data structure taboolist taboo list data structure elem element that should be added to the taboo list
Definition at line 977 of file heur_gins.c.
References TabooList::memsize, TabooList::needssorting, TabooList::ntaboolabels, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPreallocBlockMemoryArray, TabooList::sortedlabels, TabooList::taboolabels, tabooListFind(), and TRUE.
Referenced by selectInitialVariableDecomposition().
◆ tabooListFind()
find an element in the taboo list
- Parameters
-
taboolist taboo list data structure elem element that should be added to the taboo list
Definition at line 1007 of file heur_gins.c.
Referenced by selectInitialVariableDecomposition(), and tabooListAdd().
◆ tabooListGetLastK()
|
static |
get most recent k elements from taboo list
- Parameters
-
taboolist taboo list data structure k the number of elements that should be returned
Definition at line 1032 of file heur_gins.c.
Referenced by selectInitialVariableDecomposition().
◆ taboolistgetNElems()
|
static |
get number of elements in taboo list
- Parameters
-
taboolist taboo list data structure
Definition at line 1046 of file heur_gins.c.
Referenced by selectInitialVariableDecomposition().
◆ rollingHorizonFree()
|
static |
free a rolling horizon data structure
- Parameters
-
scip SCIP data structure rollinghorizon pointer to rolling horizon data structure
Definition at line 1055 of file heur_gins.c.
◆ rollingHorizonRunAgain()
|
static |
is there potential to run another iteration of the rolling horizon approach?
- Parameters
-
scip SCIP data structure rollinghorizon rolling horizon data structure heurdata heuristic data
Definition at line 1079 of file heur_gins.c.
References RollingHorizon::distances, RollingHorizon::nnonreachable, RollingHorizon::nused, rollingHorizonStoreDistances(), SCIPgetNBinVars(), and SCIPgetNIntVars().
Referenced by selectNextVariable().
◆ rollingHorizonStoreDistances()
|
static |
store the distances from the selected variable permanently for the rolling horizon approach
- Parameters
-
rollinghorizon rolling horizon data structure distances breadth-first distances indexed by Probindex of variables
Definition at line 1096 of file heur_gins.c.
Referenced by determineVariableFixings(), and rollingHorizonRunAgain().
◆ isVariableInNeighborhood()
|
static |
is the variable in the current neighborhood which is given by the breadth-first distances from a central variable?
- Parameters
-
var problem variable distances breadth-first distances indexed by Probindex of variables maxdistance maximum distance (inclusive) to be considered for neighborhoods
Definition at line 1116 of file heur_gins.c.
References getFixVal(), NULL, SCIP_Real, and SCIPvarGetProbindex().
Referenced by selectInitialVariableRandomly().
◆ getFixVal()
get fixing value of variable
- Parameters
-
scip SCIP data structure sol solution in main SCIP for fixing values var problem variable
Definition at line 1132 of file heur_gins.c.
References fixNonNeighborhoodVariables(), SCIP_Real, SCIPgetSolVal(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by determineVariableFixingsDecomp(), fixNonNeighborhoodVariables(), and isVariableInNeighborhood().
◆ fixNonNeighborhoodVariables()
|
static |
fixes variables in subproblem based on long breadth-first distances in variable graph
- Parameters
-
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 1158 of file heur_gins.c.
References determineMaxDistance(), getFixVal(), RollingHorizon::lastmaxdistance, RollingHorizon::niterations, NULL, RollingHorizon::nused, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetVarsData(), SCIPisInfinity(), TRUE, and RollingHorizon::used.
Referenced by determineVariableFixings(), and getFixVal().
◆ determineMaxDistance()
|
static |
determine the maximum allowed distance to stay within the restriction to fix at least minfixingrate many non neighborhood variables
- Parameters
-
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 1220 of file heur_gins.c.
References heurdataAvgDiscreteNeighborhoodSize(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetVarsData(), SCIPsortedvecFindInt(), and SCIPsortInt().
Referenced by fixNonNeighborhoodVariables(), selectInitialVariableDecomposition(), selectInitialVariableRandomly(), and selectNextVariable().
◆ heurdataAvgDiscreteNeighborhoodSize()
|
static |
gets the average size of a discrete neighborhood over all variables tested
- Parameters
-
heurdata heuristic data
Definition at line 1276 of file heur_gins.c.
Referenced by determineMaxDistance(), and selectInitialVariableRandomly().
◆ countLabel()
|
static |
count occurrences of this label
- Parameters
-
labels sorted array of labels start start position nlabels length of the labels array
Definition at line 1285 of file heur_gins.c.
References NULL, and selectInitialVariableDecomposition().
Referenced by selectInitialVariableDecomposition().
◆ selectInitialVariableDecomposition()
|
static |
todo select initial variable based on decomposition information, if available
- Parameters
-
scip SCIP data structure heurdata heuristic data decomp decomposition data structure with variable labels 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 1309 of file heur_gins.c.
References countLabel(), createTabooList(), determineMaxDistance(), RollingHorizon::distances, FALSE, getPotential(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPdebugMsg, SCIPdecompGetNBlocks(), SCIPdecompGetVarsLabels(), SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetVarsData(), SCIPrandomGetInt(), SCIPsolGetIndex(), SCIPsortIntPtr(), SCIPvarGetName(), SCIPvarGetType(), SCIPvariablegraphBreadthFirst(), selectInitialVariableRandomly(), tabooListAdd(), tabooListFind(), tabooListGetLastK(), taboolistgetNElems(), tabooListReset(), and TRUE.
Referenced by countLabel(), and determineVariableFixings().
◆ selectInitialVariableRandomly()
|
static |
select a good starting variable at the first iteration of a rolling horizon approach
- Parameters
-
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 1522 of file heur_gins.c.
References determineMaxDistance(), RollingHorizon::distances, getPotential(), heurdataAvgDiscreteNeighborhoodSize(), isVariableInNeighborhood(), NULL, 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(), and selectInitialVariableDecomposition().
◆ selectNextVariable()
|
static |
select the next variable using the rolling horizon
- Parameters
-
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 1712 of file heur_gins.c.
References decompHorizonMarkInterval(), determineMaxDistance(), RollingHorizon::distances, RollingHorizon::lastdistance, RollingHorizon::lastmaxdistance, NULL, RollingHorizon::nused, rollingHorizonRunAgain(), SCIP_CALL, SCIP_OKAY, SCIPgetVarsData(), SCIPvarGetProbindex(), SCIPvariablegraphBreadthFirst(), TRUE, RollingHorizon::used, and RollingHorizon::variablegraph.
Referenced by determineVariableFixings(), and selectInitialVariableRandomly().
◆ decompHorizonMarkInterval()
|
static |
mark some of the blocks between currblockstart and currblockend as recently used, depending on overlap
- Parameters
-
scip SCIP data structure decomphorizon decomposition horizon data structure heurdata heuristic data sol solution by which some of the blocks should be marked blockstartpos current start position of interval blockendpos current end position (inclusive) of interval
Definition at line 1789 of file heur_gins.c.
References b, DecompHorizon::blockindices, DecompHorizon::blocklabels, decompHorizonSetOverlapInterval(), determineVariableFixingsDecomp(), DecompHorizon::lastblockpos, DecompHorizon::lastsolblock, DecompHorizon::nblocks, DecompHorizon::ndiscretevars, NULL, SCIP_Real, SCIPdebugMsg, and DecompHorizon::suitable.
Referenced by determineVariableFixingsDecomp(), and selectNextVariable().
◆ determineVariableFixingsDecomp()
|
static |
determine the variable fixings based on a decomposition
- Parameters
-
scip SCIP data structure decomphorizon decomposition horizon 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 success used to store whether the creation of the subproblem worked
Definition at line 1843 of file heur_gins.c.
References b, DecompHorizon::blockindices, DecompHorizon::blocklabels, checkFixingrate(), chooseDecomp(), decomphorizonGetVars(), decompHorizonInitialize(), decompHorizonIsInitialized(), decompHorizonMarkInterval(), decompHorizonNext(), FALSE, getFixVal(), DecompHorizon::lastblockpos, DecompHorizon::nblocks, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPdebugMsg, SCIPgetBestSol(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPisInfinity(), SCIPvarGetType(), and DecompHorizon::varblockend.
Referenced by decompHorizonMarkInterval(), and determineVariableFixings().
◆ chooseDecomp()
|
static |
choose a decomposition from the store or return NULL if none exists/no decomposition was suitable
- Parameters
-
scip SCIP data structure
Definition at line 1949 of file heur_gins.c.
Referenced by determineVariableFixings(), and determineVariableFixingsDecomp().
◆ determineVariableFixings()
|
static |
determines the graph-induced variable fixings
- Parameters
-
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 decomphorizon decomposition horizon data structure, or NULL success used to store whether the creation of the subproblem worked
Definition at line 1972 of file heur_gins.c.
References checkFixingrate(), chooseDecomp(), determineVariableFixingsDecomp(), RollingHorizon::distances, FALSE, fixNonNeighborhoodVariables(), RollingHorizon::lastmaxdistance, RollingHorizon::niterations, NULL, rollingHorizonStoreDistances(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetVarsData(), SCIPvarGetName(), SCIPvariablegraphBreadthFirst(), SCIPvariableGraphCreate(), SCIPvariableGraphFree(), selectInitialVariableDecomposition(), selectInitialVariableRandomly(), selectNextVariable(), setLimits(), TRUE, and RollingHorizon::variablegraph.
◆ setLimits()
|
static |
set sub-SCIP solving limits
- Parameters
-
sourcescip SCIP data structure subscip SCIP data structure solvelimits pointer to solving limits data structure
Definition at line 2110 of file heur_gins.c.
References SolveLimits::nodelimit, NULL, SCIP_CALL, SCIP_OKAY, SCIPcopyLimits(), SCIPsetLongintParam(), SCIPsetRealParam(), setupSubScip(), and SolveLimits::stallnodelimit.
Referenced by determineVariableFixings(), and setupSubScip().
◆ setupSubScip()
|
static |
set up the sub-SCIP
- Parameters
-
scip SCIP data structure subscip sub-SCIP data structure solvelimits pointer to solving limits data structure heur this heuristic
Definition at line 2133 of file heur_gins.c.
References determineLimits(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PARAMSETTING_FAST, SCIP_PARAMSETTING_OFF, SCIP_Real, SCIPfindBranchrule(), SCIPfindNodesel(), SCIPgetLowerbound(), SCIPgetUpperbound(), SCIPheurGetData(), SCIPisInfinity(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetCharParam(), SCIPsetIntParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsumepsilon(), setLimits(), and TRUE.
Referenced by setLimits().
◆ determineLimits()
|
static |
determine limits for a sub-SCIP
- Parameters
-
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 2222 of file heur_gins.c.
References FALSE, SolveLimits::nodelimit, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPcheckCopyLimits(), SCIPgetNNodes(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SolveLimits::stallnodelimit, and updateFailureStatistic().
Referenced by setupSubScip().
◆ updateFailureStatistic()
|
static |
updates heurdata after a run of GINS
- Parameters
-
scip original SCIP data structure heurdata primal heuristic data
Definition at line 2273 of file heur_gins.c.
References HEUR_NAME, NULL, and SCIPheurGetName().
Referenced by determineLimits().
◆ SCIP_DECL_HEURCOPY()
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 2292 of file heur_gins.c.
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 2306 of file heur_gins.c.
◆ SCIP_DECL_HEURINIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 2326 of file heur_gins.c.
◆ SCIP_DECL_HEUREXITSOL()
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 2357 of file heur_gins.c.
◆ SCIP_DECL_HEUREXIT()
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 2377 of file heur_gins.c.
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 2409 of file heur_gins.c.