Detailed Description

optimization-based bound tightening propagator

Author: Stefan Weltge

Definition in file prop_obbt.c.

#include <assert.h>
#include <string.h>
#include "scip/prop_obbt.h"
#include "scip/prop_genvbounds.h"
#include "scip/debug.h"

Go to the source code of this file.

Macros
#define	PROP_NAME "obbt"

#define	PROP_DESC "optimization-based bound tightening propagator"

#define	PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP

#define	PROP_PRIORITY -1000000

#define	PROP_FREQ 0

#define	PROP_DELAY TRUE

#define	DEFAULT_CREATE_GENVBOUNDS TRUE

#define	DEFAULT_FILTERING_NORM TRUE

#define	DEFAULT_APPLY_FILTERROUNDS FALSE

#define	DEFAULT_DUALFEASTOL 1e-9

#define	DEFAULT_CONDITIONLIMIT -1.0

#define	DEFAULT_FILTERING_MIN 2

#define	DEFAULT_ITLIMITFACTOR 5.0

#define	DEFAULT_MAXLOOKAHEAD 3

#define	OBBT_SCOREBASE 5

#define	GENVBOUND_PROP_NAME "genvbounds"

Typedefs
typedef struct Bound	BOUND

typedef struct BoundGroup	BOUNDGROUP

Functions
static SCIP_RETCODE	solveLP (SCIP scip, int itlimit, SCIP_Bool error, SCIP_Bool *optimal)

static SCIP_RETCODE	addObjCutoff (SCIP scip, SCIP_PROPDATA propdata)

static SCIP_Bool	varIsFixedLocal (SCIP scip, SCIP_VAR var)

static int	getIterationsLeft (SCIP *scip, SCIP_Longint nolditerations, SCIP_Longint itlimit)

static SCIP_Real	getFilterCoef (SCIP scip, SCIP_PROPDATA propdata, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype)

static SCIP_RETCODE	filterExistingLP (SCIP scip, SCIP_PROPDATA propdata, int *nfiltered)

static SCIP_RETCODE	filterRound (SCIP scip, SCIP_PROPDATA propdata, int itlimit, int *nfiltered)

static SCIP_RETCODE	filterBounds (SCIP scip, SCIP_PROPDATA propdata, SCIP_Longint itlimit)

static SCIP_RETCODE	applyBoundChgs (SCIP scip, SCIP_PROPDATA propdata, SCIP_RESULT *result)

static SCIP_RETCODE	tightenBoundDive (SCIP scip, BOUND bound, SCIP_Real newval, SCIP_Bool *tightened)

static SCIP_RETCODE	createGenVBound (SCIP scip, SCIP_PROPDATA propdata, BOUND *bound)

static SCIP_RETCODE	findNewBounds (SCIP scip, SCIP_PROPDATA propdata, SCIP_Longint itlimit)

static SCIP_RETCODE	applyObbt (SCIP scip, SCIP_PROPDATA propdata, SCIP_Longint itlimit, SCIP_RESULT *result)

static unsigned int	getScore (SCIP scip, BOUND bound, int nlcount, int maxnlcount)

static	SCIP_DECL_SORTPTRCOMP (compBounds)

static SCIP_RETCODE	createGroups (SCIP_PROPDATA *propdata)

static SCIP_Bool	varIsInteresting (SCIP scip, SCIP_VAR var, int nlcount)

static SCIP_RETCODE	initBounds (SCIP scip, SCIP_PROPDATA propdata)

static	SCIP_DECL_PROPINITSOL (propInitsolObbt)

static	SCIP_DECL_PROPEXEC (propExecObbt)

static	SCIP_DECL_PROPRESPROP (propRespropObbt)

static	SCIP_DECL_PROPEXITSOL (propExitsolObbt)

static	SCIP_DECL_PROPFREE (propFreeObbt)

SCIP_RETCODE	SCIPincludePropObbt (SCIP *scip)

Macro Definition Documentation

#define PROP_NAME "obbt"

