prop_genvbounds.h File Reference

Detailed Description

generalized variable bounds propagator

Author

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/def.h"
#include "scip/type_lp.h"
#include "scip/type_prop.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"
#include "scip/type_var.h"

Go to the source code of this file.

Functions
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)