  # SCIP

Solving Constraint Integer Programs

prop_genvbounds.h File Reference

## Detailed Description

generalized variable bounds propagator

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)