Detailed Description

optimization-based bound tightening propagator

Author: Stefan Weltge; Benjamin Mueller

Definition in file prop_obbt.c.

#include "blockmemshell/memory.h"
#include "nlpi/pub_expr.h"
#include "scip/cons_abspower.h"
#include "scip/cons_bivariate.h"
#include "scip/cons_nonlinear.h"
#include "scip/cons_quadratic.h"
#include "scip/intervalarith.h"
#include "scip/prop_genvbounds.h"
#include "scip/prop_obbt.h"
#include "scip/pub_cons.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_nlp.h"
#include "scip/pub_prop.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_prop.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>

Go to the source code of this file.

Data Structures
struct	Bound

struct	BilinBound

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_APPLY_TRIVIALFITLERING TRUE

#define	DEFAULT_GENVBDSDURINGFILTER TRUE

#define	DEFAULT_DUALFEASTOL 1e-9

#define	DEFAULT_CONDITIONLIMIT -1.0

#define	DEFAULT_BOUNDSTREPS 0.001

#define	DEFAULT_FILTERING_MIN 2

#define	DEFAULT_ITLIMITFACTOR 10.0

#define	DEFAULT_MINITLIMIT 5000L

#define	DEFAULT_ONLYNONCONVEXVARS FALSE

#define	DEFAULT_TIGHTINTBOUNDSPROBING TRUE

#define	DEFAULT_TIGHTCONTBOUNDSPROBING FALSE

#define	DEFAULT_ORDERINGALGO 1

#define	OBBT_SCOREBASE 5

#define	GENVBOUND_PROP_NAME "genvbounds"

#define	INTERVALINFTY 1E+43

#define	DEFAULT_SEPARATESOL FALSE

#define	DEFAULT_SEPAMINITER 0

#define	DEFAULT_SEPAMAXITER 10

#define	DEFAULT_GENVBDSDURINGSEPA TRUE

#define	DEFAULT_PROPAGATEFREQ 0

#define	DEFAULT_CREATE_BILININEQS TRUE

#define	DEFAULT_ITLIMITFAC_BILININEQS 3.0

#define	DEFAULT_MINNONCONVEXITY 1e-1

#define	DEFAULT_RANDSEED 149

#define	infty2infty(infty1, infty2, val) ((val) >= (infty1) ? (infty2) : (val))

Typedefs
typedef struct Bound	BOUND

typedef enum Corner	CORNER

typedef struct BilinBound	BILINBOUND

Enumerations
enum	Corner { LEFTBOTTOM = 1, RIGHTBOTTOM = 2, RIGHTTOP = 4, LEFTTOP = 8, FILTERED = 15 }

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 SCIP_RETCODE	setObjProbing (SCIP scip, SCIP_PROPDATA propdata, BOUND *bound, SCIP_Real coef)