Definition at line 44 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPEXEC(), SCIP_DECL_PROPEXITSOL(), SCIP_DECL_PROPFREE(), SCIP_DECL_PROPINITSOL(), and SCIPincludePropObbt().

#define PROP_DESC "optimization-based bound tightening propagator"

Definition at line 45 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 46 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define PROP_PRIORITY -1000000

propagator priority

Definition at line 47 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define PROP_FREQ 0

propagator frequency

Definition at line 48 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define PROP_DELAY TRUE

should propagation method be delayed, if other propagators found reductions?

Definition at line 49 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define DEFAULT_CREATE_GENVBOUNDS TRUE

should obbt try to provide genvbounds if possible?

Definition at line 51 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define DEFAULT_FILTERING_NORM TRUE

should coefficients in filtering be normalized w.r.t. the domains sizes?

Definition at line 52 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define DEFAULT_APPLY_FILTERROUNDS FALSE

try to filter bounds in so-called filter rounds by solving auxiliary LPs?

Definition at line 54 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define DEFAULT_DUALFEASTOL 1e-9

feasibility tolerance for reduced costs used in obbt; this value is used if SCIP's dual feastol is greater

Definition at line 56 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define DEFAULT_CONDITIONLIMIT -1.0

maximum condition limit used in LP solver (-1.0: no limit)

Definition at line 58 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define DEFAULT_FILTERING_MIN 2

minimal number of filtered bounds to apply another filter round

Definition at line 59 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define DEFAULT_ITLIMITFACTOR 5.0

multiple of root node LP iterations used as total LP iteration limit for obbt (<= 0: no limit )

Definition at line 61 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define DEFAULT_MAXLOOKAHEAD 3

maximal number of bounds evaluated without success per group (-1: no limit)

Definition at line 63 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

#define OBBT_SCOREBASE 5

base that is used to calculate a bounds score value

Definition at line 66 of file prop_obbt.c.

Referenced by getScore().

#define GENVBOUND_PROP_NAME "genvbounds"

Definition at line 67 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPINITSOL().

Typedef Documentation

typedef struct Bound BOUND

Definition at line 84 of file prop_obbt.c.

typedef struct BoundGroup BOUNDGROUP

Definition at line 92 of file prop_obbt.c.

Function Documentation

static SCIP_RETCODE solveLP	(	SCIP *	scip,
		int	itlimit,
		SCIP_Bool *	error,
		SCIP_Bool *	optimal
	)

static

solves the LP and handles errors

Parameters

scip	SCIP data structure
itlimit	maximal number of LP iterations to perform, or -1 for no limit
error	pointer to store whether an unresolved LP error occurred
optimal	was the LP solved to optimalilty?

Definition at line 125 of file prop_obbt.c.

References FALSE, NULL, SCIP_LPSOLSTAT_ERROR, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_LPSOLSTAT_NOTSOLVED, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_TIMELIMIT, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIPdebugMessage, SCIPgetLPSolstat(), SCIPsolveDiveLP(), SCIPwarningMessage(), and TRUE.

Referenced by filterRound(), and findNewBounds().

static SCIP_RETCODE addObjCutoff	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata
	)

static

adds the objective cutoff to the LP; must be in diving mode

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator

