SCIP Doxygen Documentation
Loading...
Searching...
No Matches

Detailed Description

LNS heuristic that tries to delimit the search region to a neighborhood in the constraint graph.

Author
Gregor Hendel

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

Macros

#define HEUR_NAME   "gins"
#define HEUR_DESC   "gins works on k-neighborhood in a variable-constraint graph"
#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_LNS
#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
#define DEFAULT_USEDECOMP   TRUE
#define DEFAULT_USEDECOMPROLLHORIZON   FALSE
#define DEFAULT_USESELFALLBACK   TRUE
#define DEFAULT_OVERLAP   0.0
#define DEFAULT_CONSECUTIVEBLOCKS   TRUE

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_DECOMPchooseDecomp (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.

◆ 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 100 of file heur_gins.c.

◆ DEFAULT_BESTSOLLIMIT

#define DEFAULT_BESTSOLLIMIT   3

limit on number of improving incumbent solutions in sub-CIP

Definition at line 102 of file heur_gins.c.

◆ DEFAULT_FIXCONTVARS

#define DEFAULT_FIXCONTVARS   FALSE

should continuous variables outside the neighborhoods get fixed?

Definition at line 103 of file heur_gins.c.

Referenced by SCIPincludeHeurGins().

◆ 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 104 of file heur_gins.c.

Referenced by SCIPincludeHeurGins().

◆ 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 105 of file heur_gins.c.

Referenced by SCIPincludeHeurGins().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   71

Definition at line 107 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 108 of file heur_gins.c.

Referenced by SCIPincludeHeurGins().

◆ DEFAULT_USEROLLINGHORIZON

#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().

◆ DEFAULT_ROLLHORIZONLIMFAC

#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().

◆ DEFAULT_USEDECOMP

#define DEFAULT_USEDECOMP   TRUE

should user decompositions be considered, if available?

Definition at line 113 of file heur_gins.c.

Referenced by SCIPincludeHeurGins().

◆ DEFAULT_USEDECOMPROLLHORIZON

#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().

◆ DEFAULT_USESELFALLBACK

#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().

◆ 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 116 of file heur_gins.c.

Referenced by SCIPincludeHeurGins().

◆ DEFAULT_CONSECUTIVEBLOCKS

#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 Documentation

◆ ROLLINGHORIZON

Definition at line 142 of file heur_gins.c.

◆ DECOMPHORIZON

typedef struct DecompHorizon DECOMPHORIZON

Definition at line 165 of file heur_gins.c.

◆ TABOOLIST

typedef struct TabooList TABOOLIST

Definition at line 176 of file heur_gins.c.

Function Documentation

◆ checkFixingrate()

SCIP_Bool checkFixingrate ( SCIP * scip,
SCIP_HEURDATA * heurdata,
int nfixings )
static

check if enough fixings have been found

Parameters
scipSCIP data structure
heurdataheuristic data
nfixingsactual 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().

◆ getPotential()

SCIP_Real getPotential ( SCIP * scip,
SCIP_HEURDATA * heurdata,
SCIP_SOL * sol,
SCIP_VAR ** vars,
int nvars )
static

get the potential of a subset of variables (distance to a reference point such as the pseudo-solution or root LP solution)

Parameters
scipSCIP data structure
heurdataheuristic data
solsolution
varsvariable array
nvarslength 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().

◆ decompHorizonSetOverlapInterval()

void decompHorizonSetOverlapInterval ( DECOMPHORIZON * decomphorizon,
int leftborder,
int rightborder )
static

(re)set overlap interval of decomposition horizon

Parameters
decomphorizondecomposition horizon data structure
leftborderleft interval border
rightborderright interval border

Definition at line 343 of file heur_gins.c.

References assert(), NULL, and DecompHorizon::overlapinterval.

Referenced by decompHorizonInitialize(), and decompHorizonMarkInterval().

◆ decompHorizonCreate()

◆ decompHorizonFree()

void decompHorizonFree ( SCIP * scip,
DECOMPHORIZON ** decomphorizon )
static

◆ decompHorizonRunAgain()

SCIP_Bool decompHorizonRunAgain ( SCIP * scip,
DECOMPHORIZON * decomphorizon )
static

check if another run should be performed within the current decomposition horizon

Parameters
scipSCIP data structure
decomphorizondecomposition 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().

◆ decompHorizonIsInitialized()

SCIP_Bool decompHorizonIsInitialized ( DECOMPHORIZON * decomphorizon)
static

return TRUE if the decomposition horizon has already been initialized, FALSE otherwise

Parameters
decomphorizondecomposition horizon data structure

Definition at line 453 of file heur_gins.c.

References assert(), DecompHorizon::init, NULL, and SCIP_Bool.

Referenced by determineVariableFixingsDecomp().

◆ SCIP_DECL_SORTINDCOMP()

SCIP_DECL_SORTINDCOMP ( sortIndCompDecompHorizon )
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.

◆ decompHorizonInitialize()

◆ decompHorizonGetFirstPosBestPotential()

int decompHorizonGetFirstPosBestPotential ( SCIP * scip,
DECOMPHORIZON * decomphorizon,
SCIP_HEURDATA * heurdata,
int maxblocksize )
static

get the first block position of the consecutive interval with the highest potential

Parameters
scipSCIP data structure
decomphorizondecomposition horizon data structure
heurdataheuristic data
maxblocksizemaximum 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().

◆ decompHorizonBlockUsedRecently()

SCIP_Bool decompHorizonBlockUsedRecently ( SCIP * scip,
DECOMPHORIZON * decomphorizon,
int blockpos )
static

has this block been used too recently?

Parameters
scipSCIP data structure
decomphorizondecomposition horizon data structure
blockposposition 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().

◆ decompHorizonNext()

SCIP_Bool decompHorizonNext ( SCIP * scip,
DECOMPHORIZON * decomphorizon,
SCIP_HEURDATA * heurdata,
int maxblocksize,
int * blockintervalstart,
int * blockintervalend,
int * nextblocklabel,
SCIP_Bool * fixlinkvars )
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
scipSCIP data structure
decomphorizondecomposition horizon data structure
heurdataheuristic data
maxblocksizemaximum block size in number of variables
blockintervalstartpointer to store position of first block of interval
blockintervalendpointer to store position of last block of interval
nextblocklabelpointer to store label of the next suitable block
fixlinkvarsshould 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().

◆ decomphorizonGetVars()

SCIP_VAR ** decomphorizonGetVars ( DECOMPHORIZON * decomphorizon)
static

get the variables of this decomposition horizon

Parameters
decomphorizondecomposition horizon data structure

Definition at line 886 of file heur_gins.c.

References assert(), DecompHorizon::init, NULL, and DecompHorizon::vars.

Referenced by determineVariableFixingsDecomp().

◆ rollingHorizonCreate()

SCIP_RETCODE rollingHorizonCreate ( SCIP * scip,
ROLLINGHORIZON ** rollinghorizon )
static

create a rolling horizon data structure

Parameters
scipSCIP data structure
rollinghorizonpointer 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().

◆ tabooListReset()

void tabooListReset ( TABOOLIST * taboolist)
static

reset a taboo list

Parameters
taboolisttaboo list data structure

Definition at line 923 of file heur_gins.c.

References FALSE, TabooList::needssorting, and TabooList::ntaboolabels.

Referenced by createTabooList(), and selectInitialVariableDecomposition().

◆ createTabooList()

SCIP_RETCODE createTabooList ( SCIP * scip,
TABOOLIST ** taboolist,
int initialsize )
static

create a taboo list data structure

Parameters
scipSCIP data structure
taboolistpointer to store taboo list data structure
initialsizeinitial 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().

◆ freeTabooList()

void freeTabooList ( SCIP * scip,
TABOOLIST ** taboolist )
static

free a taboo list data structure

Parameters
scipSCIP data structure
taboolistpointer 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().

◆ tabooListAdd()

SCIP_RETCODE tabooListAdd ( SCIP * scip,
TABOOLIST * taboolist,
int elem )
static

add an element to the taboo list

Parameters
scipSCIP data structure
taboolisttaboo list data structure
elemelement 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().

◆ tabooListFind()

SCIP_Bool tabooListFind ( TABOOLIST * taboolist,
int elem )
static

find an element in the taboo list

Parameters
taboolisttaboo list data structure
elemelement 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().

◆ tabooListGetLastK()

int * tabooListGetLastK ( TABOOLIST * taboolist,
int k )
static

get most recent k elements from taboo list

Parameters
taboolisttaboo list data structure
kthe 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().

◆ taboolistgetNElems()

int taboolistgetNElems ( TABOOLIST * taboolist)
static

get number of elements in taboo list

Parameters
taboolisttaboo list data structure

Definition at line 1041 of file heur_gins.c.

References TabooList::ntaboolabels.

Referenced by selectInitialVariableDecomposition().

◆ rollingHorizonFree()

void rollingHorizonFree ( SCIP * scip,
ROLLINGHORIZON ** rollinghorizon )
static

free a rolling horizon data structure

Parameters
scipSCIP data structure
rollinghorizonpointer 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().

◆ rollingHorizonRunAgain()

SCIP_Bool rollingHorizonRunAgain ( SCIP * scip,
ROLLINGHORIZON * rollinghorizon,
SCIP_HEURDATA * heurdata )
static

is there potential to run another iteration of the rolling horizon approach?

Parameters
scipSCIP data structure
rollinghorizonrolling horizon data structure
heurdataheuristic 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().

◆ rollingHorizonStoreDistances()

void rollingHorizonStoreDistances ( ROLLINGHORIZON * rollinghorizon,
int * distances )
static

store the distances from the selected variable permanently for the rolling horizon approach

Parameters
rollinghorizonrolling horizon data structure
distancesbreadth-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().

◆ isVariableInNeighborhood()

SCIP_Bool isVariableInNeighborhood ( SCIP_VAR * var,
int * distances,
int maxdistance )
static

is the variable in the current neighborhood which is given by the breadth-first distances from a central variable?

Parameters
varproblem variable
distancesbreadth-first distances indexed by Probindex of variables
maxdistancemaximum 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().

◆ getFixVal()

SCIP_Real getFixVal ( SCIP * scip,
SCIP_SOL * sol,
SCIP_VAR * var )
static

get fixing value of variable

Parameters
scipSCIP data structure
solsolution in main SCIP for fixing values
varproblem 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().

◆ fixNonNeighborhoodVariables()

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

fixes variables in subproblem based on long breadth-first distances in variable graph

Parameters
scipSCIP data structure
heurdataheuristic data
rollinghorizonrolling horizon data structure to save relevant information, or NULL if not needed
solsolution in main SCIP for fixing values
varsvariables in the main SCIP
fixedvarsbuffer to store variables that should be fixed
fixedvalsbuffer to store fixing values for fixed variables
distancesbreadth-first distances indexed by Probindex of variables
maxdistancemaximum distance (inclusive) to be considered for neighborhoods
nfixingspointer 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().

◆ determineMaxDistance()

SCIP_RETCODE determineMaxDistance ( SCIP * scip,
SCIP_HEURDATA * heurdata,
int * distances,
int * choosevardistance )
static

determine the maximum allowed distance to stay within the restriction to fix at least minfixingrate many non neighborhood variables

Parameters
scipSCIP data structure
heurdataheuristic data
distancesbreadth-first distances indexed by Probindex of variables
choosevardistancepointer 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().

◆ heurdataAvgDiscreteNeighborhoodSize()

SCIP_Real heurdataAvgDiscreteNeighborhoodSize ( SCIP_HEURDATA * heurdata)
static

gets the average size of a discrete neighborhood over all variables tested

Parameters
heurdataheuristic data

Definition at line 1271 of file heur_gins.c.

References heurdata, MAX, and SCIP_Real.

Referenced by SCIP_DECL_HEUREXIT(), and selectInitialVariableRandomly().

◆ countLabel()

int countLabel ( int * labels,
int start,
int nlabels )
static

count occurrences of this label

Parameters
labelssorted array of labels
startstart position
nlabelslength of the labels array

Definition at line 1280 of file heur_gins.c.

References assert(), and NULL.

Referenced by selectInitialVariableDecomposition().

◆ selectInitialVariableDecomposition()

SCIP_RETCODE selectInitialVariableDecomposition ( SCIP * scip,
SCIP_HEURDATA * heurdata,
SCIP_DECOMP * decomp,
SCIP_VGRAPH * vargraph,
int * distances,
SCIP_VAR ** selvar,
int * selvarmaxdistance )
static

todo select initial variable based on decomposition information, if available

Parameters
scipSCIP data structure
heurdataheuristic data
decompdecomposition data structure with variable labels
vargraphvariable graph data structure to work on
distancesbreadth-first distances indexed by Probindex of variables
selvarpointer to store the selected variable
selvarmaxdistancemaximal 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().

◆ selectInitialVariableRandomly()

SCIP_RETCODE selectInitialVariableRandomly ( SCIP * scip,
SCIP_HEURDATA * heurdata,
SCIP_VGRAPH * vargraph,
int * distances,
SCIP_VAR ** selvar,
int * selvarmaxdistance )
static

select a good starting variable at the first iteration of a rolling horizon approach

Parameters
scipSCIP data structure
heurdataheuristic data
vargraphvariable graph data structure to work on
distancesbreadth-first distances indexed by Probindex of variables
selvarpointer to store the selected variable
selvarmaxdistancemaximal 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().

◆ selectNextVariable()

SCIP_RETCODE selectNextVariable ( SCIP * scip,
SCIP_HEURDATA * heurdata,
ROLLINGHORIZON * rollinghorizon,
int * distances,
SCIP_VAR ** selvar,
int * selvarmaxdistance )
static

select the next variable using the rolling horizon

Parameters
scipSCIP data structure
heurdataheuristic data
rollinghorizonrolling horizon data structure to save relevant information, or NULL if not needed
distancesbreadth-first distances indexed by Probindex of variables
selvarpointer to store the selected variable
selvarmaxdistancemaximal 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().

◆ decompHorizonMarkInterval()

void decompHorizonMarkInterval ( SCIP * scip,
DECOMPHORIZON * decomphorizon,
SCIP_HEURDATA * heurdata,
SCIP_SOL * sol,
int blockstartpos,
int blockendpos )
static

mark some of the blocks between currblockstart and currblockend as recently used, depending on overlap

Parameters
scipSCIP data structure
decomphorizondecomposition horizon data structure
heurdataheuristic data
solsolution by which some of the blocks should be marked
blockstartposcurrent start position of interval
blockendposcurrent 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().

◆ determineVariableFixingsDecomp()

SCIP_RETCODE determineVariableFixingsDecomp ( SCIP * scip,
DECOMPHORIZON * decomphorizon,
SCIP_VAR ** fixedvars,
SCIP_Real * fixedvals,
int * nfixings,
SCIP_HEURDATA * heurdata,
SCIP_Bool * success )
static

determine the variable fixings based on a decomposition

Parameters
scipSCIP data structure
decomphorizondecomposition horizon data structure
fixedvarsbuffer to store variables that should be fixed
fixedvalsbuffer to store fixing values for fixed variables
nfixingspointer to store the number of fixed variables
heurdataheuristic data
successused 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().

◆ chooseDecomp()

SCIP_DECOMP * chooseDecomp ( SCIP * scip)
static

choose a decomposition from the store or return NULL if none exists/no decomposition was suitable

Parameters
scipSCIP data structure

Definition at line 1944 of file heur_gins.c.

References FALSE, NULL, SCIPdecompGetNBlocks(), and SCIPgetDecomps().

Referenced by determineVariableFixings(), and SCIP_DECL_HEUREXEC().

◆ determineVariableFixings()

SCIP_RETCODE determineVariableFixings ( SCIP * scip,
SCIP_VAR ** fixedvars,
SCIP_Real * fixedvals,
int * nfixings,
SCIP_HEURDATA * heurdata,
ROLLINGHORIZON * rollinghorizon,
DECOMPHORIZON * decomphorizon,
SCIP_Bool * success )
static

determines the graph-induced variable fixings

Parameters
sciporiginal SCIP data structure
fixedvarsbuffer to store variables that should be fixed
fixedvalsbuffer to store fixing values for fixed variables
nfixingspointer to store the number of fixed variables
heurdataheuristic data
rollinghorizonrolling horizon data structure to save relevant information, or NULL if not needed
decomphorizondecomposition horizon data structure, or NULL
successused 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().

◆ setLimits()

SCIP_RETCODE setLimits ( SCIP * sourcescip,
SCIP * subscip,
SOLVELIMITS * solvelimits )
static

set sub-SCIP solving limits

Parameters
sourcescipSCIP data structure
subscipSCIP data structure
solvelimitspointer 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().

◆ setupSubScip()

SCIP_RETCODE setupSubScip ( SCIP * scip,
SCIP * subscip,
SOLVELIMITS * solvelimits,
SCIP_HEUR * heur )
static

◆ determineLimits()

SCIP_RETCODE determineLimits ( SCIP * scip,
SCIP_HEUR * heur,
SOLVELIMITS * solvelimits,
SCIP_Bool * runagain )
static

determine limits for a sub-SCIP

Parameters
scipSCIP data structure
heurthis heuristic
solvelimitspointer to solving limits data structure
runagaincan 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().

◆ updateFailureStatistic()

void updateFailureStatistic ( SCIP * scip,
SCIP_HEURDATA * heurdata )
static

updates heurdata after a run of GINS

Parameters
sciporiginal SCIP data structure
heurdataprimal heuristic data

Definition at line 2268 of file heur_gins.c.

References heurdata, SCIP_LONGINT_MAX, and SCIPgetNNodes().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

SCIP_DECL_HEURCOPY ( heurCopyGins )
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().

◆ SCIP_DECL_HEURFREE()

SCIP_DECL_HEURFREE ( heurFreeGins )
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().

◆ SCIP_DECL_HEURINIT()

SCIP_DECL_HEURINIT ( heurInitGins )
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.

◆ SCIP_DECL_HEUREXITSOL()

SCIP_DECL_HEUREXITSOL ( heurExitsolGins )
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().

◆ SCIP_DECL_HEUREXIT()

SCIP_DECL_HEUREXIT ( heurExitGins )
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().

◆ SCIP_DECL_HEUREXEC()