static SCIP_Bool	includeVarGenVBound (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	createGenVBound (SCIP scip, SCIP_PROPDATA propdata, BOUND bound, SCIP_Bool found)

static void	exchangeBounds (SCIP_PROPDATA *propdata, int i)

static void	getCorner (SCIP_VAR x, SCIP_VAR y, CORNER corner, SCIP_Real px, SCIP_Real py)

static void	getCorners (SCIP_VAR x, SCIP_VAR y, CORNER corner, SCIP_Real xs, SCIP_Real ys, SCIP_Real xt, SCIP_Real yt)

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

static SCIP_RETCODE	filterRound (SCIP scip, SCIP_PROPDATA propdata, int itlimit, int nfiltered, SCIP_Real objcoefs, int *objcoefsinds, int nobjcoefs)

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	tightenBoundProbing (SCIP scip, BOUND bound, SCIP_Real newval, SCIP_Bool *tightened)

static	SCIP_DECL_SORTPTRCOMP (compBoundsScore)

static	SCIP_DECL_SORTPTRCOMP (compBilinboundsScore)

static	SCIP_DECL_SORTPTRCOMP (compBoundsBoundtype)

static SCIP_RETCODE	sortBounds (SCIP scip, SCIP_PROPDATA propdata)

static SCIP_Real	evalBound (SCIP scip, BOUND bound)

static int	nextBound (SCIP scip, SCIP_PROPDATA propdata, SCIP_Bool convexphase)

static SCIP_RETCODE	applySeparation (SCIP scip, SCIP_PROPDATA propdata, BOUND currbound, SCIP_Longint nleftiterations, SCIP_Bool *success)

static SCIP_RETCODE	findNewBounds (SCIP scip, SCIP_PROPDATA propdata, SCIP_Longint *nleftiterations, SCIP_Bool convexphase)

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

static SCIP_RETCODE	solveBilinearLP (SCIP scip, SCIP_VAR x, SCIP_VAR y, SCIP_Real xs, SCIP_Real ys, SCIP_Real xt, SCIP_Real yt, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Longint iterlim)

static SCIP_RETCODE	applyObbtBilinear (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_Real	getScoreBilinBound (SCIP scip, SCIP_RANDNUMGEN randnumgen, BILINBOUND *bilinbound, int nbilinterms)

static SCIP_RETCODE	countNLRowVarsNonConvexity (SCIP scip, int nlcounts, SCIP_NLROW *nlrow)

static SCIP_RETCODE	getNLPVarsNonConvexity (SCIP scip, int nlcounts)

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

static SCIP_RETCODE	initBounds (SCIP scip, SCIP_PROPDATA propdata)

static	SCIP_DECL_PROPCOPY (propCopyObbt)

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

◆ PROP_NAME

#define PROP_NAME "obbt"

Definition at line 75 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPCOPY().

◆ PROP_DESC

#define PROP_DESC "optimization-based bound tightening propagator"

Definition at line 76 of file prop_obbt.c.

◆ PROP_TIMING

#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 77 of file prop_obbt.c.

◆ PROP_PRIORITY

#define PROP_PRIORITY -1000000

propagator priority

Definition at line 78 of file prop_obbt.c.

◆ PROP_FREQ

#define PROP_FREQ 0

propagator frequency

Definition at line 79 of file prop_obbt.c.

◆ PROP_DELAY

#define PROP_DELAY TRUE

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

Definition at line 80 of file prop_obbt.c.

◆ DEFAULT_CREATE_GENVBOUNDS

#define DEFAULT_CREATE_GENVBOUNDS TRUE

should obbt try to provide genvbounds if possible?

Definition at line 84 of file prop_obbt.c.

◆ DEFAULT_FILTERING_NORM

#define DEFAULT_FILTERING_NORM TRUE

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

Definition at line 85 of file prop_obbt.c.

◆ DEFAULT_APPLY_FILTERROUNDS

#define DEFAULT_APPLY_FILTERROUNDS FALSE

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

Definition at line 88 of file prop_obbt.c.

◆ DEFAULT_APPLY_TRIVIALFITLERING

#define DEFAULT_APPLY_TRIVIALFITLERING TRUE

should obbt try to use the LP solution to filter some bounds?

Definition at line 91 of file prop_obbt.c.

◆ DEFAULT_GENVBDSDURINGFILTER

#define DEFAULT_GENVBDSDURINGFILTER TRUE

try to genrate genvbounds during trivial and aggressive filtering?

Definition at line 92 of file prop_obbt.c.

◆ DEFAULT_DUALFEASTOL

#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 93 of file prop_obbt.c.

◆ DEFAULT_CONDITIONLIMIT

#define DEFAULT_CONDITIONLIMIT -1.0

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

Definition at line 96 of file prop_obbt.c.

◆ DEFAULT_BOUNDSTREPS

#define DEFAULT_BOUNDSTREPS 0.001

minimal relative improve for strengthening bounds

Definition at line 97 of file prop_obbt.c.

◆ DEFAULT_FILTERING_MIN

#define DEFAULT_FILTERING_MIN 2

minimal number of filtered bounds to apply another filter round

Definition at line 98 of file prop_obbt.c.

◆ DEFAULT_ITLIMITFACTOR

#define DEFAULT_ITLIMITFACTOR 10.0

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

Definition at line 101 of file prop_obbt.c.

◆ DEFAULT_MINITLIMIT

#define DEFAULT_MINITLIMIT 5000L

minimum LP iteration limit

Definition at line 104 of file prop_obbt.c.

◆ DEFAULT_ONLYNONCONVEXVARS

#define DEFAULT_ONLYNONCONVEXVARS FALSE

only apply obbt on non-convex variables

Definition at line 105 of file prop_obbt.c.

◆ DEFAULT_TIGHTINTBOUNDSPROBING

#define DEFAULT_TIGHTINTBOUNDSPROBING TRUE

should bounds of integral variables be tightened during the probing mode?

Definition at line 106 of file prop_obbt.c.

◆ DEFAULT_TIGHTCONTBOUNDSPROBING

#define DEFAULT_TIGHTCONTBOUNDSPROBING FALSE

should bounds of continuous variables be tightened during the probing mode?

Definition at line 109 of file prop_obbt.c.

◆ DEFAULT_ORDERINGALGO

#define DEFAULT_ORDERINGALGO 1

which type of ordering algorithm should we use? (0: no, 1: greedy, 2: greedy reverse)

Definition at line 112 of file prop_obbt.c.

◆ OBBT_SCOREBASE

#define OBBT_SCOREBASE 5

base that is used to calculate a bounds score value

Definition at line 115 of file prop_obbt.c.

◆ GENVBOUND_PROP_NAME

#define GENVBOUND_PROP_NAME "genvbounds"

Definition at line 116 of file prop_obbt.c.

◆ INTERVALINFTY

#define INTERVALINFTY 1E+43

value for infinity in interval operations

Definition at line 117 of file prop_obbt.c.

◆ DEFAULT_SEPARATESOL

#define DEFAULT_SEPARATESOL FALSE

should the obbt LP solution be separated? note that that by separating solution OBBT will apply all bound tightenings immediatly

Definition at line 119 of file prop_obbt.c.

◆ DEFAULT_SEPAMINITER

#define DEFAULT_SEPAMINITER 0

minimum number of iteration spend to separate an obbt LP solution

Definition at line 124 of file prop_obbt.c.

◆ DEFAULT_SEPAMAXITER

#define DEFAULT_SEPAMAXITER 10

maximum number of iteration spend to separate an obbt LP solution

Definition at line 125 of file prop_obbt.c.

◆ DEFAULT_GENVBDSDURINGSEPA

#define DEFAULT_GENVBDSDURINGSEPA TRUE

try to create genvbounds during separation process?

Definition at line 126 of file prop_obbt.c.

◆ DEFAULT_PROPAGATEFREQ

#define DEFAULT_PROPAGATEFREQ 0

trigger a propagation round after that many bound tightenings (0: no propagation)

Definition at line 127 of file prop_obbt.c.

◆ DEFAULT_CREATE_BILININEQS

#define DEFAULT_CREATE_BILININEQS TRUE

solve auxiliary LPs in order to find valid inequalities for bilinear terms?

Definition at line 130 of file prop_obbt.c.

◆ DEFAULT_ITLIMITFAC_BILININEQS

#define DEFAULT_ITLIMITFAC_BILININEQS 3.0

multiple of OBBT LP limit used as total LP iteration limit for solving bilinear inequality LPs (< 0 for no limit)

Definition at line 131 of file prop_obbt.c.

◆ DEFAULT_MINNONCONVEXITY

#define DEFAULT_MINNONCONVEXITY 1e-1

minimum nonconvexity for choosing a bilinear term

Definition at line 132 of file prop_obbt.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 149

initial random seed

Definition at line 133 of file prop_obbt.c.

◆ infty2infty

#define infty2infty	(	infty1,
		infty2,
		val
	)	((val) >= (infty1) ? (infty2) : (val))

translate from one value of infinity to another

if val is >= infty1, then give infty2, else give val

Definition at line 140 of file prop_obbt.c.

Typedef Documentation

◆ BOUND

typedef struct Bound BOUND

Definition at line 159 of file prop_obbt.c.

◆ CORNER

typedef enum Corner CORNER

Definition at line 170 of file prop_obbt.c.

◆ BILINBOUND

typedef struct BilinBound BILINBOUND

Definition at line 184 of file prop_obbt.c.

Enumeration Type Documentation

◆ Corner

enum Corner

Enumerator
LEFTBOTTOM
RIGHTBOTTOM
RIGHTTOP
LEFTTOP
FILTERED

Definition at line 162 of file prop_obbt.c.

Function Documentation

◆ solveLP()

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 246 of file prop_obbt.c.

Referenced by filterExistingLP().

◆ addObjCutoff()

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

static

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

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator

Definition at line 318 of file prop_obbt.c.

◆ varIsFixedLocal()

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 368 of file prop_obbt.c.

◆ setObjProbing()

static SCIP_RETCODE setObjProbing	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		BOUND *	bound,
		SCIP_Real	coef
	)

