Detailed Description

variable upper and lower bound propagator

Author: Stefan Heinz; Jens Schulz; Gerald Gamrath

This propagator uses global bound information provided by SCIP to deduce global and local bound changes. It can take into account

implications (bound change following from specific value of a binary variable)
cliques (set of binary variables, each with a corresponding value, of which at most one variable can get the value)
variable lower/upper bounds (bounds of arbitrary variables that depend linearly on the value of another variable)

The propagator does not look at a variable in whole, but at one point in time only handles one specific bound (lower or upper) of a variable and deduces changes for lower or upper bounds of other variables. The concept is as follows:

1) Extract variable bound data

Implications and cliques are stored in a way such that given a variable and its new value, we can access all bound changes that can be deduced from setting the variable to that value. However, for variable bounds, this currently does not hold, they are only stored in the other direction, i.e. for a bound of a given variable, we have a list of all other bounds of variables that directly influence the bound of the given variable and a linear function describing how they do this. For the propagation, we need the other direction, thus we store it in the propagator data when the branch-and-bound solving process is about to begin.

2) Topological sorting of bounds of variable

We compute a topological order of the bounds of variables. This is needed to define an order in which we will regard bounds of variables in the propagation process in order to avoid unneccessarily regarding the same variable bound multiple times because it was changed in the meantime when propagating another bound of a variable. Therefore, we implictly regard a directed graph, in which each node corresponds to a bound of a variable and there exists a directed edge from one node to another, if the bound corresponding to the former node influences the bound corresponding to the latter node. This is done by iteratively running a DFS until all nodes were visited. Note that there might be cycles in the graph, which are randomly broken, so the order is only almost topological.

3) Collecting bound changes

For each bound of a variable, which can trigger bound changes of other variables, the propagator catches all events informing about a global change of the bound or a local tightening of the bound. The event handler then adds the bound of the variable to a priority queue, with the key in the priority queue corresponding to the position of the bound in the topological sort.

4) Propagating Bounds

As long as there are bounds contained in the priority queue, the propagator pops one bound from the queue, which is the one most at the beginning of the topological sort, so it should not be influenced by propagating other bounds currently contained in the queue. Starting at this bound, all implication, clique, and variable bound information is used to deduce tigther bounds for other variables and change the bounds, if a tighter one is found. These bound changes trigger an event that will lead to adding the corresponding bound to the priority queue, if it is not contained, yet. The process is iterated until the priority queue contains no more bounds.

Definition in file prop_vbounds.c.

#include <assert.h>
#include <string.h>
#include "scip/prop_vbounds.h"

Go to the source code of this file.

Macros
#define	INITMEMSIZE 5

#define	VISITED 1

#define	ACTIVE 2

Propagator properties
#define	PROP_NAME "vbounds"

#define	PROP_DESC "propagates variable upper and lower bounds"

#define	PROP_TIMING SCIP_PROPTIMING_BEFORELP \| SCIP_PROPTIMING_AFTERLPLOOP

#define	PROP_PRIORITY 3000000

#define	PROP_FREQ 1

#define	PROP_DELAY FALSE

Event handler properties
#define	EVENTHDLR_NAME "vbounds"

#define	EVENTHDLR_DESC "bound change event handler for for vbounds propagator"

Default parameter values
#define	DEFAULT_USEBDWIDENING TRUE

#define	DEFAULT_USEIMPLICS FALSE

#define	DEFAULT_USECLIQUES FALSE

#define	DEFAULT_USEVBOUNDS TRUE

#define	DEFAULT_DOTOPOSORT TRUE

#define	DEFAULT_SORTCLIQUES FALSE

#define	DEFAULT_DETECTCYCLES FALSE

Propagator defines
The propagator works on indices representing a bound of a variable. This index will be called bound index in the following. For a given active variable with problem index i (note that active variables have problem indices between 0 and nactivevariable - 1), the bound index of its lower bound is 2i, the bound index of its upper bound is 2i + 1. The other way around, a given bound index i corresponds to the variable with problem index i/2 (rounded down), and to the lower bound, if i is even, to the upper bound if i is odd. The following macros can be used to convert bound index into variable problem index and boundtype and vice versa.
#define	getLbIndex(idx) (2*(idx))

#define	getUbIndex(idx) (2*(idx)+1)

#define	getVarIndex(idx) ((idx)/2)

#define	getBoundtype(idx) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)

#define	isIndexLowerbound(idx) ((idx) % 2 == 0)

#define	getBoundString(lower) ((lower) ? "lb" : "ub")

#define	getBoundtypeString(type) ((type) == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper")

#define	indexGetBoundString(idx) (getBoundString(isIndexLowerbound(idx)))

