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)

SCIP

Detailed Description

Functions