static

sets objective to minimize or maximize a single variable

Definition at line 378 of file prop_obbt.c.

Referenced by filterExistingLP().

◆ includeVarGenVBound()

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

static

determines whether variable should be included in the right-hand side of the generalized variable bound

Parameters

scip	SCIP data structure
var	variable to check

Definition at line 425 of file prop_obbt.c.

◆ getIterationsLeft()

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 452 of file prop_obbt.c.

References Bound::boundtype, getFilterCoef(), MAX, NULL, SCIP_Real, SCIPdebugMsg, and SCIPgetNLPIterations().

◆ getFilterCoef()

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 482 of file prop_obbt.c.

Referenced by getIterationsLeft().

◆ createGenVBound()

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

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
found	pointer to store if we have found a non-trivial genvbound

Definition at line 556 of file prop_obbt.c.

Referenced by filterExistingLP().

◆ exchangeBounds()

static void exchangeBounds	(	SCIP_PROPDATA *	propdata,
		int	i
	)

static

exchange a bound which has been processed and updates the last undone and unfiltered bound index NOTE: this method has to be called after filtering or processing a bound

Parameters

propdata	propagator data
i	bound that was filtered or processed

Definition at line 742 of file prop_obbt.c.

References NULL.

Referenced by filterExistingLP().