#define	getOtherBoundIndex(idx) (((idx) % 2 == 0) ? (idx) + 1 : (idx) - 1)

Typedefs
typedef struct InferInfo	INFERINFO

Functions
static INFERINFO	intToInferInfo (int i)

static int	inferInfoToInt (INFERINFO inferinfo)

static SCIP_BOUNDTYPE	inferInfoGetBoundtype (INFERINFO inferinfo)

static int	inferInfoGetPos (INFERINFO inferinfo)

static INFERINFO	getInferInfo (int pos, SCIP_BOUNDTYPE boundtype)

static int	varGetLbIndex (SCIP_PROPDATA propdata, SCIP_VAR var)

static int	varGetUbIndex (SCIP_PROPDATA propdata, SCIP_VAR var)

static void	resetPropdata (SCIP_PROPDATA *propdata)

static SCIP_RETCODE	catchEvents (SCIP scip, SCIP_PROPDATA propdata)

static SCIP_RETCODE	dropEvents (SCIP scip, SCIP_PROPDATA propdata)

static SCIP_RETCODE	addVbound (SCIP scip, SCIP_PROPDATA propdata, int startidx, int endidx, SCIP_Real coef, SCIP_Real constant)

static	SCIP_DECL_SORTPTRCOMP (compVarboundIndices)

static SCIP_RETCODE	extractCycle (SCIP scip, SCIP_PROPDATA propdata, int dfsstack, int stacknextedge, int stacksize, SCIP_Bool samebound, SCIP_Bool *infeasible)

static SCIP_RETCODE	dfs (SCIP scip, SCIP_PROPDATA propdata, int startnode, int visited, int dfsstack, int stacknextedge, int dfsnodes, int ndfsnodes, SCIP_Bool infeasible)

static SCIP_RETCODE	topologicalSort (SCIP scip, SCIP_PROPDATA propdata, SCIP_Bool *infeasible)

static SCIP_RETCODE	initData (SCIP scip, SCIP_PROP prop, SCIP_Bool *infeasible)

static SCIP_RETCODE	resolvePropagation (SCIP scip, SCIP_PROPDATA propdata, SCIP_VAR var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX bdchgidx)

static SCIP_RETCODE	relaxVbdvar (SCIP scip, SCIP_VAR var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_Real relaxedbd)

static SCIP_Real	computeRelaxedLowerbound (SCIP scip, SCIP_VAR var, SCIP_Real inferlb, SCIP_Real coef, SCIP_Real constant)

static SCIP_RETCODE	analyzeConflictLowerbound (SCIP scip, SCIP_PROPDATA propdata, SCIP_VAR infervar, SCIP_Real inferlb, SCIP_VAR vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide)

static SCIP_Real	computeRelaxedUpperbound (SCIP scip, SCIP_VAR var, SCIP_Real inferub, SCIP_Real coef, SCIP_Real constant)

static SCIP_RETCODE	analyzeConflictUpperbound (SCIP scip, SCIP_PROPDATA propdata, SCIP_VAR infervar, SCIP_Real inferub, SCIP_VAR vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide)

static SCIP_RETCODE	tightenVarLb (SCIP scip, SCIP_PROP prop, SCIP_PROPDATA propdata, SCIP_VAR var, SCIP_Real newlb, SCIP_Bool global, SCIP_VAR vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Bool force, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide, int nchgbds, SCIP_RESULT *result)

static SCIP_RETCODE	tightenVarUb (SCIP scip, SCIP_PROP prop, SCIP_PROPDATA propdata, SCIP_VAR var, SCIP_Real newub, SCIP_Bool global, SCIP_VAR vbdvar, SCIP_BOUNDTYPE boundtype, SCIP_Bool force, SCIP_Real coef, SCIP_Real constant, SCIP_Bool canwide, int nchgbds, SCIP_RESULT *result)

static SCIP_RETCODE	propagateVbounds (SCIP scip, SCIP_PROP prop, SCIP_Bool force, SCIP_RESULT *result)

Callback methods of propagator
static	SCIP_DECL_PROPCOPY (propCopyVbounds)

static	SCIP_DECL_PROPFREE (propFreeVbounds)

static	SCIP_DECL_PROPEXITSOL (propExitsolVbounds)

static	SCIP_DECL_PROPEXEC (propExecVbounds)

static	SCIP_DECL_PROPRESPROP (propRespropVbounds)

Callback methods of event handler
static	SCIP_DECL_EVENTEXEC (eventExecVbound)

Interface methods
SCIP_RETCODE	SCIPincludePropVbounds (SCIP *scip)

SCIP_Bool	SCIPisPropagatedVbounds (SCIP *scip)

