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

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.

◆ 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 99 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 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.

◆ 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.

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

◆ 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 109 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 110 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 112 of file heur_gins.c.

◆ DEFAULT_USEDECOMP

#define DEFAULT_USEDECOMP TRUE

should user decompositions be considered, if available?

Definition at line 113 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 114 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 115 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 116 of file heur_gins.c.

◆ DEFAULT_CONSECUTIVEBLOCKS

#define DEFAULT_CONSECUTIVEBLOCKS TRUE

should blocks be treated consecutively (sorted by ascending label?)

Definition at line 117 of file heur_gins.c.

Typedef Documentation

◆ ROLLINGHORIZON

typedef struct RollingHorizon 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.

◆ SOLVELIMITS

typedef struct SolveLimits SOLVELIMITS

Definition at line 232 of file heur_gins.c.

Function Documentation

◆ checkFixingrate()

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

static

check if enough fixings have been found

Parameters

scip	SCIP data structure
heurdata	heuristic data
nfixings	actual number of fixings

Definition at line 240 of file heur_gins.c.

References FALSE, SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNVars(), and TRUE.

Referenced by determineVariableFixings(), and determineVariableFixingsDecomp().

◆ getPotential()

static 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

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 NULL, REALABS, SCIP_Real, SCIPerrorMessage, SCIPgetSolVal(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetRootSol(), and SCIPvarGetUbGlobal().

Referenced by decompHorizonGetFirstPosBestPotential(), selectInitialVariableDecomposition(), and selectInitialVariableRandomly().

◆ decompHorizonSetOverlapInterval()

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

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

References NULL, and DecompHorizon::overlapinterval.

Referenced by decompHorizonInitialize(), and decompHorizonMarkInterval().

◆ decompHorizonCreate()

static SCIP_RETCODE decompHorizonCreate	(	SCIP *	scip,
		DECOMPHORIZON **	decomphorizon,
		SCIP_DECOMP *	decomp
	)

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

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

◆ decompHorizonFree()

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

static

free a decomp horizon data structure

Parameters

scip	SCIP data structure
decomphorizon	pointer to decomposition horizon that should be freed

Definition at line 404 of file heur_gins.c.

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

◆ decompHorizonRunAgain()

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

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

References DecompHorizon::lastblockpos, DecompHorizon::nblocks, NULL, and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ decompHorizonIsInitialized()

static SCIP_Bool decompHorizonIsInitialized ( DECOMPHORIZON * decomphorizon )

static

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

Parameters

decomphorizon decomposition horizon data structure

Definition at line 453 of file heur_gins.c.

References DecompHorizon::init, and NULL.

Referenced by determineVariableFixingsDecomp().

◆ SCIP_DECL_SORTINDCOMP()

static 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 DecompHorizon::blocklabels, MAX, DecompHorizon::ndiscretevars, NULL, DecompHorizon::potential, SCIP_DECOMP_LINKVAR, SCIP_Real, and DecompHorizon::suitable.

◆ decompHorizonInitialize()

static SCIP_RETCODE decompHorizonInitialize	(	SCIP *	scip,
		DECOMPHORIZON *	decomphorizon,
		SCIP_HEURDATA *	heurdata
	)

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

References b, DecompHorizon::blockindices, DecompHorizon::blocklabels, DecompHorizon::decomp, 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 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

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 b, DecompHorizon::blockindices, DecompHorizon::blocklabels, 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 decompHorizonNext().

◆ decompHorizonBlockUsedRecently()

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

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

References DecompHorizon::blockindices, DecompHorizon::lastsolblock, NULL, DecompHorizon::overlapinterval, and SCIPgetBestSol().

Referenced by decompHorizonNext().

◆ decompHorizonNext()

static 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

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 DecompHorizon::blockindices, DecompHorizon::blocklabels, decompHorizonBlockUsedRecently(), decompHorizonGetFirstPosBestPotential(), 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 determineVariableFixingsDecomp().

◆ decomphorizonGetVars()

static SCIP_VAR ** decomphorizonGetVars ( DECOMPHORIZON * decomphorizon )

static

get the variables of this decomposition horizon

Parameters

decomphorizon decomposition horizon data structure

Definition at line 886 of file heur_gins.c.

References DecompHorizon::init, NULL, and DecompHorizon::vars.

Referenced by determineVariableFixingsDecomp().

◆ rollingHorizonCreate()

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

static

create a rolling horizon data structure

Parameters

scip	SCIP data structure
rollinghorizon	pointer to rolling horizon data structure

Definition at line 898 of file heur_gins.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemoryArray, SCIPgetNBinVars(), and SCIPgetNIntVars().

Referenced by SCIP_DECL_HEUREXEC().

◆ tabooListReset()

static void tabooListReset ( TABOOLIST * taboolist )

static

reset a taboo list

Parameters

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

◆ createTabooList()

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

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

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and tabooListReset().

Referenced by selectInitialVariableDecomposition().

◆ freeTabooList()

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

static

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

References NULL, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

Referenced by SCIP_DECL_HEUREXIT().

◆ tabooListAdd()

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

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

References TabooList::memsize, TabooList::needssorting, TabooList::ntaboolabels, NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPreallocBlockMemoryArray, TabooList::sortedlabels, TabooList::taboolabels, and TRUE.

Referenced by selectInitialVariableDecomposition().

◆ tabooListFind()

static SCIP_Bool tabooListFind	(	TABOOLIST *	taboolist,
		int	elem
	)

static

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

References BMScopyMemoryArray, FALSE, TabooList::needssorting, TabooList::ntaboolabels, NULL, SCIP_Bool, SCIPsortedvecFindInt(), SCIPsortInt(), TabooList::sortedlabels, and TabooList::taboolabels.

Referenced by selectInitialVariableDecomposition().

◆ tabooListGetLastK()

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

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

References TabooList::ntaboolabels, NULL, and TabooList::taboolabels.

Referenced by selectInitialVariableDecomposition().

◆ taboolistgetNElems()

static int taboolistgetNElems ( TABOOLIST * taboolist )

static

get number of elements in taboo list

Parameters

taboolist taboo list data structure

Definition at line 1041 of file heur_gins.c.

References TabooList::ntaboolabels.

Referenced by selectInitialVariableDecomposition().

◆ rollingHorizonFree()

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

static

free a rolling horizon data structure

Parameters

scip	SCIP data structure
rollinghorizon	pointer to rolling horizon data structure

Definition at line 1050 of file heur_gins.c.

References NULL, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPvariableGraphFree().

Referenced by SCIP_DECL_HEUREXEC().

◆ rollingHorizonRunAgain()

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

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

References RollingHorizon::nnonreachable, RollingHorizon::nused, SCIPgetNBinVars(), and SCIPgetNIntVars().

Referenced by SCIP_DECL_HEUREXEC(), and selectNextVariable().

◆ rollingHorizonStoreDistances()

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

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

References BMScopyMemoryArray, RollingHorizon::distances, RollingHorizon::distancessize, RollingHorizon::lastdistance, and RollingHorizon::nnonreachable.

Referenced by determineVariableFixings().

◆ isVariableInNeighborhood()

static 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

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 NULL, and SCIPvarGetProbindex().

Referenced by selectInitialVariableRandomly().

◆ getFixVal()

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

static

get fixing value of variable

Parameters

scip	SCIP data structure
sol	solution in main SCIP for fixing values
var	problem variable

Definition at line 1127 of file heur_gins.c.

References SCIP_Real, SCIPgetSolVal(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by determineVariableFixingsDecomp(), and fixNonNeighborhoodVariables().

◆ fixNonNeighborhoodVariables()

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

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

References getFixVal(), RollingHorizon::lastmaxdistance, RollingHorizon::niterations, NULL, RollingHorizon::nused, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetVarsData(), SCIPisInfinity(), TRUE, and RollingHorizon::used.

Referenced by determineVariableFixings().

◆ determineMaxDistance()

static 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

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 MAX, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetVarsData(), SCIPsortedvecFindInt(), and SCIPsortInt().

Referenced by selectInitialVariableDecomposition(), selectInitialVariableRandomly(), and selectNextVariable().

◆ heurdataAvgDiscreteNeighborhoodSize()

static SCIP_Real heurdataAvgDiscreteNeighborhoodSize ( SCIP_HEURDATA * heurdata )

static

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

Parameters

heurdata heuristic data

Definition at line 1271 of file heur_gins.c.

References MAX, and SCIP_Real.

Referenced by SCIP_DECL_HEUREXIT(), and selectInitialVariableRandomly().

◆ countLabel()

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

static

count occurrences of this label

Parameters

labels	sorted array of labels
start	start position
nlabels	length of the labels array

Definition at line 1280 of file heur_gins.c.

References NULL.

Referenced by selectInitialVariableDecomposition().

◆ selectInitialVariableDecomposition()

static 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

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 countLabel(), createTabooList(), determineMaxDistance(), FALSE, getPotential(), MAX, MIN, 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(), tabooListAdd(), tabooListFind(), tabooListGetLastK(), taboolistgetNElems(), tabooListReset(), and TRUE.

Referenced by determineVariableFixings().

◆ selectInitialVariableRandomly()

static 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

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 determineMaxDistance(), getPotential(), heurdataAvgDiscreteNeighborhoodSize(), isVariableInNeighborhood(), MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPallocBufferArray, SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetVarsData(), SCIPisPositive(), SCIPrandomGetInt(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvariablegraphBreadthFirst(), SCIPvarIsActive(), and SCIPvarIsIntegral().

Referenced by determineVariableFixings().

◆ selectNextVariable()

static 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

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 determineMaxDistance(), RollingHorizon::distances, RollingHorizon::lastdistance, RollingHorizon::lastmaxdistance, MIN, NULL, RollingHorizon::nused, rollingHorizonRunAgain(), SCIP_CALL, SCIP_OKAY, SCIPgetVarsData(), SCIPvarGetProbindex(), SCIPvariablegraphBreadthFirst(), TRUE, RollingHorizon::used, and RollingHorizon::variablegraph.

Referenced by determineVariableFixings().

◆ decompHorizonMarkInterval()

static 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

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 b, DecompHorizon::blockindices, DecompHorizon::blocklabels, decompHorizonSetOverlapInterval(), DecompHorizon::lastblockpos, DecompHorizon::lastsolblock, DecompHorizon::nblocks, DecompHorizon::ndiscretevars, NULL, SCIP_Real, SCIPdebugMsg, and DecompHorizon::suitable.

Referenced by determineVariableFixingsDecomp().

◆ determineVariableFixingsDecomp()

static 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

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 b, DecompHorizon::blockindices, DecompHorizon::blocklabels, checkFixingrate(), 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 determineVariableFixings().

◆ chooseDecomp()

static SCIP_DECOMP * chooseDecomp ( SCIP * scip )

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

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

Referenced by determineVariableFixings(), and SCIP_DECL_HEUREXEC().

◆ determineVariableFixings()

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

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

References checkFixingrate(), chooseDecomp(), determineVariableFixingsDecomp(), 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(), TRUE, and RollingHorizon::variablegraph.

Referenced by SCIP_DECL_HEUREXEC().

◆ setLimits()

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

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

References SolveLimits::nodelimit, NULL, SCIP_CALL, SCIP_OKAY, SCIPcopyLimits(), SCIPsetLongintParam(), SCIPsetRealParam(), and SolveLimits::stallnodelimit.

Referenced by setupSubScip().

◆ setupSubScip()

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

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

References FALSE, 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().

◆ determineLimits()

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

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

References FALSE, 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()

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

static

updates heurdata after a run of GINS

Parameters

scip	original SCIP data structure
heurdata	primal heuristic data

Definition at line 2268 of file heur_gins.c.

References SCIP_LONGINT_MAX, and SCIPgetNNodes().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

static 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 HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurGins().

◆ SCIP_DECL_HEURFREE()

static 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 NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEURINIT()

static 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 DEFAULT_RANDSEED, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPheurGetData(), and TRUE.

◆ SCIP_DECL_HEUREXITSOL()

static 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 decompHorizonFree(), NULL, SCIP_OKAY, and SCIPheurGetData().

◆ SCIP_DECL_HEUREXIT()

static 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 freeTabooList(), heurdataAvgDiscreteNeighborhoodSize(), NULL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPfreeRandom(), SCIPheurGetData(), SCIPstatistic, and SCIPverbMessage().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecGins )

static

execution method of primal heuristic

Definition at line 2404 of file heur_gins.c.

References chooseDecomp(), decompHorizonCreate(), decompHorizonRunAgain(), determineLimits(), determineVariableFixings(), FALSE, MIN, NULL, 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, and updateFailureStatistic().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_NODESOFS

◆ DEFAULT_MAXNODES

◆ DEFAULT_MINIMPROVE

◆ DEFAULT_MINNODES

◆ DEFAULT_MINFIXINGRATE

◆ DEFAULT_NODESQUOT

◆ DEFAULT_NWAITINGNODES

◆ DEFAULT_USELPROWS

◆ DEFAULT_COPYCUTS

◆ DEFAULT_BESTSOLLIMIT

◆ DEFAULT_FIXCONTVARS

◆ DEFAULT_POTENTIAL

◆ DEFAULT_MAXDISTANCE

◆ DEFAULT_RANDSEED

◆ DEFAULT_RELAXDENSECONSS

◆ DEFAULT_USEROLLINGHORIZON

◆ DEFAULT_ROLLHORIZONLIMFAC

◆ DEFAULT_USEDECOMP

◆ DEFAULT_USEDECOMPROLLHORIZON

◆ DEFAULT_USESELFALLBACK

◆ DEFAULT_OVERLAP

◆ DEFAULT_CONSECUTIVEBLOCKS

Typedef Documentation

◆ ROLLINGHORIZON

◆ DECOMPHORIZON

◆ TABOOLIST

◆ SOLVELIMITS

Function Documentation

◆ checkFixingrate()

◆ getPotential()

◆ decompHorizonSetOverlapInterval()

◆ decompHorizonCreate()

◆ decompHorizonFree()

◆ decompHorizonRunAgain()

◆ decompHorizonIsInitialized()

◆ SCIP_DECL_SORTINDCOMP()

◆ decompHorizonInitialize()

◆ decompHorizonGetFirstPosBestPotential()

◆ decompHorizonBlockUsedRecently()

◆ decompHorizonNext()

◆ decomphorizonGetVars()

◆ rollingHorizonCreate()

◆ tabooListReset()

◆ createTabooList()

◆ freeTabooList()

◆ tabooListAdd()

◆ tabooListFind()

◆ tabooListGetLastK()

◆ taboolistgetNElems()

◆ rollingHorizonFree()

◆ rollingHorizonRunAgain()

◆ rollingHorizonStoreDistances()

◆ isVariableInNeighborhood()

◆ getFixVal()

◆ fixNonNeighborhoodVariables()

◆ determineMaxDistance()

◆ heurdataAvgDiscreteNeighborhoodSize()

◆ countLabel()

◆ selectInitialVariableDecomposition()

◆ selectInitialVariableRandomly()

◆ selectNextVariable()

◆ decompHorizonMarkInterval()

◆ determineVariableFixingsDecomp()

◆ chooseDecomp()