◆ getCorner()

static void getCorner	(	SCIP_VAR *	x,
		SCIP_VAR *	y,
		CORNER	corner,
		SCIP_Real *	px,
		SCIP_Real *	py
	)

static

helper function to return a corner of the domain of two variables

Parameters

x	first variable
y	second variable
corner	corner
px	buffer to store point for x
py	buffer to store point for y

Definition at line 765 of file prop_obbt.c.

References FILTERED, getCorners(), LEFTBOTTOM, LEFTTOP, NULL, RIGHTBOTTOM, RIGHTTOP, SCIP_Real, SCIPABORT, SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by filterExistingLP().

◆ getCorners()

static void getCorners	(	SCIP_VAR *	x,
		SCIP_VAR *	y,
		CORNER	corner,
		SCIP_Real *	xs,
		SCIP_Real *	ys,
		SCIP_Real *	xt,
		SCIP_Real *	yt
	)

static

helper function to return the two end points of a diagonal

Parameters

x	first variable
y	second variable
corner	corner
xs	buffer to store start point for x
ys	buffer to store start point for y
xt	buffer to store end point for x
yt	buffer to store end point for y

Definition at line 803 of file prop_obbt.c.

Referenced by getCorner().

◆ filterExistingLP()

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

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?
currbound	bound for which OBBT LP was solved (Note: might be NULL)

Definition at line 845 of file prop_obbt.c.

References bound, Bound::boundtype, createGenVBound(), Bound::done, BilinBound::done, exchangeBounds(), Bound::filtered, FILTERED, BilinBound::filtered, filterRound(), Bound::found, getCorner(), LEFTBOTTOM, LEFTTOP, NULL, REALABS, RIGHTBOTTOM, RIGHTTOP, SCIP_BASESTAT_BASIC, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPchgVarObjProbing(), SCIPcolGetBasisStatus(), SCIPdebug, SCIPdebugMessage, SCIPdebugMsg, SCIPgetDepth(), SCIPgetNVars(), SCIPgetVarObjProbing(), SCIPgetVars(), SCIPinProbing(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), setObjProbing(), solveLP(), TRUE, Bound::var, BilinBound::x, and BilinBound::y.

◆ filterRound()