SCIP_RETCODE	SCIPexecPropVbounds (SCIP scip, SCIP_Bool force, SCIP_RESULT result)

Macro Definition Documentation

◆ PROP_NAME

#define PROP_NAME "vbounds"

Definition at line 80 of file prop_vbounds.c.

Referenced by SCIP_DECL_PROPCOPY(), SCIPexecPropVbounds(), SCIPincludePropVbounds(), and SCIPisPropagatedVbounds().

◆ PROP_DESC

#define PROP_DESC "propagates variable upper and lower bounds"

Definition at line 81 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ PROP_TIMING

#define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 82 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ PROP_PRIORITY

#define PROP_PRIORITY 3000000

propagator priority

Definition at line 83 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ PROP_FREQ

#define PROP_FREQ 1

propagator frequency

Definition at line 84 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ PROP_DELAY

#define PROP_DELAY FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 85 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "vbounds"

Definition at line 94 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC "bound change event handler for for vbounds propagator"

Definition at line 95 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ DEFAULT_USEBDWIDENING

#define DEFAULT_USEBDWIDENING TRUE

should bound widening be used to initialize conflict analysis?

Definition at line 104 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ DEFAULT_USEIMPLICS

#define DEFAULT_USEIMPLICS FALSE

should implications be propagated?

Definition at line 105 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ DEFAULT_USECLIQUES

#define DEFAULT_USECLIQUES FALSE

should cliques be propagated?

Definition at line 106 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ DEFAULT_USEVBOUNDS

#define DEFAULT_USEVBOUNDS TRUE

should variable bounds be propagated?

Definition at line 107 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ DEFAULT_DOTOPOSORT

#define DEFAULT_DOTOPOSORT TRUE

should the bounds be topologically sorted in advance?

Definition at line 108 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ DEFAULT_SORTCLIQUES

#define DEFAULT_SORTCLIQUES FALSE

should cliques be regarded for the topological sort?

Definition at line 109 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ DEFAULT_DETECTCYCLES

#define DEFAULT_DETECTCYCLES FALSE

should cycles in the variable bound graph be identified?

Definition at line 110 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ getLbIndex

#define getLbIndex ( idx ) (2*(idx))

Definition at line 125 of file prop_vbounds.c.

Referenced by varGetLbIndex().

◆ getUbIndex

#define getUbIndex ( idx ) (2*(idx)+1)

Definition at line 126 of file prop_vbounds.c.

Referenced by varGetUbIndex().

◆ getVarIndex

#define getVarIndex ( idx ) ((idx)/2)

Definition at line 127 of file prop_vbounds.c.

Referenced by catchEvents(), dfs(), dropEvents(), extractCycle(), initData(), propagateVbounds(), SCIP_DECL_EVENTEXEC(), and SCIP_DECL_PROPRESPROP().

◆ getBoundtype

#define getBoundtype ( idx ) (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER)

Definition at line 128 of file prop_vbounds.c.

Referenced by initData(), and propagateVbounds().

◆ isIndexLowerbound

#define isIndexLowerbound ( idx ) ((idx) % 2 == 0)

Definition at line 129 of file prop_vbounds.c.

Referenced by catchEvents(), dfs(), dropEvents(), extractCycle(), initData(), propagateVbounds(), and SCIP_DECL_EVENTEXEC().

◆ getBoundString

#define getBoundString ( lower ) ((lower) ? "lb" : "ub")

Definition at line 130 of file prop_vbounds.c.

Referenced by dfs().

◆ getBoundtypeString

#define getBoundtypeString ( type ) ((type) == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper")

Definition at line 131 of file prop_vbounds.c.

Referenced by propagateVbounds(), resolvePropagation(), SCIP_DECL_PROPRESPROP(), tightenVarLb(), and tightenVarUb().

◆ indexGetBoundString

#define indexGetBoundString ( idx ) (getBoundString(isIndexLowerbound(idx)))

Definition at line 132 of file prop_vbounds.c.

Referenced by dfs(), extractCycle(), and SCIP_DECL_EVENTEXEC().

◆ getOtherBoundIndex

#define getOtherBoundIndex ( idx ) (((idx) % 2 == 0) ? (idx) + 1 : (idx) - 1)

Definition at line 133 of file prop_vbounds.c.

Referenced by dfs(), and extractCycle().

◆ INITMEMSIZE

#define INITMEMSIZE 5

Definition at line 406 of file prop_vbounds.c.

Referenced by addVbound().

◆ VISITED

#define VISITED 1

Definition at line 749 of file prop_vbounds.c.

Referenced by dfs().

◆ ACTIVE

#define ACTIVE 2

