SCIP
Solving Constraint Integer Programs
prop_vbounds.c File Reference
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.
◆ PROP_DESC
| #define PROP_DESC "propagates variable upper and lower bounds" |
Definition at line 112 of file prop_vbounds.c.
◆ PROP_TIMING
| #define PROP_TIMING SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 113 of file prop_vbounds.c.
◆ PROP_PRIORITY
| #define PROP_PRIORITY 3000000 |
propagator priority
Definition at line 114 of file prop_vbounds.c.
◆ PROP_FREQ
| #define PROP_FREQ 1 |
propagator frequency
Definition at line 115 of file prop_vbounds.c.
◆ 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.
◆ 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.
◆ PROP_PRESOLTIMING
| #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM | SCIP_PRESOLTIMING_EXHAUSTIVE |
Definition at line 119 of file prop_vbounds.c.
◆ PROP_PRESOL_MAXROUNDS
| #define PROP_PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 121 of file prop_vbounds.c.
◆ EVENTHDLR_NAME
| #define EVENTHDLR_NAME "vbounds" |
Definition at line 129 of file prop_vbounds.c.
◆ EVENTHDLR_DESC
| #define EVENTHDLR_DESC "bound change event handler for for vbounds propagator" |
Definition at line 130 of file prop_vbounds.c.
◆ DEFAULT_USEBDWIDENING
| #define DEFAULT_USEBDWIDENING TRUE |
should bound widening be used to initialize conflict analysis?
Definition at line 139 of file prop_vbounds.c.
◆ DEFAULT_USEIMPLICS
| #define DEFAULT_USEIMPLICS FALSE |
should implications be propagated?
Definition at line 140 of file prop_vbounds.c.
◆ DEFAULT_USECLIQUES
| #define DEFAULT_USECLIQUES FALSE |
should cliques be propagated?
Definition at line 141 of file prop_vbounds.c.
◆ DEFAULT_USEVBOUNDS
| #define DEFAULT_USEVBOUNDS TRUE |
should variable bounds be propagated?
Definition at line 142 of file prop_vbounds.c.
◆ DEFAULT_DOTOPOSORT
| #define DEFAULT_DOTOPOSORT TRUE |
should the bounds be topologically sorted in advance?
Definition at line 143 of file prop_vbounds.c.
◆ DEFAULT_SORTCLIQUES
| #define DEFAULT_SORTCLIQUES FALSE |
should cliques be regarded for the topological sort?
Definition at line 144 of file prop_vbounds.c.
◆ DEFAULT_DETECTCYCLES
| #define DEFAULT_DETECTCYCLES FALSE |
should cycles in the variable bound graph be identified?
Definition at line 145 of file prop_vbounds.c.
◆ DEFAULT_MINNEWCLIQUES
| #define DEFAULT_MINNEWCLIQUES 0.1 |
minimum number of new cliques to trigger another clique table analysis
Definition at line 146 of file prop_vbounds.c.
◆ 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.
◆ DEFAULT_MAXCLIQUESEXHAUSTIVE
| #define DEFAULT_MAXCLIQUESEXHAUSTIVE 100.0 |
maximum number of cliques per variable to run clique table analysis in exhaustive presolving
Definition at line 150 of file prop_vbounds.c.
◆ getLbIndex
| #define getLbIndex | ( | idx | ) | (2*(idx)) |
Definition at line 165 of file prop_vbounds.c.
◆ getUbIndex
| #define getUbIndex | ( | idx | ) | (2*(idx)+1) |
Definition at line 166 of file prop_vbounds.c.
◆ getVarIndex
| #define getVarIndex | ( | idx | ) | ((idx)/2) |
Definition at line 167 of file prop_vbounds.c.
◆ getBoundtype
| #define getBoundtype | ( | idx | ) | (((idx) % 2 == 0) ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER) |
Definition at line 168 of file prop_vbounds.c.
◆ isIndexLowerbound
| #define isIndexLowerbound | ( | idx | ) | ((idx) % 2 == 0) |
Definition at line 169 of file prop_vbounds.c.
◆ getBoundString
| #define getBoundString | ( | lower | ) | ((lower) ? "lb" : "ub") |
Definition at line 170 of file prop_vbounds.c.
◆ getBoundtypeString
| #define getBoundtypeString | ( | type | ) | ((type) == SCIP_BOUNDTYPE_LOWER ? "lower" : "upper") |
Definition at line 171 of file prop_vbounds.c.
◆ indexGetBoundString
| #define indexGetBoundString | ( | idx | ) | (getBoundString(isIndexLowerbound(idx))) |
Definition at line 172 of file prop_vbounds.c.
◆ getOtherBoundIndex
| #define getOtherBoundIndex | ( | idx | ) | ((idx) + 1 - 2 * ((idx) % 2)) |
Definition at line 173 of file prop_vbounds.c.
◆ INITMEMSIZE
| #define INITMEMSIZE 5 |
Definition at line 459 of file prop_vbounds.c.
◆ VISITED
| #define VISITED 1 |
Definition at line 802 of file prop_vbounds.c.
◆ ACTIVE
| #define ACTIVE 2 |
Definition at line 803 of file prop_vbounds.c.
Typedef Documentation
◆ INFERINFO
| typedef struct InferInfo INFERINFO |
Definition at line 234 of file prop_vbounds.c.
Function Documentation
◆ intToInferInfo()
|
static |
converts an integer into an inference information
- Parameters
-
i integer to convert
Definition at line 238 of file prop_vbounds.c.
Referenced by SCIP_DECL_PROPRESPROP().
◆ inferInfoToInt()
|
static |
converts an inference information into an int
- Parameters
-
inferinfo inference information to convert
Definition at line 251 of file prop_vbounds.c.
Referenced by tightenVarLb(), and tightenVarUb().
◆ inferInfoGetBoundtype()
|
static |
returns the propagation rule stored in the inference information
- Parameters
-
inferinfo inference information to convert
Definition at line 260 of file prop_vbounds.c.
References SCIP_BOUNDTYPE_LOWER, and SCIP_BOUNDTYPE_UPPER.
Referenced by SCIP_DECL_PROPRESPROP().
◆ inferInfoGetPos()
|
static |
returns the position stored in the inference information
- Parameters
-
inferinfo inference information to convert
Definition at line 271 of file prop_vbounds.c.
Referenced by SCIP_DECL_PROPRESPROP().
◆ 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 280 of file prop_vbounds.c.
References SCIP_BOUNDTYPE_LOWER, and SCIP_BOUNDTYPE_UPPER.
Referenced by tightenVarLb(), and tightenVarUb().
◆ varGetLbIndex()
|
static |
- Parameters
-
propdata propagator data var variable to get the index for
Definition at line 302 of file prop_vbounds.c.
References getLbIndex, SCIPhashmapExists(), and SCIPhashmapGetImageInt().
Referenced by dfs(), extractCycle(), initData(), SCIP_DECL_PROPRESPROP(), tightenVarLb(), and tightenVarUb().
◆ varGetUbIndex()
|
static |
- Parameters
-
propdata propagator data var variable to get the index for
Definition at line 319 of file prop_vbounds.c.
References getUbIndex, SCIPhashmapExists(), and SCIPhashmapGetImageInt().
Referenced by dfs(), extractCycle(), initData(), SCIP_DECL_PROPRESPROP(), tightenVarLb(), and tightenVarUb().
◆ resetPropdata()
|
static |
reset propagation data
- Parameters
-
propdata propagator data
Definition at line 336 of file prop_vbounds.c.
Referenced by SCIP_DECL_PROPEXITSOL(), and SCIPincludePropVbounds().
◆ catchEvents()
|
static |
catches events for variables
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 354 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 |
drops events for variables
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 413 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 |
- 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 463 of file prop_vbounds.c.
References INITMEMSIZE, NULL, SCIP_CALL, 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 510 of file prop_vbounds.c.
◆ 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 522 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 806 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 |
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 1130 of file prop_vbounds.c.
References dfs(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocClearBufferArray, and SCIPfreeBufferArray.
Referenced by 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 1177 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(), SCIPhashmapInsertInt(), 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 |
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 1348 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 |
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 1384 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 |
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 1408 of file prop_vbounds.c.
References SCIP_Real, SCIPadjustedVarLb(), SCIPfeastol(), SCIPgetHugeValue(), SCIPisEQ(), and SCIPvarIsIntegral().
Referenced by analyzeConflictLowerbound(), and SCIP_DECL_PROPRESPROP().
◆ 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 1438 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 |
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 1523 of file prop_vbounds.c.
References SCIP_Real, SCIPadjustedVarUb(), SCIPfeastol(), SCIPgetHugeValue(), SCIPisEQ(), and SCIPvarIsIntegral().
Referenced by analyzeConflictUpperbound(), and SCIP_DECL_PROPRESPROP().
◆ 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 1553 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 |
- 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 1637 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 |
- 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 1721 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 |
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 1805 of file prop_vbounds.c.
References FALSE, getBoundtype, getBoundtypeString, getVarIndex, initData(), isIndexLowerbound, NULL, REALABS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CUTOFF, 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 SCIP_DECL_PROPEXEC(), and SCIPexecPropVbounds().
◆ SCIP_DECL_PROPCOPY()
|
static |
copy method for propagator plugins (called when SCIP copies plugins)
Definition at line 2122 of file prop_vbounds.c.
References NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePropVbounds(), and SCIPpropGetName().
◆ SCIP_DECL_PROPFREE()
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 2136 of file prop_vbounds.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropSetData().
◆ SCIP_DECL_PROPINITPRE()
|
static |
presolving initialization method of propagator (called when presolving is about to begin)
Definition at line 2151 of file prop_vbounds.c.
References NULL, SCIP_OKAY, and SCIPpropGetData().
◆ SCIP_DECL_PROPEXITSOL()
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 2165 of file prop_vbounds.c.
References dropEvents(), NULL, resetPropdata(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPfreeMemoryArray, SCIPhashmapFree(), SCIPpqueueFree(), and SCIPpropGetData().
◆ 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 2232 of file prop_vbounds.c.
References FALSE, getBoundString, getLbIndex, getOtherBoundIndex, getUbIndex, getVarIndex, indexGetBoundString, isIndexLowerbound, MIN, NULL, SCIP_Bool, SCIP_OKAY, SCIPcliqueGetIndex(), SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPvarGetCliques(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarIsActive(), and TRUE.
Referenced by SCIP_DECL_PROPPRESOL().
◆ 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 2654 of file prop_vbounds.c.
References FALSE, getVarIndex, isIndexLowerbound, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_SUCCESS, SCIPaggregateVars(), SCIPdebugMsg, SCIPfixVar(), and SCIPvarGetName().
Referenced by SCIP_DECL_PROPPRESOL().
◆ 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 2773 of file prop_vbounds.c.
References applyFixingsAndAggregations(), BMSclearMemoryArray, FALSE, getLbIndex, getUbIndex, getVarIndex, isIndexLowerbound, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PRESOLTIMING_MEDIUM, SCIP_Shortbool, SCIP_SUCCESS, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPallocClearBufferArray, SCIPcleanupCliques(), SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetNBinVars(), SCIPgetNCliques(), SCIPgetNCliquesCreated(), SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPpropGetData(), SCIPvarGetProbindex(), and tarjan().
◆ SCIP_DECL_PROPEXEC()
|
static |
execution method of propagator
Definition at line 2984 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 |
propagation conflict resolving method of propagator
Definition at line 2999 of file prop_vbounds.c.
References b, 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 |
execution method of bound change event handler
Definition at line 3078 of file prop_vbounds.c.
References getVarIndex, indexGetBoundString, isIndexLowerbound, NULL, SCIP_CALL, SCIP_EVENTTYPE_FORMAT, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPeventGetNewbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPeventhdlrGetData(), SCIPgetNVars(), SCIPpqueueInsert(), SCIPpqueueNElems(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarIsBinary(), and TRUE.