static SCIP_RETCODE filterRound	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		int	itlimit,
		int *	nfiltered,
		SCIP_Real *	objcoefs,
		int *	objcoefsinds,
		int	nobjcoefs
	)

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
objcoefs	array to store the nontrivial objective coefficients
objcoefsinds	array to store bound indices for which their corresponding variables has a nontrivial objective coefficient
nobjcoefs	number of nontrivial objective coefficients

Definition at line 1011 of file prop_obbt.c.

Referenced by filterExistingLP().

◆ 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 1160 of file prop_obbt.c.

◆ applyBoundChgs()

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 1303 of file prop_obbt.c.

◆ tightenBoundProbing()

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

static

tries to tighten a bound in probing mode

Parameters

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

Definition at line 1370 of file prop_obbt.c.

◆ SCIP_DECL_SORTPTRCOMP() [1/3]

static SCIP_DECL_SORTPTRCOMP ( compBoundsScore )

static

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

Definition at line 1431 of file prop_obbt.c.

◆ SCIP_DECL_SORTPTRCOMP() [2/3]

static SCIP_DECL_SORTPTRCOMP ( compBilinboundsScore )

static

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

Definition at line 1441 of file prop_obbt.c.

◆ SCIP_DECL_SORTPTRCOMP() [3/3]

static SCIP_DECL_SORTPTRCOMP ( compBoundsBoundtype )

static

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

Definition at line 1451 of file prop_obbt.c.

References NULL, SCIP_OKAY, SCIPdebugMsg, and SCIPsortDownPtr().

◆ sortBounds()

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

static

sort the propdata->bounds array with their distance or their boundtype key

Parameters

scip	SCIP data structure
propdata	propagator data

Definition at line 1477 of file prop_obbt.c.

References Bound::boundtype, NULL, REALABS, SCIP_BOUNDTYPE_LOWER, SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetUbLocal(), and Bound::var.

◆ evalBound()

static SCIP_Real evalBound	(	SCIP *	scip,
		BOUND *	bound
	)

static

evaluates a bound for the current LP solution

Definition at line 1493 of file prop_obbt.c.

References NULL, and SCIP_Real.

◆ nextBound()

static int nextBound	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_Bool	convexphase
	)

static

returns the index of the next undone and unfiltered bound with the smallest distance

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator
convexphase	consider only convex variables?

Definition at line 1509 of file prop_obbt.c.

◆ applySeparation()

static SCIP_RETCODE applySeparation	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		BOUND *	currbound,
		SCIP_Longint *	nleftiterations,
		SCIP_Bool *	success
	)

static

try to separate the solution of the last OBBT LP in order to learn better variable bounds; we apply additional separation rounds as long as the routine finds better bounds; because of dual degeneracy we apply a minimum number of separation rounds

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator
currbound	current bound
nleftiterations	number of left iterations (-1 for no limit)
success	pointer to store if we have found a better bound

Definition at line 1561 of file prop_obbt.c.

◆ findNewBounds()

static SCIP_RETCODE findNewBounds	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_Longint *	nleftiterations,
		SCIP_Bool	convexphase
	)

static

finds new variable bounds until no iterations left or all bounds have been checked

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator
nleftiterations	pointer to store the number of left iterations
convexphase	consider only convex variables?

Definition at line 1642 of file prop_obbt.c.

◆ 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 1870 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPEXEC().

◆ solveBilinearLP()

static SCIP_RETCODE solveBilinearLP	(	SCIP *	scip,
		SCIP_VAR *	x,
		SCIP_VAR *	y,
		SCIP_Real	xs,
		SCIP_Real	ys,
		SCIP_Real	xt,
		SCIP_Real	yt,
		SCIP_Real *	xcoef,
		SCIP_Real *	ycoef,
		SCIP_Real *	constant,
		SCIP_Longint	iterlim
	)

static

computes a valid inequality from the current LP relaxation for a bilinear term xy only involving x and y; the inequality is found by optimizing along the line connecting the points (xs,ys) and (xt,yt) over the currently given linear relaxation of the problem; this optimization problem is an LP

max lambda s.t. Ax <= b (x,y) = (xs,ys) + lambda ((xt,yt) - (xs,ys)) lambda in [0,1]

which is equivalent to

max x s.t. (1) Ax <= b (2) (x - xs) / (xt - xs) = (y - ys) / (yt - ys)

