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/scip.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)

Function Documentation

SCIP_RETCODE SCIPgenVBoundAdd	(	SCIP *	scip,
		SCIP_PROP *	genvboundprop,
		SCIP_VAR **	vars,
		SCIP_VAR *	var,
		SCIP_Real *	coefs,
		int	ncoefs,
		SCIP_Real	coefcutoffbound,
		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

Parameters

scip	SCIP data structure
genvboundprop	genvbound propagator
vars	array of RHSs variables
var	LHSs variable
coefs	array of coefficients for the RHSs variables
ncoefs	size of coefs array
coefcutoffbound	nonpositive value of the cutoff bounds multiplier
constant	constant term
boundtype	type of bound provided by the genvbound

Definition at line 1785 of file prop_genvbounds.c.

References addNewGenVBound(), GenVBound::boundtype, GenVBound::coefs, GenVBound::constant, GenVBound::cutoffcoef, FALSE, getGenVBound(), initPropdata(), GenVBound::ncoefs, NULL, PROP_NAME, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPdebug, SCIPdebugMessage, SCIPduplicateMemoryArray, SCIPfreeMemoryArray, SCIPgetTransObjoffset(), SCIPgetTransObjscale(), SCIPisNegative(), SCIPisPositive(), SCIPpropGetData(), SCIPpropGetName(), SCIPreallocMemoryArray, GenVBound::var, and GenVBound::vars.

Referenced by createGenVBound().

SCIP_RETCODE SCIPincludePropGenvbounds ( SCIP * scip )

creates the genvbounds propagator and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2333 of file prop_genvbounds.c.

References DEFAULT_GLOBAL_PROPAGATION, DEFAULT_PROPAGATE_IN_ROOT_NODE, DEFAULT_SORT, EVENTHDLR_DESC, EVENTHDLR_NAME, NULL, PROP_DELAY, PROP_DESC, PROP_FREQ, PROP_NAME, PROP_PRESOL_DELAY, PROP_PRESOL_MAXROUNDS, PROP_PRESOL_PRIORITY, PROP_PRIORITY, PROP_TIMING, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPallocMemory, SCIPincludeEventhdlrBasic(), SCIPincludePropBasic(), SCIPsetPropExitpre(), SCIPsetPropExitsol(), SCIPsetPropFree(), SCIPsetPropInit(), SCIPsetPropPresol(), SCIPsetPropResprop(), and TRUE.

Referenced by SCIPincludeDefaultPlugins().

SCIP

Detailed Description

Functions

Function Documentation