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)

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)

◆ PROP_NAME

 #define PROP_NAME   "vbounds"

◆ PROP_DESC

 #define PROP_DESC   "propagates variable upper and lower bounds"

Definition at line 101 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ PROP_TIMING

 #define PROP_TIMING   SCIP_PROPTIMING_BEFORELP | SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 102 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ PROP_PRIORITY

 #define PROP_PRIORITY   3000000

propagator priority

Definition at line 103 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ PROP_FREQ

 #define PROP_FREQ   1

propagator frequency

Definition at line 104 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 105 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 107 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ PROP_PRESOLTIMING

 #define PROP_PRESOLTIMING   SCIP_PRESOLTIMING_MEDIUM | SCIP_PRESOLTIMING_EXHAUSTIVE

Definition at line 108 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 109 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ EVENTHDLR_NAME

 #define EVENTHDLR_NAME   "vbounds"

Definition at line 119 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ EVENTHDLR_DESC

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

Definition at line 120 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 129 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ DEFAULT_USEIMPLICS

 #define DEFAULT_USEIMPLICS   FALSE

should implications be propagated?

Definition at line 130 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ DEFAULT_USECLIQUES

 #define DEFAULT_USECLIQUES   FALSE

should cliques be propagated?

Definition at line 131 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ DEFAULT_USEVBOUNDS

 #define DEFAULT_USEVBOUNDS   TRUE

should variable bounds be propagated?

Definition at line 132 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 133 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 134 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 135 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 136 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 137 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 140 of file prop_vbounds.c.

Referenced by SCIPincludePropVbounds().

◆ getLbIndex

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

Definition at line 157 of file prop_vbounds.c.

Referenced by tarjan(), and varGetLbIndex().

◆ getUbIndex

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

Definition at line 158 of file prop_vbounds.c.

Referenced by tarjan(), and varGetUbIndex().

◆ getVarIndex

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

Definition at line 159 of file prop_vbounds.c.

◆ getBoundtype

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

Definition at line 160 of file prop_vbounds.c.

Referenced by initData(), and propagateVbounds().

◆ isIndexLowerbound

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

Definition at line 161 of file prop_vbounds.c.

◆ getBoundString

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

Definition at line 162 of file prop_vbounds.c.

Referenced by dfs(), and tarjan().

◆ getBoundtypeString

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

Definition at line 163 of file prop_vbounds.c.

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

◆ indexGetBoundString

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

Definition at line 164 of file prop_vbounds.c.

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

◆ getOtherBoundIndex

 #define getOtherBoundIndex ( idx ) ((idx) + 1 - 2 * ((idx) % 2))

Definition at line 165 of file prop_vbounds.c.

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

◆ INITMEMSIZE

 #define INITMEMSIZE   5

Definition at line 442 of file prop_vbounds.c.

◆ VISITED

 #define VISITED   1

Definition at line 785 of file prop_vbounds.c.

Referenced by dfs().

◆ ACTIVE

 #define ACTIVE   2

Definition at line 786 of file prop_vbounds.c.

Referenced by dfs().

◆ INFERINFO

 typedef struct InferInfo INFERINFO

Definition at line 226 of file prop_vbounds.c.

◆ intToInferInfo()

 static INFERINFO intToInferInfo ( int i )
static

converts an integer into an inference information

Parameters
 i integer to convert

Definition at line 230 of file prop_vbounds.c.

References inferInfoToInt().

◆ inferInfoToInt()

 static int inferInfoToInt ( INFERINFO inferinfo )
static

converts an inference information into an int

Parameters
 inferinfo inference information to convert

Definition at line 243 of file prop_vbounds.c.

References inferInfoGetBoundtype().

Referenced by intToInferInfo(), tightenVarLb(), and tightenVarUb().

◆ inferInfoGetBoundtype()

 static SCIP_BOUNDTYPE inferInfoGetBoundtype ( INFERINFO inferinfo )
static

returns the propagation rule stored in the inference information

Parameters
 inferinfo inference information to convert

Definition at line 252 of file prop_vbounds.c.

References inferInfoGetPos(), SCIP_BOUNDTYPE_LOWER, and SCIP_BOUNDTYPE_UPPER.

Referenced by inferInfoToInt().

◆ inferInfoGetPos()

 static int inferInfoGetPos ( INFERINFO inferinfo )
static

returns the position stored in the inference information

Parameters
 inferinfo inference information to convert

Definition at line 263 of file prop_vbounds.c.

References getInferInfo().

Referenced by inferInfoGetBoundtype().

◆ getInferInfo()

 static INFERINFO getInferInfo ( int pos, SCIP_BOUNDTYPE boundtype )
static

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

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

Definition at line 272 of file prop_vbounds.c.

References SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, and varGetLbIndex().

Referenced by inferInfoGetPos(), tightenVarLb(), and tightenVarUb().

◆ varGetLbIndex()

 static int varGetLbIndex ( SCIP_PROPDATA * propdata, SCIP_VAR * var )
static
Parameters
 propdata propagator data var variable to get the index for

Definition at line 295 of file prop_vbounds.c.

References getLbIndex, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and varGetUbIndex().

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

◆ varGetUbIndex()

 static int varGetUbIndex ( SCIP_PROPDATA * propdata, SCIP_VAR * var )
static
Parameters
 propdata propagator data var variable to get the index for

Definition at line 307 of file prop_vbounds.c.