Let x* be the optimal primal and (mu,theta) be the optimal dual solution of this LP. The KKT conditions imply that the aggregation of the linear constraints mu*Ax <= mu*b can be written as

x * (1 - theta / (xt - xs)) + y * theta / (yt - ys) = mu * Ax <= mu * b

<=> alpha * x + beta * y <= mu * b = alpha * (x*) + beta * (y*)

which is a valid inequality in the (x,y)-space; in order to avoid numerical difficulties when (xs,ys) is too close to (xt,yt), we scale constraint (2) by min{ max{1,|xt-xs|,|yt-ys|}, 100 } beforehand

Parameters

scip	SCIP data structure
x	first variable
y	second variable
xs	x-coordinate of the first point
ys	y-coordinate of the first point
xt	x-coordinate of the second point
yt	y-coordinate of the second point
xcoef	pointer to store the coefficient of x
ycoef	pointer to store the coefficient of y
constant	pointer to store the constant
iterlim	iteration limit (-1: for no limit)

Definition at line 2123 of file prop_obbt.c.

References applyObbtBilinear(), FALSE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPaddRowProbing(), SCIPaddVarToRow(), SCIPbacktrackProbing(), SCIPchgVarObjProbing(), SCIPcreateEmptyRowUnspec(), SCIPdebugMsg, SCIPgetLPSolstat(), SCIPinProbing(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPisHugeValue(), SCIPnewProbingNode(), SCIPreleaseRow(), SCIProwGetDualsol(), SCIPsolveProbingLP(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPwarningMessage(), and TRUE.

◆ applyObbtBilinear()

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

static

Parameters

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

Definition at line 2252 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPEXEC(), and solveBilinearLP().

◆ getScore()

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 2415 of file prop_obbt.c.

◆ getScoreBilinBound()

static SCIP_Real getScoreBilinBound	(	SCIP *	scip,
		SCIP_RANDNUMGEN *	randnumgen,
		BILINBOUND *	bilinbound,
		int	nbilinterms
	)

static

computes the score of a bilinear term bound

Parameters

scip	SCIP data structure
randnumgen	random number generator
bilinbound	bilinear term bound
nbilinterms	maximal number of bilinear terms in all quadratic constraints

Definition at line 2458 of file prop_obbt.c.

◆ countNLRowVarsNonConvexity()

static SCIP_RETCODE countNLRowVarsNonConvexity	(	SCIP *	scip,
		int *	nlcounts,
		SCIP_NLROW *	nlrow
	)

static

count the variables which appear in non-convex term of nlrow

Parameters

scip	SCIP data structure
nlcounts	store the number each variable appears in a non-convex term
nlrow	nonlinear row

Definition at line 2503 of file prop_obbt.c.

◆ getNLPVarsNonConvexity()

static SCIP_RETCODE getNLPVarsNonConvexity	(	SCIP *	scip,
		int *	nlcounts
	)

static

count how often each variable appears in a non-convex term

Parameters

scip	SCIP data structure
nlcounts	store the number each variable appears in a non-convex term

Definition at line 2573 of file prop_obbt.c.

◆ varIsInteresting()

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

static

determines whether a variable is interesting

Parameters

scip	SCIP data structure
var	variable to check
nlcount	number of nonlinear constraints containing the variable or number of non-convex terms containing the variable (depends on propdata->onlynonconvexvars)

Definition at line 2729 of file prop_obbt.c.

◆ initBounds()

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

static

initializes interesting bounds

Parameters

scip	SCIP data structure
propdata	data of the obbt propagator

Definition at line 2745 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPEXEC().

◆ SCIP_DECL_PROPCOPY()

static SCIP_DECL_PROPCOPY ( propCopyObbt )

static

copy method for propagator plugins (called when SCIP copies plugins)

Note: The UG framework assumes that all default plug-ins of SCIP implement a copy callback. We check SCIPgetSubscipDepth() in PROPEXEC to prevent the propagator to run in a sub-SCIP.

Definition at line 2950 of file prop_obbt.c.

References NULL, PROP_NAME, SCIPpropGetData(), and SCIPpropGetName().

◆ SCIP_DECL_PROPINITSOL()

static SCIP_DECL_PROPINITSOL ( propInitsolObbt )

static

solving process initialization method of propagator (called when branch and bound process is about to begin)

Definition at line 2964 of file prop_obbt.c.

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecObbt )

static

execution method of propagator

Definition at line 2995 of file prop_obbt.c.

References applyObbt(), applyObbtBilinear(), initBounds(), MAX, NULL, SCIP_CALL, SCIP_DECL_PROPEXITSOL(), SCIP_DECL_PROPRESPROP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIPallColsInLP(), SCIPallowWeakDualReds(), SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPSolstat(), SCIPgetNRootLPIterations(), SCIPgetProbName(), SCIPinProbing(), SCIPnodeGetNumber(), and SCIPpropGetData().

◆ SCIP_DECL_PROPRESPROP()

static SCIP_DECL_PROPRESPROP ( propRespropObbt )

static

propagation conflict resolving method of propagator

Definition at line 3111 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPEXEC().

◆ SCIP_DECL_PROPEXITSOL()

static SCIP_DECL_PROPEXITSOL ( propExitsolObbt )

static

solving process deinitialization method of propagator (called before branch and bound process data is freed)

Definition at line 3120 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPEXEC().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeObbt )

