Detailed Description
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
- 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.
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.
#include "blockmemshell/memory.h"
#include "scip/prop_vbounds.h"
#include "scip/pub_event.h"
#include "scip/pub_implics.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_prop.h"
#include "scip/pub_var.h"
#include "scip/scip_conflict.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_prop.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.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 |
#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) |
SCIP_RETCODE | SCIPincludePropVbounds (SCIP *scip) |
SCIP_Bool | SCIPisPropagatedVbounds (SCIP *scip) |
SCIP_RETCODE | SCIPexecPropVbounds (SCIP *scip, 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) |
Macro Definition Documentation
◆ PROP_NAME
#define PROP_NAME "vbounds" |
Definition at line 111 of file prop_vbounds.c.
Referenced by SCIPexecPropVbounds(), SCIPincludePropVbounds(), and SCIPisPropagatedVbounds().
◆ PROP_DESC
#define PROP_DESC "propagates variable upper and lower bounds" |
Definition at line 112 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ PROP_TIMING
#define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 113 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ PROP_PRIORITY
#define PROP_PRIORITY 3000000 |
propagator priority
Definition at line 114 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ PROP_FREQ
#define PROP_FREQ 1 |
propagator frequency
Definition at line 115 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 116 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ PROP_PRESOL_PRIORITY
#define PROP_PRESOL_PRIORITY -90000 |
priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers
Definition at line 118 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ PROP_PRESOLTIMING
#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM | SCIP_PRESOLTIMING_EXHAUSTIVE |
Definition at line 119 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ PROP_PRESOL_MAXROUNDS
#define PROP_PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 120 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ EVENTHDLR_NAME
#define EVENTHDLR_NAME "vbounds" |
Definition at line 130 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ EVENTHDLR_DESC
#define EVENTHDLR_DESC "bound change event handler for for vbounds propagator" |
Definition at line 131 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 140 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ DEFAULT_USEIMPLICS
#define DEFAULT_USEIMPLICS FALSE |
should implications be propagated?
Definition at line 141 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ DEFAULT_USECLIQUES
#define DEFAULT_USECLIQUES FALSE |
should cliques be propagated?
Definition at line 142 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ DEFAULT_USEVBOUNDS
#define DEFAULT_USEVBOUNDS TRUE |
should variable bounds be propagated?
Definition at line 143 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 144 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 145 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 146 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ DEFAULT_MINNEWCLIQUES
#define DEFAULT_MINNEWCLIQUES 0.1 |
minimum number of new cliques to trigger another clique table analysis
Definition at line 147 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ DEFAULT_MAXCLIQUESMEDIUM
#define DEFAULT_MAXCLIQUESMEDIUM 50.0 |
maximum number of cliques per variable to run clique table analysis in medium presolving
Definition at line 148 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ DEFAULT_MAXCLIQUESEXHAUSTIVE
#define DEFAULT_MAXCLIQUESEXHAUSTIVE 100.0 |
maximum number of cliques per variable to run clique table analysis in exhaustive presolving
Definition at line 151 of file prop_vbounds.c.
Referenced by SCIPincludePropVbounds().
◆ getLbIndex
#define getLbIndex | ( | idx | ) | (2*(idx)) |
Definition at line 168 of file prop_vbounds.c.
Referenced by tarjan(), and varGetLbIndex().
◆ getUbIndex
#define getUbIndex | ( | idx | ) | (2*(idx)+1) |
Definition at line 169 of file prop_vbounds.c.
Referenced by tarjan(), and varGetUbIndex().
◆ getVarIndex
#define getVarIndex | ( | idx | ) | ((idx)/2) |
Definition at line 170 of file prop_vbounds.c.
Referenced by applyFixingsAndAggregations(), catchEvents(), dfs(), dropEvents(), extractCycle(), initData(), propagateVbounds(), and tarjan().
◆ getBoundtype
#define getBoundtype | ( | idx | ) | (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER) |
Definition at line 171 of file prop_vbounds.c.
Referenced by initData(), and propagateVbounds().
◆ isIndexLowerbound
#define isIndexLowerbound | ( | idx | ) | ((idx) % 2 == 0) |
Definition at line 172 of file prop_vbounds.c.
Referenced by applyFixingsAndAggregations(), catchEvents(), dfs(), dropEvents(), extractCycle(), initData(), propagateVbounds(), and tarjan().
◆ getBoundString
#define getBoundString | ( | lower | ) | ((lower) ? "lb" : "ub") |
Definition at line 173 of file prop_vbounds.c.
◆ getBoundtypeString
#define getBoundtypeString | ( | type | ) | ((type) == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper") |
Definition at line 174 of file prop_vbounds.c.
Referenced by propagateVbounds(), resolvePropagation(), tightenVarLb(), and tightenVarUb().
◆ indexGetBoundString
#define indexGetBoundString | ( | idx | ) | (getBoundString(isIndexLowerbound(idx))) |
Definition at line 175 of file prop_vbounds.c.
Referenced by dfs(), extractCycle(), and tarjan().
◆ getOtherBoundIndex
#define getOtherBoundIndex | ( | idx | ) | ((idx) + 1 - 2 * ((idx) % 2)) |
Definition at line 176 of file prop_vbounds.c.
Referenced by dfs(), extractCycle(), and tarjan().
◆ INITMEMSIZE
#define INITMEMSIZE 5 |
Definition at line 462 of file prop_vbounds.c.
Referenced by addVbound().
◆ VISITED
#define VISITED 1 |
Definition at line 805 of file prop_vbounds.c.
Referenced by dfs().
◆ ACTIVE
#define ACTIVE 2 |
Definition at line 806 of file prop_vbounds.c.
Referenced by dfs().
Typedef Documentation
◆ INFERINFO
typedef struct InferInfo INFERINFO |
Definition at line 237 of file prop_vbounds.c.
Function Documentation
◆ intToInferInfo()
|
static |
converts an integer into an inference information
- Parameters
-
i integer to convert
Definition at line 241 of file prop_vbounds.c.
References inferInfoToInt().
◆ inferInfoToInt()
|
static |
converts an inference information into an int
- Parameters
-
inferinfo inference information to convert
Definition at line 254 of file prop_vbounds.c.
References inferInfoGetBoundtype().
Referenced by intToInferInfo(), tightenVarLb(), and tightenVarUb().
◆ inferInfoGetBoundtype()
|
static |
returns the propagation rule stored in the inference information
- Parameters
-
inferinfo inference information to convert
Definition at line 263 of file prop_vbounds.c.
References inferInfoGetPos(), SCIP_BOUNDTYPE_LOWER, and SCIP_BOUNDTYPE_UPPER.
Referenced by inferInfoToInt().
◆ inferInfoGetPos()
|
static |
returns the position stored in the inference information
- Parameters
-
inferinfo inference information to convert
Definition at line 274 of file prop_vbounds.c.
References getInferInfo().
Referenced by inferInfoGetBoundtype().
◆ getInferInfo()
|
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 283 of file prop_vbounds.c.
References SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, and varGetLbIndex().
Referenced by inferInfoGetPos(), tightenVarLb(), and tightenVarUb().
◆ varGetLbIndex()
|
static |
- Parameters
-
propdata propagator data var variable to get the index for
Definition at line 305 of file prop_vbounds.c.
References getLbIndex, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and varGetUbIndex().
Referenced by dfs(), extractCycle(), getInferInfo(), initData(), tightenVarLb(), and tightenVarUb().
◆ varGetUbIndex()
|
static |
- Parameters
-
propdata propagator data var variable to get the index for
Definition at line 322 of file prop_vbounds.c.
References getUbIndex, resetPropdata(), SCIPhashmapExists(), and SCIPhashmapGetImageInt().
Referenced by dfs(), extractCycle(), initData(), tightenVarLb(), tightenVarUb(), and varGetLbIndex().
◆ resetPropdata()
|
static |
reset propagation data
- Parameters
-
propdata propagator data
Definition at line 339 of file prop_vbounds.c.
References catchEvents(), FALSE, and NULL.
Referenced by SCIPincludePropVbounds(), and varGetUbIndex().
◆ catchEvents()
|
static |
catches events for variables
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 357 of file prop_vbounds.c.
References dropEvents(), 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(), and resetPropdata().
◆ dropEvents()
|
static |
drops events for variables
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 416 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 catchEvents().
◆ addVbound()
|
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 466 of file prop_vbounds.c.
References INITMEMSIZE, NULL, SCIP_CALL, SCIP_DECL_SORTPTRCOMP(), SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocMemoryArray.
Referenced by initData().
◆ SCIP_DECL_SORTPTRCOMP()
|
static |
comparison method for two indices in the topoorder array, preferring higher indices because the order is reverse topological
Definition at line 513 of file prop_vbounds.c.
Referenced by addVbound().
◆ extractCycle()
|
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 525 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 |
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 809 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(), topologicalSort(), TRUE, varGetLbIndex(), varGetUbIndex(), and VISITED.
Referenced by topologicalSort().
◆ topologicalSort()
|
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 1133 of file prop_vbounds.c.
References dfs(), initData(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocClearBufferArray, and SCIPfreeBufferArray.
Referenced by dfs(), and initData().
◆ initData()
|
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 1180 of file prop_vbounds.c.
References addVbound(), BMSclearMemoryArray, catchEvents(), FALSE, getBoundtype, getVarIndex, isIndexLowerbound, NULL, resolvePropagation(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPgetNVars(), SCIPgetProbName(), SCIPgetProbvarSum(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapInsertInt(), 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().
◆ resolvePropagation()
|
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 1351 of file prop_vbounds.c.
References getBoundtypeString, NULL, 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().
◆ relaxVbdvar()
|
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 1387 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().
◆ computeRelaxedLowerbound()
|
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 1411 of file prop_vbounds.c.
References analyzeConflictLowerbound(), SCIP_Real, SCIPadjustedVarLb(), SCIPfeastol(), SCIPgetHugeValue(), SCIPisEQ(), and SCIPvarIsIntegral().
Referenced by analyzeConflictLowerbound(), and relaxVbdvar().
◆ analyzeConflictLowerbound()
|
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 1441 of file prop_vbounds.c.
References computeRelaxedLowerbound(), computeRelaxedUpperbound(), 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 computeRelaxedLowerbound(), and tightenVarLb().
◆ computeRelaxedUpperbound()
|
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 1526 of file prop_vbounds.c.
References analyzeConflictUpperbound(), SCIP_Real, SCIPadjustedVarUb(), SCIPfeastol(), SCIPgetHugeValue(), SCIPisEQ(), and SCIPvarIsIntegral().
Referenced by analyzeConflictLowerbound(), and analyzeConflictUpperbound().
◆ analyzeConflictUpperbound()
|
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 1556 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(), tightenVarLb(), and TRUE.
Referenced by computeRelaxedUpperbound(), and tightenVarUb().
◆ tightenVarLb()
|
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 1640 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(), tightenVarUb(), TRUE, varGetLbIndex(), and varGetUbIndex().
Referenced by analyzeConflictUpperbound(), and propagateVbounds().
◆ tightenVarUb()
|
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 1724 of file prop_vbounds.c.
References analyzeConflictUpperbound(), FALSE, getBoundtypeString, getInferInfo(), inferInfoToInt(), NULL, 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().
◆ propagateVbounds()
|
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 1808 of file prop_vbounds.c.
References FALSE, getBoundtype, getBoundtypeString, getVarIndex, initData(), isIndexLowerbound, NULL, REALABS, 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, SCIPallocBufferArray, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetStage(), SCIPinRepropagation(), SCIPisEQ(), SCIPisInfinity(), SCIPpqueueFind(), 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().
◆ SCIP_DECL_PROPCOPY()
|
static |
copy method for propagator plugins (called when SCIP copies plugins)
Definition at line 2125 of file prop_vbounds.c.
Referenced by propagateVbounds().
◆ SCIP_DECL_PROPFREE()
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 2139 of file prop_vbounds.c.
◆ SCIP_DECL_PROPINITPRE()
|
static |
presolving initialization method of propagator (called when presolving is about to begin)
Definition at line 2154 of file prop_vbounds.c.
◆ SCIP_DECL_PROPEXITSOL()
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 2168 of file prop_vbounds.c.
◆ tarjan()
|
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.
- Parameters
-
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 2235 of file prop_vbounds.c.
References applyFixingsAndAggregations(), FALSE, getBoundString, getLbIndex, getOtherBoundIndex, getUbIndex, getVarIndex, indexGetBoundString, isIndexLowerbound, NULL, SCIP_Bool, SCIP_OKAY, SCIPcliqueGetIndex(), SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPvarGetCliques(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarIsActive(), and TRUE.
◆ applyFixingsAndAggregations()
|
static |
apply fixings and aggregations found by the clique graph analysis
- Parameters
-
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 2657 of file prop_vbounds.c.
References FALSE, getVarIndex, isIndexLowerbound, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_PROPPRESOL(), SCIP_OKAY, SCIP_SUCCESS, SCIPaggregateVars(), SCIPdebugMsg, SCIPfixVar(), and SCIPvarGetName().
Referenced by tarjan().
◆ SCIP_DECL_PROPPRESOL()
|
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 2776 of file prop_vbounds.c.
Referenced by applyFixingsAndAggregations().
◆ SCIP_DECL_PROPEXEC()
|
static |
execution method of propagator
Definition at line 2987 of file prop_vbounds.c.
◆ SCIP_DECL_PROPRESPROP()
|
static |
propagation conflict resolving method of propagator
Definition at line 3002 of file prop_vbounds.c.
◆ SCIP_DECL_EVENTEXEC()
|
static |
execution method of bound change event handler
Definition at line 3081 of file prop_vbounds.c.