Definition at line 196 of file prop_obbt.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddRowDive(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowUnspec(), SCIPdebugMessage, SCIPflushRowExtensions(), SCIPgetCutoffbound(), SCIPgetVarsData(), SCIPinDive(), SCIPinfinity(), SCIPisInfinity(), SCIProwIsInLP(), SCIPsnprintf(), and SCIPvarGetObj().

Referenced by applyObbt().

static SCIP_Bool varIsFixedLocal	(	SCIP *	scip,
		SCIP_VAR *	var
	)

static

determines, whether a variable is already locally fixed

Parameters

scip	SCIP data structure
var	variable to check

Definition at line 246 of file prop_obbt.c.

References SCIPisFeasEQ(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by applyObbt(), findNewBounds(), getFilterCoef(), and varIsInteresting().

static int getIterationsLeft	(	SCIP *	scip,
		SCIP_Longint	nolditerations,
		SCIP_Longint	itlimit
	)

static

returns number of LP iterations left (-1: no limit )

Parameters

scip	SCIP data structure
nolditerations	iterations count at the beginning of the corresponding function
itlimit	LP iteration limit (-1: no limit)

Definition at line 256 of file prop_obbt.c.

References MAX, MIN, NULL, SCIP_Longint, SCIPdebugMessage, and SCIPgetNLPIterations().

Referenced by filterBounds(), and findNewBounds().

static SCIP_Real getFilterCoef	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_VAR *	var,
		SCIP_BOUNDTYPE	boundtype
	)

static

returns the objective coefficient for a variable's bound that will be chosen during filtering

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator
var	variable
boundtype	boundtype to be filtered?

Definition at line 286 of file prop_obbt.c.

References NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_Real, SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and varIsFixedLocal().

Referenced by filterBounds().

static SCIP_RETCODE filterExistingLP	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		int *	nfiltered
	)

static

trying to filter some bounds using the existing LP solution

Parameters

scip	original SCIP data structure
propdata	data of the obbt propagator
nfiltered	how many bounds were filtered this round?

Definition at line 331 of file prop_obbt.c.

References Bound::boundtype, Bound::filtered, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPgetLPSolstat(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetUbLocal(), TRUE, and Bound::var.

Referenced by applyObbt(), and findNewBounds().

static SCIP_RETCODE filterRound	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		int	itlimit,
		int *	nfiltered
	)

static

enforces one round of filtering

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator
itlimit	LP iteration limit (-1: no limit)
nfiltered	how many bounds were filtered this round

Definition at line 385 of file prop_obbt.c.

References Bound::boundtype, Bound::filtered, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObjDive(), SCIPdebugMessage, SCIPgetVarObjDive(), SCIPgetVarsData(), SCIPinDive(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisNegative(), SCIPisPositive(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetUbLocal(), solveLP(), TRUE, and Bound::var.

Referenced by filterBounds().

static SCIP_RETCODE filterBounds	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_Longint	itlimit
	)

static

filter some bounds that are not improvable by solving auxiliary LPs

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator
itlimit	LP iteration limit (-1: no limit)

Definition at line 468 of file prop_obbt.c.

References filterRound(), getFilterCoef(), getIterationsLeft(), NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPchgVarObjDive(), SCIPdebugMessage, SCIPgetNLPIterations(), SCIPgetVarsData(), and SCIPinDive().

Referenced by applyObbt().

static SCIP_RETCODE applyBoundChgs	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_RESULT *	result
	)

static

applies possible bound changes that were found

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator
result	result pointer

Definition at line 557 of file prop_obbt.c.

References Bound::boundtype, FALSE, Bound::found, Bound::newval, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPdebug, SCIPdebugMessage, SCIPinDive(), SCIPtightenVarLb(), SCIPtightenVarUb(), and Bound::var.

Referenced by applyObbt().

static SCIP_RETCODE tightenBoundDive	(	SCIP *	scip,
		BOUND *	bound,
		SCIP_Real	newval,
		SCIP_Bool *	tightened
	)

static

tries to tighten a bound in diving mode

Parameters

scip	SCIP data structure
bound	bound that could be tightened
newval	new bound value
tightened	was tightening successful?

Definition at line 620 of file prop_obbt.c.

References Bound::boundtype, FALSE, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPchgVarLbDive(), SCIPchgVarUbDive(), SCIPfloor(), SCIPgetVarLbDive(), SCIPgetVarUbDive(), SCIPinDive(), SCIPisLbBetter(), SCIPisUbBetter(), SCIPvarIsIntegral(), TRUE, and Bound::var.

Referenced by findNewBounds().

static SCIP_RETCODE createGenVBound	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		BOUND *	bound
	)

static

creates a genvbound if the dual LP solution provides such information

Consider the problem

min { +/- x_i : obj * x <= z, lb <= Ax <= ub, l <= x <= u },