static

destructor of propagator to free user data (called when SCIP is exiting)

Definition at line 3173 of file prop_obbt.c.

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ PROP_NAME

◆ PROP_DESC

◆ PROP_TIMING

◆ PROP_PRIORITY

◆ PROP_FREQ

◆ PROP_DELAY

◆ DEFAULT_CREATE_GENVBOUNDS

◆ DEFAULT_FILTERING_NORM

◆ DEFAULT_APPLY_FILTERROUNDS

◆ DEFAULT_APPLY_TRIVIALFITLERING

◆ DEFAULT_GENVBDSDURINGFILTER

◆ DEFAULT_DUALFEASTOL

◆ DEFAULT_CONDITIONLIMIT

◆ DEFAULT_BOUNDSTREPS

◆ DEFAULT_FILTERING_MIN

◆ DEFAULT_ITLIMITFACTOR

◆ DEFAULT_MINITLIMIT

◆ DEFAULT_ONLYNONCONVEXVARS

◆ DEFAULT_TIGHTINTBOUNDSPROBING

◆ DEFAULT_TIGHTCONTBOUNDSPROBING

◆ DEFAULT_ORDERINGALGO

◆ OBBT_SCOREBASE

◆ GENVBOUND_PROP_NAME

◆ INTERVALINFTY

◆ DEFAULT_SEPARATESOL

◆ DEFAULT_SEPAMINITER

◆ DEFAULT_SEPAMAXITER

◆ DEFAULT_GENVBDSDURINGSEPA

◆ DEFAULT_PROPAGATEFREQ

◆ DEFAULT_CREATE_BILININEQS

◆ DEFAULT_ITLIMITFAC_BILININEQS

◆ DEFAULT_MINNONCONVEXITY

◆ DEFAULT_RANDSEED

◆ infty2infty

Typedef Documentation

◆ BOUND

◆ CORNER

◆ BILINBOUND

Enumeration Type Documentation

◆ Corner

Function Documentation

◆ solveLP()

◆ addObjCutoff()

◆ varIsFixedLocal()

◆ setObjProbing()

◆ includeVarGenVBound()

◆ getIterationsLeft()

◆ getFilterCoef()

◆ createGenVBound()

◆ exchangeBounds()

◆ getCorner()

◆ getCorners()

◆ filterExistingLP()

◆ filterRound()

◆ filterBounds()

◆ applyBoundChgs()

◆ tightenBoundProbing()

◆ SCIP_DECL_SORTPTRCOMP() [1/3]

◆ SCIP_DECL_SORTPTRCOMP() [2/3]

◆ SCIP_DECL_SORTPTRCOMP() [3/3]

◆ sortBounds()

◆ evalBound()

◆ nextBound()

◆ applySeparation()

◆ findNewBounds()

◆ applyObbt()

◆ solveBilinearLP()

◆ applyObbtBilinear()

◆ getScore()

◆ getScoreBilinBound()

◆ countNLRowVarsNonConvexity()

◆ getNLPVarsNonConvexity()