References getUbIndex, resetPropdata(), SCIPhashmapExists(), and SCIPhashmapGetImageInt().

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

◆ resetPropdata()

 static void resetPropdata ( SCIP_PROPDATA * propdata )
static

reset propagation data

Parameters
 propdata propagator data

Definition at line 319 of file prop_vbounds.c.

References catchEvents(), FALSE, and NULL.

Referenced by SCIPincludePropVbounds(), and varGetUbIndex().

◆ catchEvents()

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

catches events for variables

Parameters
 scip SCIP data structure propdata propagator data

Definition at line 337 of file prop_vbounds.c.

Referenced by initData(), and resetPropdata().

◆ dropEvents()

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

drops events for variables

Parameters
 scip SCIP data structure propdata propagator data

Definition at line 396 of file prop_vbounds.c.

Referenced by catchEvents().

 static SCIP_RETCODE addVbound ( SCIP * scip, SCIP_PROPDATA * propdata, int startidx, int endidx, SCIP_Real coef, SCIP_Real constant )
static
Parameters
 scip SCIP data structure propdata propagator data startidx index of bound of variable influencing the other variable endidx index of bound of variable which is influenced coef coefficient in the variable bound constant constant in the variable bound

Definition at line 446 of file prop_vbounds.c.

Referenced by initData().

◆ SCIP_DECL_SORTPTRCOMP()

 static SCIP_DECL_SORTPTRCOMP ( compVarboundIndices )
static

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

Definition at line 493 of file prop_vbounds.c.

◆ extractCycle()

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

Definition at line 505 of file prop_vbounds.c.

Referenced by dfs().

◆ dfs()

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

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

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

Definition at line 789 of file prop_vbounds.c.

Referenced by topologicalSort().

◆ topologicalSort()

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

sort the bounds of variables topologically

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

Definition at line 1113 of file prop_vbounds.c.

Referenced by dfs(), and initData().

◆ initData()

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

initializes the internal data for the variable bounds propagator

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

Definition at line 1160 of file prop_vbounds.c.

Referenced by propagateVbounds(), and topologicalSort().

◆ resolvePropagation()

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

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

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

Definition at line 1331 of file prop_vbounds.c.

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

◆ relaxVbdvar()

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

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

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

Definition at line 1367 of file prop_vbounds.c.

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

◆ computeRelaxedLowerbound()

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

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

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

Definition at line 1391 of file prop_vbounds.c.

Referenced by analyzeConflictLowerbound(), and relaxVbdvar().

◆ analyzeConflictLowerbound()

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

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

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

Definition at line 1421 of file prop_vbounds.c.

Referenced by computeRelaxedLowerbound(), and tightenVarLb().

◆ computeRelaxedUpperbound()

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

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

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

Definition at line 1506 of file prop_vbounds.c.

Referenced by analyzeConflictLowerbound(), and analyzeConflictUpperbound().

◆ analyzeConflictUpperbound()

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

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

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

Definition at line 1536 of file prop_vbounds.c.

Referenced by computeRelaxedUpperbound(), and tightenVarUb().

◆ tightenVarLb()

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

Definition at line 1620 of file prop_vbounds.c.

Referenced by analyzeConflictUpperbound(), and propagateVbounds().

◆ tightenVarUb()

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

Definition at line 1704 of file prop_vbounds.c.

Referenced by propagateVbounds(), and tightenVarLb().

◆ propagateVbounds()

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

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

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

Definition at line 1788 of file prop_vbounds.c.

Referenced by SCIPexecPropVbounds(), and tightenVarUb().

◆ SCIP_DECL_PROPCOPY()

 static SCIP_DECL_PROPCOPY ( propCopyVbounds )
static

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

Definition at line 2073 of file prop_vbounds.c.

Referenced by propagateVbounds().

◆ SCIP_DECL_PROPFREE()

 static SCIP_DECL_PROPFREE ( propFreeVbounds )
static

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

Definition at line 2087 of file prop_vbounds.c.

◆ SCIP_DECL_PROPINITPRE()

 static SCIP_DECL_PROPINITPRE ( propInitpreVbounds )
static

presolving initialization method of propagator (called when presolving is about to begin)

Definition at line 2102 of file prop_vbounds.c.

◆ SCIP_DECL_PROPEXITSOL()

 static SCIP_DECL_PROPEXITSOL ( propExitsolVbounds )
static

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

Definition at line 2116 of file prop_vbounds.c.

◆ tarjan()

 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

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 2183 of file prop_vbounds.c.

◆ applyFixingsAndAggregations()

 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

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 2604 of file prop_vbounds.c.

Referenced by tarjan().

◆ SCIP_DECL_PROPPRESOL()

 static SCIP_DECL_PROPPRESOL ( propPresolVbounds )
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 2723 of file prop_vbounds.c.

Referenced by applyFixingsAndAggregations().

◆ SCIP_DECL_PROPEXEC()

 static SCIP_DECL_PROPEXEC ( propExecVbounds )
static

execution method of propagator

Definition at line 2934 of file prop_vbounds.c.

◆ SCIP_DECL_PROPRESPROP()

 static SCIP_DECL_PROPRESPROP ( propRespropVbounds )
static

propagation conflict resolving method of propagator

Definition at line 2949 of file prop_vbounds.c.

◆ SCIP_DECL_EVENTEXEC()

 static SCIP_DECL_EVENTEXEC ( eventExecVbound )
static

execution method of bound change event handler

Definition at line 3028 of file prop_vbounds.c.