where z is the current cutoff bound. Let (mu, nu, gamma, alpha, beta) >= 0 be the optimal solution of the dual of problem (P), where the variables correspond to the primal inequalities in the following way:

     Ax >=  lb    <->   mu
    -Ax >= -ub    <->   nu

-obj * x >= -z <-> gamma x >= l <-> alpha -x >= -u <-> beta

Fixing these multipliers, by weak duality, we obtain the inequality

+/- x_i >= lb*mu - ub*nu - z*gamma + l*alpha - u*beta

that holds for all primal feasible points x with objective value at least z. Setting

c = lb*mu - ub*nu, redcost_k = alpha_k - beta_k

we obtain the inequality

+/- x_i >= sum ( redcost_k * x_k ) + (-gamma) * cutoff_bound + c,

that holds for all primal feasible points with objective value at least cutoff_bound. Therefore, the latter inequality can be added as a generalized variable bound.

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator
bound	bound of x_i

Definition at line 710 of file prop_obbt.c.

References Bound::boundtype, NULL, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, SCIPgenVBoundAdd(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetVarLbDive(), SCIPgetVarRedcost(), SCIPgetVarsData(), SCIPgetVarUbDive(), SCIPinDive(), SCIPisInfinity(), SCIPisPositive(), SCIPisZero(), SCIProwGetDualsol(), SCIPvarGetName(), and Bound::var.

Referenced by findNewBounds().

static SCIP_RETCODE findNewBounds	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_Longint	itlimit
	)

static

tries to find tighter values for bounds and stores them in the bound data structure

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator
itlimit	LP iteration limit (-1: no limit)

Definition at line 850 of file prop_obbt.c.

References BMSclearMemoryArray, Bound::boundtype, createGenVBound(), FALSE, Bound::filtered, filterExistingLP(), BoundGroup::firstbdindex, Bound::found, getIterationsLeft(), BoundGroup::nbounds, Bound::newval, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPallocBufferArray, SCIPchgVarObjDive(), SCIPdebugCheckLbGlobal, SCIPdebugCheckUbGlobal, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetDepth(), SCIPgetNLPIterations(), SCIPgetVarsData(), SCIPinDive(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbLocal(), solveLP(), tightenBoundDive(), TRUE, Bound::var, and varIsFixedLocal().

Referenced by applyObbt().

static SCIP_RETCODE applyObbt	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_Longint	itlimit,
		SCIP_RESULT *	result
	)

static

main function of obbt

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator
itlimit	LP iteration limit (-1: no limit)
result	result pointer

Definition at line 1009 of file prop_obbt.c.

References addObjCutoff(), applyBoundChgs(), FALSE, filterBounds(), filterExistingLP(), findNewBounds(), MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPchgDualfeastol(), SCIPdebugMessage, SCIPdualfeastol(), SCIPendDive(), SCIPgetNLPIterations(), SCIPgetRealParam(), SCIPreleaseRow(), SCIProwIsInLP(), SCIPsetRealParam(), SCIPstartDive(), SCIPwarningMessage(), and varIsFixedLocal().

Referenced by SCIP_DECL_PROPEXEC().

static unsigned int getScore	(	SCIP *	scip,
		BOUND *	bound,
		int	nlcount,
		int	maxnlcount
	)

static

computes the score of a bound

Parameters

scip	SCIP data structure
bound	pointer of bound
nlcount	number of nonlinear constraints containing the bounds variable
maxnlcount	maximal number of nonlinear constraints a variable appears in

Definition at line 1108 of file prop_obbt.c.

References Bound::boundtype, NULL, OBBT_SCOREBASE, SCIP_BOUNDTYPE_UPPER, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPvarGetType(), and Bound::var.

Referenced by initBounds().

static SCIP_DECL_SORTPTRCOMP ( compBounds )

static

comparison method for two bounds w.r.t. their scores

Definition at line 1151 of file prop_obbt.c.

References Bound::score.

static SCIP_RETCODE createGroups ( SCIP_PROPDATA * propdata )

static

creates groups for the bounds array

Parameters