SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
variable upper and lower bound propagator
This propagator uses global bound information provided by SCIP to deduce global and local bound changes. It can take into account
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.
Additionally, the propagator analyzes the conflict/clique graph during presolving. It uses Tarjan's algorithm to search for strongly connected components, for each of which all variables can be aggregated to one. Additionally, it may detect invalid assignments of binary variables and fix the variable to the only possible value left.
Definition in file prop_vbounds.c.
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 |
| #define | PROP_PRESOL_PRIORITY -90000 |
| #define | PROP_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM | SCIP_PRESOLTIMING_EXHAUSTIVE |
| #define | PROP_PRESOL_MAXROUNDS -1 |
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 |
| #define | DEFAULT_MINNEWCLIQUES 0.1 |
| #define | DEFAULT_MAXCLIQUESMEDIUM 50.0 |
| #define | DEFAULT_MAXCLIQUESEXHAUSTIVE 100.0 |
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 2*i, the bound index of its upper bound is 2*i + 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) + 1 - 2 * ((idx) % 2)) |
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_PROPINITPRE (propInitpreVbounds) |
| static | SCIP_DECL_PROPEXITSOL (propExitsolVbounds) |
| static SCIP_RETCODE | tarjan (SCIP *scip, int startnode, int *startindex, SCIP_Shortbool *nodeonstack, int *nodeindex, int *nodelowlink, SCIP_Shortbool *nodeinfeasible, int *dfsstack, int *predstackidx, int *stacknextclique, int *stacknextcliquevar, int *topoorder, int *nordered, int *cliquefirstentry, int *cliquecurrentexit, int *sccvars, int *sccstarts, int *nsccs, int *infeasnodes, int *ninfeasnodes, SCIP_Bool *infeasible) |
| static SCIP_RETCODE | applyFixingsAndAggregations (SCIP *scip, SCIP_VAR **vars, int *infeasnodes, int ninfeasnodes, SCIP_Shortbool *nodeinfeasible, int *sccvars, int *sccstarts, int nsccs, SCIP_Bool *infeasible, int *nfixedvars, int *naggrvars, SCIP_RESULT *result) |
| static | SCIP_DECL_PROPPRESOL (propPresolVbounds) |
| 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) |
| #define PROP_NAME "vbounds" |
Definition at line 85 of file prop_vbounds.c.
Referenced by SCIPexecPropVbounds(), SCIPincludePropVbounds(), and SCIPisPropagatedVbounds().
| #define PROP_DESC "propagates variable upper and lower bounds" |
Definition at line 86 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 87 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define PROP_PRIORITY 3000000 |
propagator priority
Definition at line 88 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define PROP_FREQ 1 |
propagator frequency
Definition at line 89 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define PROP_DELAY FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 90 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define PROP_PRESOL_PRIORITY -90000 |
priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers
Definition at line 92 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM | SCIP_PRESOLTIMING_EXHAUSTIVE |
Definition at line 93 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define PROP_PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 94 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define EVENTHDLR_NAME "vbounds" |
Definition at line 104 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define EVENTHDLR_DESC "bound change event handler for for vbounds propagator" |
Definition at line 105 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define DEFAULT_USEBDWIDENING TRUE |
should bound widening be used to initialize conflict analysis?
Definition at line 114 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define DEFAULT_USEIMPLICS FALSE |
should implications be propagated?
Definition at line 115 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define DEFAULT_USECLIQUES FALSE |
should cliques be propagated?
Definition at line 116 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define DEFAULT_USEVBOUNDS TRUE |
should variable bounds be propagated?
Definition at line 117 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define DEFAULT_DOTOPOSORT TRUE |
should the bounds be topologically sorted in advance?
Definition at line 118 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define DEFAULT_SORTCLIQUES FALSE |
should cliques be regarded for the topological sort?
Definition at line 119 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define DEFAULT_DETECTCYCLES FALSE |
should cycles in the variable bound graph be identified?
Definition at line 120 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define DEFAULT_MINNEWCLIQUES 0.1 |
minimum number of new cliques to trigger another clique table analysis
Definition at line 121 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define DEFAULT_MAXCLIQUESMEDIUM 50.0 |
maximum number of cliques per variable to run clique table analysis in medium presolving
Definition at line 122 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define DEFAULT_MAXCLIQUESEXHAUSTIVE 100.0 |
maximum number of cliques per variable to run clique table analysis in exhaustive presolving
Definition at line 125 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
| #define getLbIndex | ( | idx | ) | (2*(idx)) |
Definition at line 142 of file prop_vbounds.c.
Referenced by tarjan(), and varGetLbIndex().
| #define getUbIndex | ( | idx | ) | (2*(idx)+1) |
Definition at line 143 of file prop_vbounds.c.
Referenced by tarjan(), and varGetUbIndex().
| #define getVarIndex | ( | idx | ) | ((idx)/2) |
Definition at line 144 of file prop_vbounds.c.
Referenced by applyFixingsAndAggregations(), catchEvents(), dfs(), dropEvents(), extractCycle(), initData(), propagateVbounds(), and tarjan().
| #define getBoundtype | ( | idx | ) | (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER) |
Definition at line 145 of file prop_vbounds.c.
Referenced by initData(), and propagateVbounds().
| #define isIndexLowerbound | ( | idx | ) | ((idx) % 2 == 0) |
Definition at line 146 of file prop_vbounds.c.
Referenced by applyFixingsAndAggregations(), catchEvents(), dfs(), dropEvents(), extractCycle(), initData(), propagateVbounds(), and tarjan().
| #define getBoundString | ( | lower | ) | ((lower) ? "lb" : "ub") |
Definition at line 147 of file prop_vbounds.c.
| #define getBoundtypeString | ( | type | ) | ((type) == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper") |
Definition at line 148 of file prop_vbounds.c.
Referenced by propagateVbounds(), resolvePropagation(), tightenVarLb(), and tightenVarUb().
| #define indexGetBoundString | ( | idx | ) | (getBoundString(isIndexLowerbound(idx))) |
Definition at line 149 of file prop_vbounds.c.
Referenced by dfs(), extractCycle(), and tarjan().
| #define getOtherBoundIndex | ( | idx | ) | ((idx) + 1 - 2 * ((idx) % 2)) |
Definition at line 150 of file prop_vbounds.c.
Referenced by dfs(), extractCycle(), and tarjan().
| #define INITMEMSIZE 5 |
Definition at line 427 of file prop_vbounds.c.
Referenced by addVbound().
| #define VISITED 1 |
Definition at line 770 of file prop_vbounds.c.
Referenced by dfs().
| #define ACTIVE 2 |
Definition at line 771 of file prop_vbounds.c.
Referenced by dfs().
| typedef struct InferInfo INFERINFO |
Definition at line 211 of file prop_vbounds.c.
|
static |
converts an integer into an inference information
| i | integer to convert |
Definition at line 215 of file prop_vbounds.c.
References inferInfoToInt().
|
static |
converts an inference information into an int
| inferinfo | inference information to convert |
Definition at line 228 of file prop_vbounds.c.
References inferInfoGetBoundtype().
Referenced by intToInferInfo(), tightenVarLb(), and tightenVarUb().
|
static |
returns the propagation rule stored in the inference information
| inferinfo | inference information to convert |
Definition at line 237 of file prop_vbounds.c.
References inferInfoGetPos(), SCIP_BOUNDTYPE_LOWER, and SCIP_BOUNDTYPE_UPPER.
Referenced by inferInfoToInt().
|
static |
returns the position stored in the inference information
| inferinfo | inference information to convert |
Definition at line 248 of file prop_vbounds.c.
References getInferInfo().
Referenced by inferInfoGetBoundtype().
|
static |
constructs an inference information out of a position of a variable and a boundtype
| pos | position of the variable which forced that propagation |
| boundtype | propagation rule that deduced the value |
Definition at line 257 of file prop_vbounds.c.
References SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, and varGetLbIndex().
Referenced by inferInfoGetPos(), tightenVarLb(), and tightenVarUb().
|
static |
| propdata | propagator data |
| var | variable to get the index for |
Definition at line 280 of file prop_vbounds.c.
References getLbIndex, SCIPhashmapExists(), SCIPhashmapGetImage(), and varGetUbIndex().
Referenced by dfs(), extractCycle(), getInferInfo(), initData(), tightenVarLb(), and tightenVarUb().
|
static |
| propdata | propagator data |
| var | variable to get the index for |
Definition at line 292 of file prop_vbounds.c.
References getUbIndex, resetPropdata(), SCIPhashmapExists(), and SCIPhashmapGetImage().
Referenced by dfs(), extractCycle(), initData(), tightenVarLb(), tightenVarUb(), and varGetLbIndex().
|
static |
reset propagation data
| propdata | propagator data |
Definition at line 304 of file prop_vbounds.c.
References catchEvents(), and FALSE.
Referenced by SCIPincludePropVbounds(), and varGetUbIndex().
|
static |
catches events for variables
| scip | SCIP data structure |
| propdata | propagator data |
Definition at line 322 of file prop_vbounds.c.
References dropEvents(), getVarIndex, isIndexLowerbound, 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(), and resetPropdata().
|
static |
drops events for variables
| scip | SCIP data structure |
| propdata | propagator data |
Definition at line 381 of file prop_vbounds.c.
References getVarIndex, isIndexLowerbound, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_OKAY, and SCIPdropVarEvent().
Referenced by catchEvents().
|
static |
| 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 431 of file prop_vbounds.c.
References INITMEMSIZE, SCIP_CALL, SCIP_DECL_SORTPTRCOMP(), SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocMemoryArray.
Referenced by initData().
|
static |
comparison method for two indices in the topoorder array, preferring higher indices because the order is reverse topological
Definition at line 478 of file prop_vbounds.c.
Referenced by addVbound().
|
static |
| 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 490 of file prop_vbounds.c.
References FALSE, getOtherBoundIndex, getVarIndex, indexGetBoundString, isIndexLowerbound, 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().
|
static |
performs depth-first-search in the implicitly given directed graph from the given start index
| 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 774 of file prop_vbounds.c.
References ACTIVE, extractCycle(), FALSE, getBoundString, getOtherBoundIndex, getVarIndex, indexGetBoundString, isIndexLowerbound, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPisFeasGE(), SCIPvarGetCliques(), SCIPvarGetImplIds(), SCIPvarGetImplTypes(), SCIPvarGetImplVars(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetNImpls(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), topologicalSort(), TRUE, varGetLbIndex(), varGetUbIndex(), and VISITED.
Referenced by topologicalSort().
|
static |
sort the bounds of variables topologically
| scip | SCIP data structure |
| propdata | propagator data |
| infeasible | pointer to store whether an infeasibility was detected |
Definition at line 1099 of file prop_vbounds.c.
References dfs(), initData(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocClearBufferArray, and SCIPfreeBufferArray.
Referenced by dfs(), and initData().
|
static |
initializes the internal data for the variable bounds propagator
| scip | SCIP data structure |
| prop | vbounds propagator |
| infeasible | pointer to store whether an infeasibility was detected |
Definition at line 1146 of file prop_vbounds.c.
References addVbound(), BMSclearMemoryArray, catchEvents(), FALSE, getBoundtype, getVarIndex, isIndexLowerbound, resolvePropagation(), 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(), and topologicalSort().
|
static |
resolves a propagation by adding the variable which implied that bound change
| 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 1318 of file prop_vbounds.c.
References getBoundtypeString, relaxVbdvar(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPABORT, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPdebugMsg, SCIPerrorMessage, and SCIPvarGetName().
Referenced by analyzeConflictLowerbound(), analyzeConflictUpperbound(), and initData().
|
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
| 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 1354 of file prop_vbounds.c.
References computeRelaxedLowerbound(), SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddConflictRelaxedLb(), and SCIPaddConflictRelaxedUb().
Referenced by analyzeConflictLowerbound(), analyzeConflictUpperbound(), and resolvePropagation().
|
static |
compute the relaxed bound which is sufficient to propagate the inference lower bound of given variable
| 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 1378 of file prop_vbounds.c.
References analyzeConflictLowerbound(), SCIP_Real, SCIPadjustedVarLb(), SCIPfeastol(), SCIPgetHugeValue(), SCIPisEQ(), and SCIPvarIsIntegral().
Referenced by analyzeConflictLowerbound(), and relaxVbdvar().
|
static |
analyzes an infeasibility which was reached by updating the lower bound of the inference variable above its upper bound
| 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 1408 of file prop_vbounds.c.
References computeRelaxedLowerbound(), computeRelaxedUpperbound(), FALSE, 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 computeRelaxedLowerbound(), and tightenVarLb().
|
static |
compute the relaxed bound which is sufficient to propagate the inference upper bound of given variable
| 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 1493 of file prop_vbounds.c.
References analyzeConflictUpperbound(), SCIP_Real, SCIPadjustedVarUb(), SCIPfeastol(), SCIPgetHugeValue(), SCIPisEQ(), and SCIPvarIsIntegral().
Referenced by analyzeConflictLowerbound(), and analyzeConflictUpperbound().
|
static |
analyzes an infeasibility which was reached by updating the upper bound of the inference variable below its lower bound
| 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 1523 of file prop_vbounds.c.
References computeRelaxedUpperbound(), FALSE, 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(), tightenVarLb(), and TRUE.
Referenced by computeRelaxedUpperbound(), and tightenVarUb().
|
static |
| 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 1607 of file prop_vbounds.c.
References analyzeConflictLowerbound(), FALSE, getBoundtypeString, getInferInfo(), inferInfoToInt(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIPcutoffNode(), SCIPdebugMsg, SCIPgetRootNode(), SCIPinferVarLbProp(), SCIPisGT(), SCIPtightenVarLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), tightenVarUb(), TRUE, varGetLbIndex(), and varGetUbIndex().
Referenced by analyzeConflictUpperbound(), and propagateVbounds().
|
static |
| 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 1691 of file prop_vbounds.c.
References analyzeConflictUpperbound(), FALSE, getBoundtypeString, getInferInfo(), inferInfoToInt(), propagateVbounds(), 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(), and tightenVarLb().
|
static |
performs propagation of variables lower and upper bounds, implications, and cliques
| 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 1775 of file prop_vbounds.c.
References FALSE, getBoundtype, getBoundtypeString, getVarIndex, initData(), isIndexLowerbound, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_PROPCOPY(), 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 SCIPexecPropVbounds(), and tightenVarUb().
|
static |
copy method for propagator plugins (called when SCIP copies plugins)
Definition at line 2059 of file prop_vbounds.c.
Referenced by propagateVbounds().
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 2073 of file prop_vbounds.c.
|
static |
presolving initialization method of propagator (called when presolving is about to begin)
Definition at line 2088 of file prop_vbounds.c.
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 2102 of file prop_vbounds.c.
|
static |
performs Tarjan's algorithm for strongly connected components in the implicitly given directed implication graph from the given start index; each variable x is represented by two nodes lb(x) = 2*idx(x) and ub(x) = 2*idx(x)+1 where lb(x) means that the lower bound of x should be changed, i.e., that x is fixed to 1, and vice versa.
The algorithm is an iterative version of Tarjans algorithm (see https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm) with some additional tweaks. Each clique x_1 + ... + x_k <= 1 is represented by k(k-1) arcs (lb(x_i),ub(x_j)), j != i. This quadratic number can blow up the running time of Tarjan's algorithm, which is linear in the number of nodes and arcs of the graph. However, it suffices to consider only k of these arcs during the course of the algorithm. To this end, when we first come to a node lb(x_i) of the clique, traverse all arcs (lb(x_i),ub(x_j)) for this particular i, and store that we entered the clique via lb(x_i). Next time we come to any node lb(x_i') of the clique, we know that the only arc pointing to an unvisited node is (lb(x_i'),ub(x_i)), all other edges can be disregarded. After that, we can disregard the clique for the further search. Additionally, we try to identify infeasible fixings for binary variables. Those can be given by a path from x=1 to x=0 (or vice versa) or if x=0 (or 1) implies both y=0 and y=1.
| scip | SCIP data structure |
| startnode | node to start the depth-first-search |
| startindex | next index to assign to a processed node |
| nodeonstack | array to store the whether a each node is on the stack |
| nodeindex | array to store the dfs index for each node |
| nodelowlink | array to store the lowlink for each node |
| nodeinfeasible | array to store whether the fixing of a node was detected to be infeasible |
| dfsstack | array of size number of nodes to store the stack |
| predstackidx | for each node on the stack: stack position of its predecessor in the Tarjan search |
| stacknextclique | array of size number of nodes to store the next clique to be regarded in the algorithm for all nodes on the stack |
| stacknextcliquevar | array of size number of nodes to store the next variable in the next clique to be regarded in the algorithm for all nodes on the stack |
| topoorder | array with reverse (almost) topological ordering of the nodes |
| nordered | number of ordered nodes (disconnected nodes are disregarded) |
| cliquefirstentry | node from which a clique was entered for the first time; needed because when entering the clique a second time, only the other bound corresponding to this node remains to be processed |
| cliquecurrentexit | for cliques which define an arc on the current path: target node of this arc |
| sccvars | array with all nontrivial strongly connected components in the graph |
| sccstarts | start indices of SCCs in sccvars array; one additional entry at the end to give length of used part of sccvars array |
| nsccs | pointer to store number of strongly connected components |
| infeasnodes | sparse array with node indices of infeasible nodes |
| ninfeasnodes | pointer to store the number of infeasible nodes |
| infeasible | pointer to store whether an infeasibility was detected |
Definition at line 2169 of file prop_vbounds.c.
References applyFixingsAndAggregations(), FALSE, getBoundString, getLbIndex, getOtherBoundIndex, getUbIndex, getVarIndex, indexGetBoundString, isIndexLowerbound, SCIP_Bool, SCIP_OKAY, SCIPcliqueGetIndex(), SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPvarGetCliques(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarIsActive(), and TRUE.
|
static |
apply fixings and aggregations found by the clique graph analysis
| scip | SCIP data structure |
| vars | array of active variables |
| infeasnodes | sparse array with node indices of infeasible nodes |
| ninfeasnodes | pointer to store the number of infeasible nodes |
| nodeinfeasible | array to store whether the fixing of a node was detected to be infeasible |
| sccvars | array with all nontrivial strongly connected components in the graph |
| sccstarts | start indices of SCCs in sccvars array; one additional entry at the end to give length of used part of sccvars array |
| nsccs | pointer to store number of strongly connected components |
| infeasible | pointer to store whether an infeasibility was detected |
| nfixedvars | pointer to number of fixed variables, increment when fixing another one |
| naggrvars | pointer to number of aggregated variables, increment when aggregating another one |
| result | pointer to store result of the call |
Definition at line 2591 of file prop_vbounds.c.
References FALSE, getVarIndex, isIndexLowerbound, SCIP_Bool, SCIP_CALL, SCIP_DECL_PROPPRESOL(), SCIP_OKAY, SCIP_SUCCESS, SCIPaggregateVars(), SCIPdebugMsg, SCIPfixVar(), and SCIPvarGetName().
Referenced by tarjan().
|
static |
presolving method of propagator: search for strongly connected components in the implication graph and aggregate all variables within a component; additionally, identifies infeasible variable assignments as a side product if a path from x=1 to x=0 (or vice versa) is found or x=1 implies both y=0 and y=1 The identification of such assignments depends on the order in which variable bounds are processed; therefore, we are doing a second run with the bounds processed in (almost) topological order.
Definition at line 2710 of file prop_vbounds.c.
Referenced by applyFixingsAndAggregations().
|
static |
execution method of propagator
Definition at line 2923 of file prop_vbounds.c.
|
static |
propagation conflict resolving method of propagator
Definition at line 2939 of file prop_vbounds.c.
|
static |
execution method of bound change event handler
Definition at line 3018 of file prop_vbounds.c.