Solving Constraint Integer Programs

prop_genvbounds.h File Reference

Detailed Description

generalized variable bounds propagator

Stefan Weltge
Ambros Gleixner

A generalized variable bound is a linear inequality of the form

\[ c \, x_i \geq \sum (a_j \, x_j) + d \cdot \mbox{primal\_bound} + \mbox{const}, \]

where $c$ is either 1 or -1 and $primal\_bound$ is an upper bound on the optimal objective value, which may improve during the solving process. In SCIP, generalized variable bounds are used for providing bounds on the LHS's variable $x_i$. If the above inequality is valid, the following bounds, depending on $x_i$'s coefficient, are also valid:

\[ c = 1 \qquad\Rightarrow\qquad x_i \geq \mbox{minactivity}(\sum a_j \, x_j) + d \cdot \mbox{primal\_bound} + \mbox{const} \]

\[ c = -1 \qquad\Rightarrow\qquad x_i \leq - \mbox{minactivity}(\sum a_j \, x_j) - d \cdot \mbox{primal\_bound} - \mbox{const}. \]

Note that for feasible problems, $d \leq 0$ must hold. If $d < 0$ a decrease of the primal bound causes an improvement of the provided bound. Similarly, if $a_j > 0$ ( $< 0$), a tightened lower (upper) bound of a variable $x_j$ also yields a better bound for $x_i$.

The genvbounds propagator sorts its stored generalized variable bounds topologically in the following order: A generalized variable bound A ( $c\, x_i \geq \ldots$) preceeds a generalized variable bound B if the left-hand side variable of A appears in the right-hand side of B with sign of its coefficient equal to c; i.e., if A is propagated and tightens the corresponding bound of x_i, then the minactivity on the right-hand side of B increases. We assume that this order is acyclic for the generalized variable bounds added. Under this condition, propagating the generalized variable bounds in a topological order ensures that all propagations are found in one round.

Both global and local propagation is applied: If the primal bound improves, generalized variable bounds with a nonzero coefficient d are enforced in order to tighten global bounds using the global variable bounds for computing the minactivity. Independently, the genvbounds propagator catches events SCIP_EVENTTYPE_LBTIGHTENED and SCIP_EVENTTYPE_UBTIGHTENED, i.e., locally tightened bounds of variables that occur in the right-hand sides of generalized variable bounds, in order to perform an efficient local propagation when called.

Definition in file prop_genvbounds.h.

#include "scip/scip.h"

Go to the source code of this file.


SCIP_RETCODE SCIPgenVBoundAdd (SCIP *scip, SCIP_PROP *genvboundprop, SCIP_VAR **vars, SCIP_VAR *var, SCIP_Real *coefs, int ncoefs, SCIP_Real coefprimalbound, SCIP_Real constant, SCIP_BOUNDTYPE boundtype)
SCIP_RETCODE SCIPincludePropGenvbounds (SCIP *scip)

Function Documentation

SCIP_PROP genvboundprop,
SCIP_VAR **  vars,
SCIP_Real coefs,
int  ncoefs,
SCIP_Real  coefprimalbound,
SCIP_Real  constant,
SCIP_BOUNDTYPE  boundtype 

adds a generalized variable bound to the genvbounds propagator; if there is already a genvbound for the bound "boundtype" of variable "var", it will be replaced

scipSCIP data structure
genvboundpropgenvbound propagator
varsarray of RHSs variables
varLHSs variable
coefsarray of coefficients for the RHSs variables
ncoefssize of coefs array
coefprimalboundnonpositive value of the primal bounds multiplier
constantconstant term
boundtypetype of bound provided by the genvbound
SCIP_RETCODE SCIPincludePropGenvbounds ( SCIP scip)

creates the genvbounds propagator and includes it in SCIP

scipSCIP data structure