Definition at line 750 of file prop_vbounds.c.

Referenced by dfs().

Typedef Documentation

◆ INFERINFO

typedef struct InferInfo INFERINFO

Definition at line 190 of file prop_vbounds.c.

Function Documentation

◆ intToInferInfo()

static INFERINFO intToInferInfo ( int i )

static

converts an integer into an inference information

Parameters

i	integer to convert

Definition at line 194 of file prop_vbounds.c.

Referenced by SCIP_DECL_PROPRESPROP().

◆ inferInfoToInt()

static int inferInfoToInt ( INFERINFO inferinfo )

static

converts an inference information into an int

Parameters

inferinfo inference information to convert

Definition at line 207 of file prop_vbounds.c.

Referenced by tightenVarLb(), and tightenVarUb().

◆ inferInfoGetBoundtype()

static SCIP_BOUNDTYPE inferInfoGetBoundtype ( INFERINFO inferinfo )

static

returns the propagation rule stored in the inference information

Parameters

inferinfo inference information to convert

Definition at line 216 of file prop_vbounds.c.

References SCIP_BOUNDTYPE_LOWER, and SCIP_BOUNDTYPE_UPPER.

Referenced by SCIP_DECL_PROPRESPROP().

◆ inferInfoGetPos()

static int inferInfoGetPos ( INFERINFO inferinfo )

static

returns the position stored in the inference information

Parameters

inferinfo inference information to convert

Definition at line 227 of file prop_vbounds.c.

Referenced by SCIP_DECL_PROPRESPROP().

◆ getInferInfo()

static INFERINFO getInferInfo	(	int	pos,
		SCIP_BOUNDTYPE	boundtype
	)

static

constructs an inference information out of a position of a variable and a boundtype

Parameters

pos	position of the variable which forced that propagation
boundtype	propagation rule that deduced the value

Definition at line 236 of file prop_vbounds.c.

References SCIP_BOUNDTYPE_LOWER, and SCIP_BOUNDTYPE_UPPER.

Referenced by tightenVarLb(), and tightenVarUb().

◆ varGetLbIndex()

static int varGetLbIndex	(	SCIP_PROPDATA *	propdata,
		SCIP_VAR *	var
	)

static

Parameters

propdata	propagator data
var	variable to get the index for

Definition at line 259 of file prop_vbounds.c.

References getLbIndex, SCIPhashmapExists(), and SCIPhashmapGetImage().

Referenced by dfs(), extractCycle(), initData(), SCIP_DECL_PROPRESPROP(), tightenVarLb(), and tightenVarUb().

◆ varGetUbIndex()

static int varGetUbIndex	(	SCIP_PROPDATA *	propdata,
		SCIP_VAR *	var
	)

static

Parameters

propdata	propagator data
var	variable to get the index for

Definition at line 271 of file prop_vbounds.c.

References getUbIndex, SCIPhashmapExists(), and SCIPhashmapGetImage().

Referenced by dfs(), extractCycle(), initData(), SCIP_DECL_PROPRESPROP(), tightenVarLb(), and tightenVarUb().

◆ resetPropdata()

static void resetPropdata ( SCIP_PROPDATA * propdata )

static

reset propagation data

Parameters

propdata propagator data

Definition at line 283 of file prop_vbounds.c.

References FALSE, and NULL.

Referenced by SCIP_DECL_PROPEXITSOL(), and SCIPincludePropVbounds().

◆ catchEvents()

static SCIP_RETCODE catchEvents	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata
	)

static

catches events for variables

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 301 of file prop_vbounds.c.

References getVarIndex, isIndexLowerbound, NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_OKAY, SCIPcatchVarEvent(), SCIPvarGetNCliques(), and SCIPvarGetNImpls().

Referenced by initData().

◆ dropEvents()

static SCIP_RETCODE dropEvents	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata
	)

static

drops events for variables

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 360 of file prop_vbounds.c.

References getVarIndex, isIndexLowerbound, NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_OKAY, and SCIPdropVarEvent().

Referenced by SCIP_DECL_PROPEXITSOL().

◆ addVbound()

static SCIP_RETCODE addVbound	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		int	startidx,
		int	endidx,
		SCIP_Real	coef,
		SCIP_Real	constant
	)

static

Parameters

scip	SCIP data structure
propdata	propagator data
startidx	index of bound of variable influencing the other variable
endidx	index of bound of variable which is influenced
coef	coefficient in the variable bound
constant	constant in the variable bound

Definition at line 410 of file prop_vbounds.c.

References INITMEMSIZE, NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocMemoryArray.

Referenced by initData().

◆ SCIP_DECL_SORTPTRCOMP()

