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 |
#define HEUR_NAME "gins" |
Definition at line 81 of file heur_gins.c.
#define HEUR_DESC "gins works on k-neighborhood in a variable-constraint graph" |
Definition at line 82 of file heur_gins.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS |
Definition at line 83 of file heur_gins.c.
#define HEUR_PRIORITY -1103000 |
Definition at line 84 of file heur_gins.c.
#define HEUR_FREQ 20 |
Definition at line 85 of file heur_gins.c.
#define HEUR_FREQOFS 8 |
Definition at line 86 of file heur_gins.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 87 of file heur_gins.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE |
Definition at line 88 of file heur_gins.c.
#define HEUR_USESSUBSCIP TRUE |
does the heuristic use a secondary SCIP instance?
Definition at line 89 of file heur_gins.c.
#define DEFAULT_NODESOFS 500 |
number of nodes added to the contingent of the total nodes
Definition at line 91 of file heur_gins.c.
#define DEFAULT_MAXNODES 5000 |
maximum number of nodes to regard in the subproblem
Definition at line 92 of file heur_gins.c.
#define DEFAULT_MINIMPROVE 0.01 |
factor by which Gins should at least improve the incumbent
Definition at line 93 of file heur_gins.c.
#define DEFAULT_MINNODES 50 |
minimum number of nodes to regard in the subproblem
Definition at line 94 of file heur_gins.c.
#define DEFAULT_MINFIXINGRATE 0.66 |
minimum percentage of integer variables that have to be fixed
Definition at line 95 of file heur_gins.c.
#define DEFAULT_NODESQUOT 0.15 |
subproblem nodes in relation to nodes of the original problem
Definition at line 96 of file heur_gins.c.
#define DEFAULT_NWAITINGNODES 100 |
number of nodes without incumbent change that heuristic should wait
Definition at line 97 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 98 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 100 of file heur_gins.c.
#define DEFAULT_BESTSOLLIMIT 3 |
limit on number of improving incumbent solutions in sub-CIP
Definition at line 102 of file heur_gins.c.
#define DEFAULT_FIXCONTVARS FALSE |
should continuous variables outside the neighborhoods get fixed?
Definition at line 103 of file heur_gins.c.
Referenced by SCIPincludeHeurGins().
#define DEFAULT_POTENTIAL 'r' |
the reference point to compute the neighborhood potential: (r)oot, (l)ocal lp, or (p)seudo solution
Definition at line 104 of file heur_gins.c.
Referenced by SCIPincludeHeurGins().
#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 105 of file heur_gins.c.
Referenced by SCIPincludeHeurGins().
#define DEFAULT_RANDSEED 71 |
Definition at line 107 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 108 of file heur_gins.c.
Referenced by SCIPincludeHeurGins().
#define DEFAULT_USEROLLINGHORIZON TRUE |
should the heuristic solve a sequence of sub-MIP's around the first selected variable
Definition at line 110 of file heur_gins.c.
Referenced by SCIPincludeHeurGins().
#define DEFAULT_ROLLHORIZONLIMFAC 0.4 |
limiting percentage for variables already used in sub-SCIPs to terminate rolling horizon approach
Definition at line 111 of file heur_gins.c.
Referenced by SCIPincludeHeurGins().
#define DEFAULT_USEDECOMP TRUE |
should user decompositions be considered, if available?
Definition at line 113 of file heur_gins.c.
Referenced by SCIPincludeHeurGins().
#define DEFAULT_USEDECOMPROLLHORIZON FALSE |
should user decompositions be considered for initial selection in rolling horizon, if available?
Definition at line 114 of file heur_gins.c.
Referenced by SCIPincludeHeurGins().
#define DEFAULT_USESELFALLBACK TRUE |
should random initial variable selection be used if decomposition was not successful?
Definition at line 115 of file heur_gins.c.
Referenced by SCIPincludeHeurGins().
#define DEFAULT_OVERLAP 0.0 |
overlap of blocks between runs - 0.0: no overlap, 1.0: shift by only 1 block
Definition at line 116 of file heur_gins.c.
Referenced by SCIPincludeHeurGins().
#define DEFAULT_CONSECUTIVEBLOCKS TRUE |
should blocks be treated consecutively (sorted by ascending label?)
Definition at line 117 of file heur_gins.c.
Referenced by SCIPincludeHeurGins().
typedef struct RollingHorizon ROLLINGHORIZON |
Definition at line 142 of file heur_gins.c.
typedef struct DecompHorizon DECOMPHORIZON |
Definition at line 165 of file heur_gins.c.
Definition at line 176 of file heur_gins.c.
|
static |
check if enough fixings have been found
scip | SCIP data structure |
heurdata | heuristic data |
nfixings | actual number of fixings |
Definition at line 240 of file heur_gins.c.
References FALSE, heurdata, nbinvars, nintvars, nvars, SCIP_Bool, SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNVars(), and TRUE.
Referenced by determineVariableFixings(), and determineVariableFixingsDecomp().
|
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 273 of file heur_gins.c.
References assert(), heurdata, i, NULL, nvars, REALABS, SCIP_Real, SCIPerrorMessage, SCIPgetSolVal(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetRootSol(), SCIPvarGetUbGlobal(), sol, var, and vars.
Referenced by decompHorizonGetFirstPosBestPotential(), selectInitialVariableDecomposition(), and selectInitialVariableRandomly().
|
static |
(re)set overlap interval of decomposition horizon
decomphorizon | decomposition horizon data structure |
leftborder | left interval border |
rightborder | right interval border |
Definition at line 343 of file heur_gins.c.
References assert(), NULL, and DecompHorizon::overlapinterval.
Referenced by decompHorizonInitialize(), and decompHorizonMarkInterval().
|
static |
create a decomp horizon data structure
scip | SCIP data structure |
decomphorizon | pointer to store decomposition horizon |
decomp | decomposition in transformed space |
Definition at line 358 of file heur_gins.c.
References assert(), DecompHorizon::blockindices, DecompHorizon::blocklabels, DecompHorizon::decomp, 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 SCIP_DECL_HEUREXEC().
|
static |
free a decomp horizon data structure
scip | SCIP data structure |
decomphorizon | pointer to decomposition horizon that should be freed |
Definition at line 404 of file heur_gins.c.
References assert(), DecompHorizon::blockindices, DecompHorizon::blocklabels, DecompHorizon::lastsolblock, DecompHorizon::memsize, DecompHorizon::ndiscretevars, NULL, DecompHorizon::nvars, DecompHorizon::potential, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, DecompHorizon::suitable, DecompHorizon::varblockend, DecompHorizon::vars, and DecompHorizon::varsmemsize.
Referenced by SCIP_DECL_HEUREXITSOL().
|
static |
check if another run should be performed within the current decomposition horizon
scip | SCIP data structure |
decomphorizon | decomposition horizon data structure |
Definition at line 437 of file heur_gins.c.
References assert(), DecompHorizon::lastblockpos, DecompHorizon::nblocks, NULL, SCIP_Bool, and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
return TRUE if the decomposition horizon has already been initialized, FALSE otherwise
decomphorizon | decomposition horizon data structure |
Definition at line 453 of file heur_gins.c.
References assert(), DecompHorizon::init, NULL, and SCIP_Bool.
Referenced by determineVariableFixingsDecomp().
|
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 469 of file heur_gins.c.
References assert(), DecompHorizon::blocklabels, MAX, DecompHorizon::ndiscretevars, NULL, DecompHorizon::potential, SCIP_DECOMP_LINKVAR, SCIP_Real, and DecompHorizon::suitable.
|
static |
initialize decomposition horizon data structure by setting up data structures and analyzing blocks
scip | SCIP data structure |
decomphorizon | decomposition horizon data structure |
heurdata | heuristic data structure |
Definition at line 519 of file heur_gins.c.
References assert(), b, DecompHorizon::blockindices, DecompHorizon::blocklabels, DecompHorizon::decomp, decompHorizonSetOverlapInterval(), heurdata, DecompHorizon::init, DecompHorizon::nblocks, DecompHorizon::ndiscretevars, DecompHorizon::nsuitableblocks, NULL, DecompHorizon::nvars, 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, vars, and DecompHorizon::varsmemsize.
Referenced by determineVariableFixingsDecomp().
|
static |
get the first block position of the consecutive interval with the highest potential
scip | SCIP data structure |
decomphorizon | decomposition horizon data structure |
heurdata | heuristic data |
maxblocksize | maximum block size in number of variables |
Definition at line 627 of file heur_gins.c.
References assert(), b, DecompHorizon::blockindices, DecompHorizon::blocklabels, FALSE, getPotential(), heurdata, 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 decompHorizonNext().
|
static |
has this block been used too recently?
scip | SCIP data structure |
decomphorizon | decomposition horizon data structure |
blockpos | position of block |
Definition at line 766 of file heur_gins.c.
References assert(), DecompHorizon::blockindices, DecompHorizon::lastsolblock, NULL, DecompHorizon::overlapinterval, SCIP_Bool, and SCIPgetBestSol().
Referenced by decompHorizonNext().
|
static |
query the start and end of the next suitable block after the last lastblockused
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 786 of file heur_gins.c.
References assert(), DecompHorizon::blockindices, DecompHorizon::blocklabels, decompHorizonBlockUsedRecently(), decompHorizonGetFirstPosBestPotential(), FALSE, heurdata, 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 determineVariableFixingsDecomp().
|
static |
get the variables of this decomposition horizon
decomphorizon | decomposition horizon data structure |
Definition at line 886 of file heur_gins.c.
References assert(), DecompHorizon::init, NULL, and DecompHorizon::vars.
Referenced by determineVariableFixingsDecomp().
|
static |
create a rolling horizon data structure
scip | SCIP data structure |
rollinghorizon | pointer to rolling horizon data structure |
Definition at line 898 of file heur_gins.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemoryArray, SCIPgetNBinVars(), and SCIPgetNIntVars().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
reset a taboo list
taboolist | taboo list data structure |
Definition at line 923 of file heur_gins.c.
References FALSE, TabooList::needssorting, and TabooList::ntaboolabels.
Referenced by createTabooList(), and selectInitialVariableDecomposition().
|
static |
create a taboo list data structure
scip | SCIP data structure |
taboolist | pointer to store taboo list data structure |
initialsize | initial storage capacity of taboo list |
Definition at line 933 of file heur_gins.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and tabooListReset().
Referenced by selectInitialVariableDecomposition().
free a taboo list data structure
scip | SCIP data structure |
taboolist | pointer to taboo list data structure that should be freed |
Definition at line 954 of file heur_gins.c.
References assert(), NULL, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
Referenced by SCIP_DECL_HEUREXIT().
|
static |
add an element to the taboo list
scip | SCIP data structure |
taboolist | taboo list data structure |
elem | element that should be added to the taboo list |
Definition at line 972 of file heur_gins.c.
References assert(), TabooList::memsize, TabooList::needssorting, TabooList::ntaboolabels, NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPreallocBlockMemoryArray, TabooList::sortedlabels, TabooList::taboolabels, and TRUE.
Referenced by selectInitialVariableDecomposition().
find an element in the taboo list
taboolist | taboo list data structure |
elem | element that should be added to the taboo list |
Definition at line 1002 of file heur_gins.c.
References assert(), BMScopyMemoryArray, FALSE, TabooList::needssorting, TabooList::ntaboolabels, NULL, SCIP_Bool, SCIPsortedvecFindInt(), SCIPsortInt(), TabooList::sortedlabels, and TabooList::taboolabels.
Referenced by selectInitialVariableDecomposition().
|
static |
get most recent k elements from taboo list
taboolist | taboo list data structure |
k | the number of elements that should be returned |
Definition at line 1027 of file heur_gins.c.
References assert(), TabooList::ntaboolabels, NULL, and TabooList::taboolabels.
Referenced by selectInitialVariableDecomposition().
|
static |
get number of elements in taboo list
taboolist | taboo list data structure |
Definition at line 1041 of file heur_gins.c.
References TabooList::ntaboolabels.
Referenced by selectInitialVariableDecomposition().
|
static |
free a rolling horizon data structure
scip | SCIP data structure |
rollinghorizon | pointer to rolling horizon data structure |
Definition at line 1050 of file heur_gins.c.
References assert(), NULL, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPvariableGraphFree().
Referenced by SCIP_DECL_HEUREXEC().
|
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 1074 of file heur_gins.c.
References heurdata, RollingHorizon::nnonreachable, RollingHorizon::nused, SCIP_Bool, SCIPgetNBinVars(), and SCIPgetNIntVars().
Referenced by SCIP_DECL_HEUREXEC(), and selectNextVariable().
|
static |
store the distances from the selected variable permanently for the rolling horizon approach
rollinghorizon | rolling horizon data structure |
distances | breadth-first distances indexed by Probindex of variables |
Definition at line 1091 of file heur_gins.c.
References BMScopyMemoryArray, RollingHorizon::distances, RollingHorizon::distancessize, i, RollingHorizon::lastdistance, and RollingHorizon::nnonreachable.
Referenced by determineVariableFixings().
|
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 1111 of file heur_gins.c.
References assert(), NULL, SCIP_Bool, SCIPvarGetProbindex(), and var.
Referenced by selectInitialVariableRandomly().
get fixing value of variable
Definition at line 1127 of file heur_gins.c.
References assert(), SCIP_Real, SCIPgetSolVal(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), sol, and var.
Referenced by determineVariableFixingsDecomp(), and fixNonNeighborhoodVariables().
|
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 1153 of file heur_gins.c.
References getFixVal(), heurdata, i, RollingHorizon::lastmaxdistance, nbinvars, nintvars, RollingHorizon::niterations, NULL, RollingHorizon::nused, nvars, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetVarsData(), SCIPisInfinity(), sol, TRUE, RollingHorizon::used, and vars.
Referenced by determineVariableFixings().
|
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 1215 of file heur_gins.c.
References assert(), heurdata, MAX, MIN, nbinvars, nintvars, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetVarsData(), SCIPsortedvecFindInt(), and SCIPsortInt().
Referenced by selectInitialVariableDecomposition(), selectInitialVariableRandomly(), and selectNextVariable().
|
static |
gets the average size of a discrete neighborhood over all variables tested
heurdata | heuristic data |
Definition at line 1271 of file heur_gins.c.
References heurdata, MAX, and SCIP_Real.
Referenced by SCIP_DECL_HEUREXIT(), and selectInitialVariableRandomly().
|
static |
count occurrences of this label
labels | sorted array of labels |
start | start position |
nlabels | length of the labels array |
Definition at line 1280 of file heur_gins.c.
References assert(), and NULL.
Referenced by selectInitialVariableDecomposition().
|
static |
todo select initial variable based on decomposition information, if available
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 1304 of file heur_gins.c.
References assert(), countLabel(), createTabooList(), determineMaxDistance(), FALSE, getPotential(), heurdata, MAX, MIN, nbinvars, nintvars, NULL, nvars, 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(), sol, tabooListAdd(), tabooListFind(), tabooListGetLastK(), taboolistgetNElems(), tabooListReset(), TRUE, and vars.
Referenced by determineVariableFixings().
|
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 1517 of file heur_gins.c.
References assert(), determineMaxDistance(), getPotential(), heurdata, heurdataAvgDiscreteNeighborhoodSize(), isVariableInNeighborhood(), MIN, nbinvars, nintvars, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPallocBufferArray, SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetVarsData(), SCIPisPositive(), SCIPrandomGetInt(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvariablegraphBreadthFirst(), SCIPvarIsActive(), SCIPvarIsIntegral(), sol, and vars.
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 1707 of file heur_gins.c.
References assert(), determineMaxDistance(), RollingHorizon::distances, heurdata, i, RollingHorizon::lastdistance, RollingHorizon::lastmaxdistance, MIN, nbinvars, nintvars, NULL, RollingHorizon::nused, rollingHorizonRunAgain(), SCIP_CALL, SCIP_OKAY, SCIPgetVarsData(), SCIPvarGetProbindex(), SCIPvariablegraphBreadthFirst(), TRUE, RollingHorizon::used, RollingHorizon::variablegraph, and vars.
Referenced by determineVariableFixings().
|
static |
mark some of the blocks between currblockstart and currblockend as recently used, depending on overlap
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 1784 of file heur_gins.c.
References assert(), b, DecompHorizon::blockindices, DecompHorizon::blocklabels, decompHorizonSetOverlapInterval(), heurdata, DecompHorizon::lastblockpos, DecompHorizon::lastsolblock, DecompHorizon::nblocks, DecompHorizon::ndiscretevars, NULL, SCIP_Real, SCIPdebugMsg, sol, and DecompHorizon::suitable.
Referenced by determineVariableFixingsDecomp().
|
static |
determine the variable fixings based on a decomposition
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 1838 of file heur_gins.c.
References assert(), b, DecompHorizon::blockindices, DecompHorizon::blocklabels, checkFixingrate(), decomphorizonGetVars(), decompHorizonInitialize(), decompHorizonIsInitialized(), decompHorizonMarkInterval(), decompHorizonNext(), FALSE, getFixVal(), heurdata, DecompHorizon::lastblockpos, DecompHorizon::nblocks, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPdebugMsg, SCIPgetBestSol(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPisInfinity(), SCIPvarGetType(), sol, var, DecompHorizon::varblockend, and vars.
Referenced by determineVariableFixings().
|
static |
choose a decomposition from the store or return NULL if none exists/no decomposition was suitable
scip | SCIP data structure |
Definition at line 1944 of file heur_gins.c.
References FALSE, NULL, SCIPdecompGetNBlocks(), and SCIPgetDecomps().
Referenced by determineVariableFixings(), and SCIP_DECL_HEUREXEC().
|
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 |
decomphorizon | decomposition horizon data structure, or NULL |
success | used to store whether the creation of the subproblem worked |
Definition at line 1967 of file heur_gins.c.
References assert(), checkFixingrate(), chooseDecomp(), determineVariableFixingsDecomp(), FALSE, fixNonNeighborhoodVariables(), heurdata, RollingHorizon::lastmaxdistance, nbinvars, nintvars, RollingHorizon::niterations, NULL, nvars, rollingHorizonStoreDistances(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetVarsData(), SCIPvarGetName(), SCIPvariablegraphBreadthFirst(), SCIPvariableGraphCreate(), SCIPvariableGraphFree(), selectInitialVariableDecomposition(), selectInitialVariableRandomly(), selectNextVariable(), sol, TRUE, RollingHorizon::variablegraph, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
set sub-SCIP solving limits
sourcescip | SCIP data structure |
subscip | SCIP data structure |
solvelimits | pointer to solving limits data structure |
Definition at line 2105 of file heur_gins.c.
References assert(), SolveLimits::nodelimit, NULL, SCIP_CALL, SCIP_OKAY, SCIPcopyLimits(), SCIPsetLongintParam(), SCIPsetRealParam(), and SolveLimits::stallnodelimit.
Referenced by 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 2128 of file heur_gins.c.
References assert(), cutoff, FALSE, heurdata, MIN, NULL, 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 SCIP_DECL_HEUREXEC().
|
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 2217 of file heur_gins.c.
References assert(), FALSE, heurdata, MIN, SolveLimits::nodelimit, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPcheckCopyLimits(), SCIPgetNNodes(), SCIPheurGetData(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), and SolveLimits::stallnodelimit.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
updates heurdata after a run of GINS
scip | original SCIP data structure |
heurdata | primal heuristic data |
Definition at line 2268 of file heur_gins.c.
References heurdata, SCIP_LONGINT_MAX, and SCIPgetNNodes().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 2287 of file heur_gins.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurGins().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 2301 of file heur_gins.c.
References assert(), heurdata, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 2321 of file heur_gins.c.
References assert(), DEFAULT_RANDSEED, FALSE, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPheurGetData(), and TRUE.
|
static |
solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)
Definition at line 2352 of file heur_gins.c.
References assert(), decompHorizonFree(), heurdata, NULL, SCIP_OKAY, and SCIPheurGetData().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 2372 of file heur_gins.c.
References assert(), freeTabooList(), heurdata, heurdataAvgDiscreteNeighborhoodSize(), NULL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPfreeRandom(), SCIPheurGetData(), SCIPstatistic, and SCIPverbMessage().
|
static |
execution method of primal heuristic
Definition at line 2404 of file heur_gins.c.
References assert(), chooseDecomp(), decompHorizonCreate(), decompHorizonRunAgain(), determineLimits(), determineVariableFixings(), FALSE, heurdata, i, MIN, NULL, nvars, result, rollingHorizonCreate(), rollingHorizonFree(), rollingHorizonRunAgain(), SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIP_STATUS_NODELIMIT, SCIP_STATUS_STALLNODELIMIT, SCIPallocBufferArray, SCIPblkmem(), SCIPcopyLargeNeighborhoodSearch(), SCIPcreate(), SCIPdebugMsg, SCIPfree(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNNodes(), SCIPgetNSols(), SCIPgetNTotalNodes(), SCIPgetSolNodenum(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPgetVarsData(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPheurGetData(), SCIPisStopped(), SCIPmergeVariableStatistics(), SCIPsolIsOriginal(), SCIPsolve(), SCIPtranslateSubSols(), setupSubScip(), TRUE, updateFailureStatistic(), and vars.