static SCIP_DECL_SORTPTRCOMP ( compVarboundIndices )

static

comparison method for two indices in the topoorder array, preferring higher indices because the order is reverse topological

Definition at line 457 of file prop_vbounds.c.

◆ extractCycle()

static SCIP_RETCODE extractCycle	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		int *	dfsstack,
		int *	stacknextedge,
		int	stacksize,
		SCIP_Bool	samebound,
		SCIP_Bool *	infeasible
	)

static

Parameters

scip	SCIP data structure
propdata	propagator data
dfsstack	array of size number of nodes to store the stack; only needed for performance reasons
stacknextedge	array storing the next edge to be visited in dfs for all nodes on the stack/in the current path; negative numbers represent a clique, positive numbers an implication (smaller numbers) or a variable bound
stacksize	current stack size
samebound	does the cycle contain the same bound twice or both bounds of the same variable?
infeasible	pointer to store whether an infeasibility was detected

Definition at line 469 of file prop_vbounds.c.

References FALSE, getOtherBoundIndex, getVarIndex, indexGetBoundString, isIndexLowerbound, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPcliqueIsEquation(), SCIPdebugMsg, SCIPisEQ(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisGT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetCliques(), SCIPvarGetImplBounds(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetNImpls(), SCIPvarGetUbLocal(), TRUE, varGetLbIndex(), and varGetUbIndex().

Referenced by dfs().

◆ dfs()

static SCIP_RETCODE dfs	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		int	startnode,
		int *	visited,
		int *	dfsstack,
		int *	stacknextedge,
		int *	dfsnodes,
		int *	ndfsnodes,
		SCIP_Bool *	infeasible
	)

static

performs depth-first-search in the implicitly given directed graph from the given start index

Parameters

scip	SCIP data structure
propdata	propagator data
startnode	node to start the depth-first-search
visited	array to store for each node, whether it was already visited
dfsstack	array of size number of nodes to store the stack; only needed for performance reasons
stacknextedge	array of size number of nodes to store the next edge to be visited in dfs for all nodes on the stack/in the current path; only needed for performance reasons
dfsnodes	array of nodes that can be reached starting at startnode, in reverse dfs order
ndfsnodes	pointer to store number of nodes that can be reached starting at startnode
infeasible	pointer to store whether an infeasibility was detected

Definition at line 753 of file prop_vbounds.c.

References ACTIVE, extractCycle(), FALSE, getBoundString, getOtherBoundIndex, getVarIndex, indexGetBoundString, isIndexLowerbound, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPisFeasGE(), SCIPvarGetCliques(), SCIPvarGetImplIds(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetNImpls(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), TRUE, varGetLbIndex(), varGetUbIndex(), and VISITED.

Referenced by topologicalSort().

◆ topologicalSort()

static SCIP_RETCODE topologicalSort	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_Bool *	infeasible
	)

static

sort the bounds of variables topologically

Parameters

scip	SCIP data structure
propdata	propagator data
infeasible	pointer to store whether an infeasibility was detected

Definition at line 1078 of file prop_vbounds.c.

References dfs(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocClearBufferArray, and SCIPfreeBufferArray.

Referenced by initData().

◆ initData()

static SCIP_RETCODE initData	(	SCIP *	scip,
		SCIP_PROP *	prop,
		SCIP_Bool *	infeasible
	)

static

initializes the internal data for the variable bounds propagator

Parameters

scip	SCIP data structure
prop	vbounds propagator
infeasible	pointer to store whether an infeasibility was detected

Definition at line 1125 of file prop_vbounds.c.

References addVbound(), BMSclearMemoryArray, catchEvents(), FALSE, getBoundtype, getVarIndex, isIndexLowerbound, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetNVars(), SCIPgetProbName(), SCIPgetProbvarSum(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapInsert(), SCIPisPositive(), SCIPpqueueCreate(), SCIPpropGetData(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetType(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarHasImplic(), SCIPvarIsActive(), topologicalSort(), TRUE, varGetLbIndex(), and varGetUbIndex().

Referenced by propagateVbounds().

◆ resolvePropagation()

static SCIP_RETCODE resolvePropagation	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_VAR *	var,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_BDCHGIDX *	bdchgidx
	)

static

resolves a propagation by adding the variable which implied that bound change

Parameters

scip	SCIP data structure
propdata	propagator data
var	variable to be reported
boundtype	bound to be reported
bdchgidx	the index of the bound change, representing the point of time where the change took place, or NULL for the current local bounds

Definition at line 1297 of file prop_vbounds.c.

References getBoundtypeString, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPABORT, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPdebugMsg, SCIPerrorMessage, and SCIPvarGetName().

Referenced by analyzeConflictLowerbound(), analyzeConflictUpperbound(), and SCIP_DECL_PROPRESPROP().

◆ relaxVbdvar()

static SCIP_RETCODE relaxVbdvar	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_BDCHGIDX *	bdchgidx,
		SCIP_Real	relaxedbd
	)

static

relaxes bound of give variable as long as the given inference bound still leads to a cutoff and add that bound change to the conflict set

Parameters

scip	SCIP data structure
var	variable for which the upper bound should be relaxed
boundtype	boundtype used for the variable bound variable
bdchgidx	the index of the bound change, representing the point of time where the change took place, or NULL for the current local bounds
relaxedbd	relaxed bound

Definition at line 1333 of file prop_vbounds.c.

References SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIPaddConflictRelaxedLb(), and SCIPaddConflictRelaxedUb().

Referenced by analyzeConflictLowerbound(), analyzeConflictUpperbound(), and SCIP_DECL_PROPRESPROP().

◆ computeRelaxedLowerbound()

static SCIP_Real computeRelaxedLowerbound	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Real	inferlb,
		SCIP_Real	coef,
		SCIP_Real	constant
	)

static

compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable

Parameters

scip	SCIP data structure
var	variable which was propagated
inferlb	inference lower bound
coef	inference variable bound coefficient used
constant	inference variable bound constant used

Definition at line 1357 of file prop_vbounds.c.

References SCIP_Real, SCIPadjustedVarLb(), SCIPfeastol(), SCIPisEQ(), and SCIPvarIsIntegral().

Referenced by analyzeConflictLowerbound(), and SCIP_DECL_PROPRESPROP().

◆ analyzeConflictLowerbound()

static SCIP_RETCODE analyzeConflictLowerbound	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_VAR *	infervar,
		SCIP_Real	inferlb,
		SCIP_VAR *	vbdvar,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_Real	coef,
		SCIP_Real	constant,
		SCIP_Bool	canwide
	)

static

analyzes an infeasibility which was reached by updating the lower bound of the inference variable above its upper bound

Parameters

scip	SCIP data structure
propdata	propagator data
infervar	variable which led to a cutoff
inferlb	lower bound which led to infeasibility
vbdvar	variable which is the reason for the lower bound change
boundtype	bound which is the reason for the lower bound change
coef	inference variable bound coefficient used
constant	inference variable bound constant used
canwide	can bound widening be used (for vbounds) or not (for implications or cliques)

Definition at line 1382 of file prop_vbounds.c.

References computeRelaxedLowerbound(), FALSE, NULL, relaxVbdvar(), resolvePropagation(), SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIPaddConflictRelaxedUb(), SCIPaddConflictUb(), SCIPadjustedVarLb(), SCIPanalyzeConflict(), SCIPdebugMsg, SCIPfeastol(), SCIPgetConflictVarUb(), SCIPgetStage(), SCIPgetVarUbAtIndex(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPisEQ(), SCIPisGT(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and TRUE.

Referenced by tightenVarLb().

◆ computeRelaxedUpperbound()

static SCIP_Real computeRelaxedUpperbound	(	SCIP *	scip,
		SCIP_VAR *	var,
		SCIP_Real	inferub,
		SCIP_Real	coef,
		SCIP_Real	constant
	)

static

compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable

Parameters

scip	SCIP data structure
var	variable which was propagated
inferub	inference upper bound
coef	inference variable bound coefficient used
constant	inference variable bound constant used

Definition at line 1467 of file prop_vbounds.c.

References SCIP_Real, SCIPadjustedVarUb(), SCIPfeastol(), SCIPisEQ(), and SCIPvarIsIntegral().

Referenced by analyzeConflictUpperbound(), and SCIP_DECL_PROPRESPROP().

◆ analyzeConflictUpperbound()

static SCIP_RETCODE analyzeConflictUpperbound	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_VAR *	infervar,
		SCIP_Real	inferub,
		SCIP_VAR *	vbdvar,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_Real	coef,
		SCIP_Real	constant,
		SCIP_Bool	canwide
	)

static

analyzes an infeasibility which was reached by updating the upper bound of the inference variable below its lower bound

Parameters

scip	SCIP data structure
propdata	propagator data
infervar	variable which led to a cutoff
inferub	upper bound which led to infeasibility
vbdvar	variable which is the reason for the upper bound change
boundtype	bound which is the reason for the upper bound change
coef	inference variable bound coefficient used
constant	inference variable bound constant used
canwide	can bound widening be used (for vbounds) or not (for inplications or cliques)

Definition at line 1492 of file prop_vbounds.c.

References computeRelaxedUpperbound(), FALSE, NULL, relaxVbdvar(), resolvePropagation(), SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIPaddConflictLb(), SCIPaddConflictRelaxedLb(), SCIPadjustedVarUb(), SCIPanalyzeConflict(), SCIPdebugMsg, SCIPfeastol(), SCIPgetConflictVarLb(), SCIPgetStage(), SCIPgetVarLbAtIndex(), SCIPinitConflictAnalysis(), SCIPisConflictAnalysisApplicable(), SCIPisEQ(), SCIPisLT(), SCIPvarGetLbLocal(), SCIPvarIsIntegral(), and TRUE.

Referenced by tightenVarUb().

◆ tightenVarLb()

static SCIP_RETCODE tightenVarLb	(	SCIP *	scip,
		SCIP_PROP *	prop,
		SCIP_PROPDATA *	propdata,
		SCIP_VAR *	var,
		SCIP_Real	newlb,
		SCIP_Bool	global,
		SCIP_VAR *	vbdvar,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_Bool	force,
		SCIP_Real	coef,
		SCIP_Real	constant,
		SCIP_Bool	canwide,
		int *	nchgbds,
		SCIP_RESULT *	result
	)

static

Parameters

scip	SCIP data structure
prop	vbounds propagator
propdata	propagator data
var	variable whose lower bound should be tightened
newlb	new lower bound for the variable
global	is the bound globally valid?
vbdvar	variable which is the reason for the lower bound change
boundtype	bound which is the reason for the lower bound change
force	should domain changes for continuous variables be forced
coef	coefficient in vbound constraint causing the propagation; or 0.0 if propagation is caused by clique or implication
constant	constant in vbound constraint causing the propagation; or 0.0 if propagation is caused by clique or implication
canwide	can bound widening be used (for vbounds) or not (for inplications or cliques)
nchgbds	pointer to increase, if a bound was changed
result	pointer to store the result of the propagation

Definition at line 1576 of file prop_vbounds.c.

References analyzeConflictLowerbound(), FALSE, getBoundtypeString, getInferInfo(), inferInfoToInt(), NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIPcutoffNode(), SCIPdebugMsg, SCIPgetRootNode(), SCIPinferVarLbProp(), SCIPisGT(), SCIPtightenVarLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, varGetLbIndex(), and varGetUbIndex().

Referenced by propagateVbounds().

◆ tightenVarUb()

static SCIP_RETCODE tightenVarUb	(	SCIP *	scip,
		SCIP_PROP *	prop,
		SCIP_PROPDATA *	propdata,
		SCIP_VAR *	var,
		SCIP_Real	newub,
		SCIP_Bool	global,
		SCIP_VAR *	vbdvar,
		SCIP_BOUNDTYPE	boundtype,
		SCIP_Bool	force,
		SCIP_Real	coef,
		SCIP_Real	constant,
		SCIP_Bool	canwide,
		int *	nchgbds,
		SCIP_RESULT *	result
	)

static

Parameters

scip	SCIP data structure
prop	vbounds propagator
propdata	propagator data
var	variable whose upper bound should be tightened
newub	new upper bound of the variable
global	is the bound globally valid?
vbdvar	variable which is the reason for the upper bound change
boundtype	bound which is the reason for the upper bound change
force	should domain changes for continuous variables be forced
coef	coefficient in vbound constraint causing the propagation; or 0.0 if propagation is caused by clique or implication
constant	constant in vbound constraint causing the propagation; or 0.0 if propagation is caused by clique or implication
canwide	can bound widening be used (for vbounds) or not (for inplications or cliques)
nchgbds	pointer to increase, if a bound was changed
result	pointer to store the result of the propagation

Definition at line 1660 of file prop_vbounds.c.

References analyzeConflictUpperbound(), FALSE, getBoundtypeString, getInferInfo(), inferInfoToInt(), NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIPcutoffNode(), SCIPdebugMsg, SCIPgetRootNode(), SCIPinferVarUbProp(), SCIPisLT(), SCIPtightenVarUbGlobal(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, varGetLbIndex(), and varGetUbIndex().

Referenced by propagateVbounds().

◆ propagateVbounds()

static SCIP_RETCODE propagateVbounds	(	SCIP *	scip,
		SCIP_PROP *	prop,
		SCIP_Bool	force,
		SCIP_RESULT *	result
	)

static

performs propagation of variables lower and upper bounds, implications, and cliques

Parameters

scip	SCIP data structure
prop	vbounds propagator
force	should domain changes for continuous variables be forced
result	pointer to store the result of the propagation

Definition at line 1744 of file prop_vbounds.c.

References FALSE, getBoundtype, getBoundtypeString, getVarIndex, initData(), isIndexLowerbound, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_STAGE_PRESOLVING, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPgetStage(), SCIPinRepropagation(), SCIPisEQ(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPpqueueRemove(), SCIPpropGetData(), SCIPvarGetCliques(), SCIPvarGetImplBounds(), SCIPvarGetImplIds(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetNImpls(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsActive(), SCIPvarIsBinary(), tightenVarLb(), tightenVarUb(), and TRUE.

Referenced by SCIP_DECL_PROPEXEC(), and SCIPexecPropVbounds().

◆ SCIP_DECL_PROPCOPY()

static SCIP_DECL_PROPCOPY ( propCopyVbounds )

static

copy method for propagator plugins (called when SCIP copies plugins)

Definition at line 2028 of file prop_vbounds.c.

References NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePropVbounds(), and SCIPpropGetName().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeVbounds )

static

destructor of propagator to free user data (called when SCIP is exiting)

Definition at line 2042 of file prop_vbounds.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropSetData().

◆ SCIP_DECL_PROPEXITSOL()

static SCIP_DECL_PROPEXITSOL ( propExitsolVbounds )

static

solving process deinitialization method of propagator (called before branch and bound process data is freed)

Definition at line 2057 of file prop_vbounds.c.

References dropEvents(), NULL, resetPropdata(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPfreeMemoryArray, SCIPhashmapFree(), SCIPpqueueFree(), and SCIPpropGetData().

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecVbounds )

static

execution method of propagator

Definition at line 2108 of file prop_vbounds.c.

References FALSE, propagateVbounds(), SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, and SCIP_REDUCEDDOM.

◆ SCIP_DECL_PROPRESPROP()

static SCIP_DECL_PROPRESPROP ( propRespropVbounds )

static

propagation conflict resolving method of propagator

Definition at line 2124 of file prop_vbounds.c.

References computeRelaxedLowerbound(), computeRelaxedUpperbound(), getBoundtypeString, getVarIndex, inferInfoGetBoundtype(), inferInfoGetPos(), intToInferInfo(), NULL, relaxVbdvar(), resolvePropagation(), SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPdebugMsg, SCIPisZero(), SCIPpropGetData(), SCIPvarGetName(), SCIPvarIsBinary(), varGetLbIndex(), and varGetUbIndex().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecVbound )

static

execution method of bound change event handler

Definition at line 2203 of file prop_vbounds.c.

References getVarIndex, indexGetBoundString, isIndexLowerbound, NULL, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPeventGetNewbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPeventhdlrGetData(), SCIPgetNVars(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarIsBinary(), and TRUE.

SCIP

Detailed Description

Macros

Typedefs

Functions

Macro Definition Documentation

◆ PROP_NAME

◆ PROP_DESC

◆ PROP_TIMING

◆ PROP_PRIORITY

◆ PROP_FREQ

◆ PROP_DELAY

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

◆ DEFAULT_USEBDWIDENING

◆ DEFAULT_USEIMPLICS

◆ DEFAULT_USECLIQUES

◆ DEFAULT_USEVBOUNDS

◆ DEFAULT_DOTOPOSORT

◆ DEFAULT_SORTCLIQUES

◆ DEFAULT_DETECTCYCLES

◆ getLbIndex

◆ getUbIndex

◆ getVarIndex

◆ getBoundtype

◆ isIndexLowerbound

◆ getBoundString

◆ getBoundtypeString

◆ indexGetBoundString

◆ getOtherBoundIndex

◆ INITMEMSIZE

◆ VISITED

◆ ACTIVE

Typedef Documentation

◆ INFERINFO

Function Documentation

◆ intToInferInfo()

◆ inferInfoToInt()

◆ inferInfoGetBoundtype()

◆ inferInfoGetPos()

◆ getInferInfo()

◆ varGetLbIndex()

◆ varGetUbIndex()

◆ resetPropdata()

◆ catchEvents()

◆ dropEvents()

◆ addVbound()

◆ SCIP_DECL_SORTPTRCOMP()

◆ extractCycle()

◆ dfs()

◆ topologicalSort()

◆ initData()

◆ resolvePropagation()

◆ relaxVbdvar()

◆ computeRelaxedLowerbound()

◆ analyzeConflictLowerbound()

◆ computeRelaxedUpperbound()

◆ analyzeConflictUpperbound()

◆ tightenVarLb()

◆ tightenVarUb()

◆ propagateVbounds()

◆ SCIP_DECL_PROPCOPY()

◆ SCIP_DECL_PROPFREE()

◆ SCIP_DECL_PROPEXITSOL()

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPRESPROP()

◆ SCIP_DECL_EVENTEXEC()