SCIP Doxygen Documentation
Loading...
Searching...
No Matches

Detailed Description

optimization-based bound tightening propagator

Author
Stefan Weltge
Benjamin Mueller

Definition in file prop_obbt.c.

#include <assert.h>
#include <string.h>
#include "scip/cons_indicator.h"
#include "scip/cons_linear.h"
#include "scip/cons_nonlinear.h"
#include "scip/nlhdlr_bilinear.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"

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   TRUE
#define DEFAULT_INDICATORS   FALSE
#define DEFAULT_INDICATORTHRESHOLD   1e6
#define DEFAULT_TIGHTINTBOUNDSPROBING   TRUE
#define DEFAULT_TIGHTCONTBOUNDSPROBING   FALSE
#define DEFAULT_ORDERINGALGO   1
#define OBBT_SCOREBASE   5
#define GENVBOUND_PROP_NAME   "genvbounds"
#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_CREATE_LINCONS   FALSE
#define DEFAULT_ITLIMITFAC_BILININEQS   3.0
#define DEFAULT_MINNONCONVEXITY   1e-1
#define DEFAULT_RANDSEED   149

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_VARbilinboundGetX (BILINBOUND *bilinbound)
static SCIP_VARbilinboundGetY (BILINBOUND *bilinbound)
static int bilinboundGetLocksNeg (BILINBOUND *bilinbound)
static int bilinboundGetLocksPos (BILINBOUND *bilinbound)
static SCIP_Real bilinboundGetScore (SCIP *scip, SCIP_RANDNUMGEN *randnumgen, BILINBOUND *bilinbound)
static SCIP_Bool indicatorVarIsInteresting (SCIP *scip, SCIP_VAR *var, int nlcount, int nindcount, SCIP_Real threshold)
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, int *nnonzduals)
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 nindcount, int maxnlcount, SCIP_Real smallub)
static SCIP_RETCODE getNLPVarsNonConvexity (SCIP *scip, unsigned int *nccounts)
static SCIP_RETCODE getNVarsIndicators (SCIP *scip, int *nindcount)
static SCIP_Bool varIsInteresting (SCIP *scip, SCIP_VAR *var, int nlcount, int nindcount)
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 83 of file prop_obbt.c.

◆ PROP_DESC

#define PROP_DESC   "optimization-based bound tightening propagator"

Definition at line 84 of file prop_obbt.c.

◆ PROP_TIMING

#define PROP_TIMING   SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 85 of file prop_obbt.c.

◆ PROP_PRIORITY

#define PROP_PRIORITY   -1000000

propagator priority

Definition at line 86 of file prop_obbt.c.

◆ PROP_FREQ

#define PROP_FREQ   0

propagator frequency

Definition at line 87 of file prop_obbt.c.

◆ PROP_DELAY

#define PROP_DELAY   TRUE

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

Definition at line 88 of file prop_obbt.c.

◆ DEFAULT_CREATE_GENVBOUNDS

#define DEFAULT_CREATE_GENVBOUNDS   TRUE

should obbt try to provide genvbounds if possible?

Definition at line 91 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_FILTERING_NORM

#define DEFAULT_FILTERING_NORM   TRUE

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

Definition at line 92 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_APPLY_FILTERROUNDS

#define DEFAULT_APPLY_FILTERROUNDS   FALSE

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

Definition at line 94 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_APPLY_TRIVIALFITLERING

#define DEFAULT_APPLY_TRIVIALFITLERING   TRUE

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

Definition at line 96 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_GENVBDSDURINGFILTER

#define DEFAULT_GENVBDSDURINGFILTER   TRUE

try to genrate genvbounds during trivial and aggressive filtering?

Definition at line 97 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

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

Referenced by SCIPincludePropObbt().

◆ DEFAULT_CONDITIONLIMIT

#define DEFAULT_CONDITIONLIMIT   -1.0

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

Definition at line 100 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_BOUNDSTREPS

#define DEFAULT_BOUNDSTREPS   0.001

minimal relative improve for strengthening bounds

Definition at line 101 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_FILTERING_MIN

#define DEFAULT_FILTERING_MIN   2

minimal number of filtered bounds to apply another filter round

Definition at line 102 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

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

◆ DEFAULT_MINITLIMIT

#define DEFAULT_MINITLIMIT   5000L

minimum LP iteration limit

Definition at line 106 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_ONLYNONCONVEXVARS

#define DEFAULT_ONLYNONCONVEXVARS   TRUE

only apply obbt on non-convex variables

Definition at line 107 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_INDICATORS

#define DEFAULT_INDICATORS   FALSE

apply obbt on variables of indicator constraints? (independent of convexity)

Definition at line 108 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_INDICATORTHRESHOLD

#define DEFAULT_INDICATORTHRESHOLD   1e6

variables of indicator constraints with smaller upper bound are not considered and upper bound is tightened only if new bound is smaller

Definition at line 109 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_TIGHTINTBOUNDSPROBING

#define DEFAULT_TIGHTINTBOUNDSPROBING   TRUE

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

Definition at line 111 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_TIGHTCONTBOUNDSPROBING

#define DEFAULT_TIGHTCONTBOUNDSPROBING   FALSE

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

Definition at line 113 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_ORDERINGALGO

#define DEFAULT_ORDERINGALGO   1

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

Definition at line 115 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ OBBT_SCOREBASE

#define OBBT_SCOREBASE   5

base that is used to calculate a bounds score value

Definition at line 117 of file prop_obbt.c.

Referenced by getScore().

◆ GENVBOUND_PROP_NAME

#define GENVBOUND_PROP_NAME   "genvbounds"

Definition at line 118 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPINITSOL().

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

Referenced by SCIPincludePropObbt().

◆ DEFAULT_SEPAMINITER

#define DEFAULT_SEPAMINITER   0

minimum number of iteration spend to separate an obbt LP solution

Definition at line 123 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_SEPAMAXITER

#define DEFAULT_SEPAMAXITER   10

maximum number of iteration spend to separate an obbt LP solution

Definition at line 124 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_GENVBDSDURINGSEPA

#define DEFAULT_GENVBDSDURINGSEPA   TRUE

try to create genvbounds during separation process?

Definition at line 125 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_PROPAGATEFREQ

#define DEFAULT_PROPAGATEFREQ   0

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

Definition at line 126 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_CREATE_BILININEQS

#define DEFAULT_CREATE_BILININEQS   TRUE

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

Definition at line 128 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_CREATE_LINCONS

#define DEFAULT_CREATE_LINCONS   FALSE

create linear constraints from inequalities for bilinear terms?

Definition at line 129 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

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

Referenced by SCIPincludePropObbt().

◆ DEFAULT_MINNONCONVEXITY

#define DEFAULT_MINNONCONVEXITY   1e-1

minimum nonconvexity for choosing a bilinear term

Definition at line 131 of file prop_obbt.c.

Referenced by SCIPincludePropObbt().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   149

initial random seed

Definition at line 132 of file prop_obbt.c.

Typedef Documentation

◆ BOUND

typedef struct Bound BOUND

Definition at line 152 of file prop_obbt.c.

◆ CORNER

typedef enum Corner CORNER

Definition at line 163 of file prop_obbt.c.

◆ BILINBOUND

typedef struct BilinBound BILINBOUND

Definition at line 173 of file prop_obbt.c.

Enumeration Type Documentation

◆ Corner

enum Corner
Enumerator
LEFTBOTTOM 
RIGHTBOTTOM 
RIGHTTOP 
LEFTTOP 
FILTERED 

Definition at line 155 of file prop_obbt.c.

Function Documentation

◆ solveLP()

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

solves the LP and handles errors

Parameters
scipSCIP data structure
itlimitmaximal number of LP iterations to perform, or -1 for no limit
errorpointer to store whether an unresolved LP error occurred
optimalwas the LP solved to optimalilty?

Definition at line 247 of file prop_obbt.c.

References assert(), FALSE, lpsolstat, NULL, SCIP_Bool, 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, SCIPdebugMsg, SCIPgetLPSolstat(), SCIPsolveProbingLP(), SCIPwarningMessage(), and TRUE.

Referenced by applySeparation(), filterExistingLP(), filterRound(), and findNewBounds().

◆ addObjCutoff()

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

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

Parameters
scipSCIP data structure
propdatadata of the obbt propagator

Definition at line 319 of file prop_obbt.c.

References assert(), FALSE, i, NULL, nvars, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddRowProbing(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowUnspec(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetCutoffbound(), SCIPgetVarsData(), SCIPinfinity(), SCIPinProbing(), SCIPisInfinity(), SCIProwIsInLP(), SCIPsnprintf(), SCIPvarGetObj(), and vars.

Referenced by applyObbt(), and applyObbtBilinear().

◆ varIsFixedLocal()

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

determines, whether a variable is already locally fixed

Parameters
scipSCIP data structure
varvariable to check

Definition at line 369 of file prop_obbt.c.

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

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

◆ setObjProbing()

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

References assert(), bound, i, NULL, nvars, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObjProbing(), SCIPgetNVars(), SCIPgetVarObjProbing(), SCIPgetVars(), and vars.

Referenced by filterExistingLP(), filterRound(), and findNewBounds().

◆ includeVarGenVBound()

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
scipSCIP data structure
varvariable to check

Definition at line 426 of file prop_obbt.c.

References assert(), FALSE, NULL, SCIP_Bool, SCIP_INVALID, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPdualfeastol(), SCIPgetVarRedcost(), SCIPvarGetStatus(), TRUE, and var.

Referenced by createGenVBound().

◆ getIterationsLeft()

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

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

Parameters
scipSCIP data structure
nolditerationsiterations count at the beginning of the corresponding function
itlimitLP iteration limit (-1: no limit)

Definition at line 453 of file prop_obbt.c.

References assert(), MAX, MIN, NULL, SCIP_Longint, SCIPdebugMsg, and SCIPgetNLPIterations().

Referenced by applyObbtBilinear(), filterBounds(), and findNewBounds().

◆ getFilterCoef()

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
scipSCIP data structure
propdatadata of the obbt propagator
varvariable
boundtypeboundtype to be filtered?

Definition at line 483 of file prop_obbt.c.

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

Referenced by filterBounds().

◆ createGenVBound()

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
scipSCIP data structure
propdatadata of the obbt propagator
boundbound of x_i
foundpointer to store if we have found a non-trivial genvbound

Definition at line 557 of file prop_obbt.c.

References assert(), bound, c, EPSZ, FALSE, includeVarGenVBound(), NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPdualfeastol(), SCIPfreeBufferArray, SCIPgenVBoundAdd(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetVarRedcost(), SCIPgetVarsData(), SCIPinProbing(), SCIPisInfinity(), SCIPisZero(), SCIPrelDiff(), SCIProwGetDualsol(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbLocal(), TRUE, and vars.

Referenced by applySeparation(), filterExistingLP(), filterRound(), and findNewBounds().

◆ exchangeBounds()

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
propdatapropagator data
ibound that was filtered or processed

Definition at line 743 of file prop_obbt.c.

References assert(), and i.

Referenced by filterExistingLP(), and findNewBounds().

◆ getCorner()

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
xfirst variable
ysecond variable
cornercorner
pxbuffer to store point for x
pybuffer to store point for y

Definition at line 766 of file prop_obbt.c.

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

Referenced by filterExistingLP(), and getCorners().

◆ getCorners()

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
xfirst variable
ysecond variable
cornercorner
xsbuffer to store start point for x
ysbuffer to store start point for y
xtbuffer to store end point for x
ytbuffer to store end point for y

Definition at line 804 of file prop_obbt.c.

References assert(), FILTERED, getCorner(), LEFTBOTTOM, LEFTTOP, NULL, RIGHTBOTTOM, RIGHTTOP, SCIP_Real, SCIPABORT, x, and y.

Referenced by applyObbtBilinear().

◆ bilinboundGetX()

SCIP_VAR * bilinboundGetX ( BILINBOUND * bilinbound)
static

returns the first variable of a bilinear bound

Parameters
bilinboundbilinear bound

Definition at line 846 of file prop_obbt.c.

References assert(), BilinBound::expr, NULL, SCIPexprGetChildren(), SCIPexprGetNChildren(), and SCIPgetExprAuxVarNonlinear().

Referenced by applyObbtBilinear(), bilinboundGetScore(), and filterExistingLP().

◆ bilinboundGetY()

SCIP_VAR * bilinboundGetY ( BILINBOUND * bilinbound)
static

returns the second variable of a bilinear bound

Parameters
bilinboundbilinear bound

Definition at line 858 of file prop_obbt.c.

References assert(), BilinBound::expr, NULL, SCIPexprGetChildren(), SCIPexprGetNChildren(), and SCIPgetExprAuxVarNonlinear().

Referenced by applyObbtBilinear(), bilinboundGetScore(), and filterExistingLP().

◆ bilinboundGetLocksNeg()

int bilinboundGetLocksNeg ( BILINBOUND * bilinbound)
static

returns the negative locks of the expression in a bilinear bound

Parameters
bilinboundbilinear bound

Definition at line 870 of file prop_obbt.c.

References assert(), BilinBound::expr, NULL, and SCIPgetExprNLocksNegNonlinear().

Referenced by applyObbtBilinear(), and bilinboundGetScore().

◆ bilinboundGetLocksPos()

int bilinboundGetLocksPos ( BILINBOUND * bilinbound)
static

returns the positive locks of the expression in a bilinear bound

Parameters
bilinboundbilinear bound

Definition at line 881 of file prop_obbt.c.

References assert(), BilinBound::expr, NULL, and SCIPgetExprNLocksPosNonlinear().

Referenced by applyObbtBilinear(), and bilinboundGetScore().

◆ bilinboundGetScore()

SCIP_Real bilinboundGetScore ( SCIP * scip,
SCIP_RANDNUMGEN * randnumgen,
BILINBOUND * bilinbound )
static

computes the score of a bilinear term bound

Parameters
scipSCIP data structure
randnumgenrandom number generator
bilinboundbilinear bound

Definition at line 892 of file prop_obbt.c.

References assert(), bilinboundGetLocksNeg(), bilinboundGetLocksPos(), bilinboundGetX(), bilinboundGetY(), MAX, MIN, NULL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_Real, SCIPepsilon(), SCIPgetLPSolstat(), SCIPrandomGetReal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetUbLocal(), x, and y.

Referenced by initBounds().

◆ indicatorVarIsInteresting()

SCIP_Bool indicatorVarIsInteresting ( SCIP * scip,
SCIP_VAR * var,
int nlcount,
int nindcount,
SCIP_Real threshold )
static

determines whether a variable of an indicator constraint is (still) interesting

A variable is interesting if it is not only part of indicator constraints or if the upper bound is greater than the given threshold.

Parameters
scipSCIP data structure
varvariable to check
nlcountnumber of nonlinear constraints containing the variable or number of non-convex terms containing the variable (depends on propdata->onlynonconvexvars)
nindcountnumber of indicator constraints containing the variable or 0 (depends on propdata->indicators)
thresholdvariables with smaller upper bound are not interesting

Definition at line 941 of file prop_obbt.c.

References FALSE, SCIP_Bool, SCIP_Real, SCIPisLE(), SCIPvarGetUbLocal(), TRUE, and var.

Referenced by filterBounds(), and initBounds().

◆ filterExistingLP()

◆ filterRound()

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
scipSCIP data structure
propdatadata of the obbt propagator
itlimitLP iteration limit (-1: no limit)
nfilteredhow many bounds were filtered this round
objcoefsarray to store the nontrivial objective coefficients
objcoefsindsarray to store bound indices for which their corresponding variables has a nontrivial objective coefficient
nobjcoefsnumber of nontrivial objective coefficients

Definition at line 1137 of file prop_obbt.c.

References assert(), bound, createGenVBound(), Bound::filtered, i, NULL, nvars, SCIP_BASESTAT_BASIC, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObjProbing(), SCIPcolGetBasisStatus(), SCIPdebugMsg, SCIPgetDepth(), SCIPgetNLPIterations(), SCIPgetVarObjProbing(), SCIPgetVarsData(), SCIPinProbing(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetCol(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetUbLocal(), setObjProbing(), solveLP(), TRUE, Bound::var, and vars.

Referenced by filterBounds().

◆ filterBounds()

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

filter some bounds that are not improvable by solving auxiliary LPs

Parameters
scipSCIP data structure
propdatadata of the obbt propagator
itlimitLP iteration limit (-1: no limit)

Definition at line 1297 of file prop_obbt.c.

References assert(), bound, filterRound(), getFilterCoef(), getIterationsLeft(), i, indicatorVarIsInteresting(), NULL, nvars, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPchgVarObjProbing(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPIterations(), SCIPgetVarObjProbing(), SCIPgetVarsData(), SCIPinProbing(), SCIPisZero(), TRUE, and vars.

Referenced by applyObbt().

◆ applyBoundChgs()

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

applies possible bound changes that were found

Parameters
scipSCIP data structure
propdatadata of the obbt propagator
resultresult pointer

Definition at line 1459 of file prop_obbt.c.

References assert(), bound, FALSE, i, NULL, result, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPdebug, SCIPdebugMsg, SCIPinProbing(), SCIPisLE(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by applyObbt().

◆ tightenBoundProbing()

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

tries to tighten a bound in probing mode

Parameters
scipSCIP data structure
boundbound that could be tightened
newvalnew bound value
tightenedwas tightening successful?

Definition at line 1534 of file prop_obbt.c.

References assert(), bound, FALSE, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPfloor(), SCIPinProbing(), SCIPisLbBetter(), SCIPisUbBetter(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and TRUE.

Referenced by applySeparation(), and findNewBounds().

◆ SCIP_DECL_SORTPTRCOMP() [1/3]

SCIP_DECL_SORTPTRCOMP ( compBoundsScore )
static

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

Definition at line 1595 of file prop_obbt.c.

References Bound::score.

◆ SCIP_DECL_SORTPTRCOMP() [2/3]

SCIP_DECL_SORTPTRCOMP ( compBilinboundsScore )
static

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

Definition at line 1605 of file prop_obbt.c.

References BilinBound::score.

◆ SCIP_DECL_SORTPTRCOMP() [3/3]

SCIP_DECL_SORTPTRCOMP ( compBoundsBoundtype )
static

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

Definition at line 1615 of file prop_obbt.c.

References Bound::boundtype, Bound::done, Bound::filtered, SCIP_BOUNDTYPE_LOWER, and Bound::score.

◆ sortBounds()

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

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

Parameters
scipSCIP data structure
propdatapropagator data

Definition at line 1641 of file prop_obbt.c.

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

Referenced by findNewBounds().

◆ evalBound()

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

evaluates a bound for the current LP solution

Definition at line 1657 of file prop_obbt.c.

References assert(), bound, NULL, REALABS, SCIP_BOUNDTYPE_LOWER, SCIP_Real, SCIPvarGetLbLocal(), SCIPvarGetLPSol(), and SCIPvarGetUbLocal().

Referenced by nextBound().

◆ nextBound()

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
scipSCIP data structure
propdatadata of the obbt propagator
convexphaseconsider only convex variables?

Definition at line 1673 of file prop_obbt.c.

References assert(), Bound::done, evalBound(), Bound::filtered, Bound::indicator, Bound::nonconvex, NULL, SCIP_Bool, SCIP_Real, and SCIPinfinity().

Referenced by findNewBounds().

◆ applySeparation()

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
scipSCIP data structure
propdatadata of the obbt propagator
currboundcurrent bound
nleftiterationsnumber of left iterations (-1 for no limit)
successpointer to store if we have found a better bound

Definition at line 1726 of file prop_obbt.c.

References assert(), createGenVBound(), cutoff, FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIPapplyCutsProbing(), SCIPdebug, SCIPdebugMsg, SCIPgetDepth(), SCIPgetNCuts(), SCIPgetNLPIterations(), SCIPinProbing(), SCIPisEQ(), SCIPseparateSol(), SCIPvarGetLPSol(), solveLP(), tightenBoundProbing(), TRUE, and Bound::var.

Referenced by findNewBounds().

◆ findNewBounds()

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

◆ applyObbt()

◆ solveBilinearLP()

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,
int * nnonzduals )
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 (1) by max{1,|xt-xs|,|yt-ys|} beforehand

Parameters
scipSCIP data structure
xfirst variable
ysecond variable
xsx-coordinate of the first point
ysy-coordinate of the first point
xtx-coordinate of the second point
yty-coordinate of the second point
xcoefpointer to store the coefficient of x
ycoefpointer to store the coefficient of y
constantpointer to store the constant
iterlimiteration limit (-1: for no limit)
nnonzdualsbuffer to store the number of non-zero dual multipliers except for the auxiliary row (NULL if not needed)

Definition at line 2301 of file prop_obbt.c.

References assert(), FALSE, lperror, MAX3, MIN, NULL, r, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPaddRowProbing(), SCIPaddVarToRow(), SCIPbacktrackProbing(), SCIPchgVarObjProbing(), SCIPcreateEmptyRowUnspec(), SCIPdebugMsg, SCIPgetLPRows(), SCIPgetLPSolstat(), SCIPgetNLPRows(), SCIPinProbing(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPisHugeValue(), SCIPisZero(), SCIPnewProbingNode(), SCIPreleaseRow(), SCIProwGetDualsol(), SCIPsolveProbingLP(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPwarningMessage(), TRUE, x, and y.

Referenced by applyObbtBilinear().

◆ applyObbtBilinear()

◆ getScore()

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

computes the score of a bound

Parameters
scipSCIP data structure
boundpointer of bound
nlcountnumber of nonlinear constraints containing the bounds variable
nindcountnumber of indicator constraints containing the bounds variable
maxnlcountmaximal number of nonlinear and indicator constraints a variable appears in
smallubvariables with upper bound smaller than this value are counted in half iff part of indicator constraints

Definition at line 2644 of file prop_obbt.c.

References assert(), bound, NULL, OBBT_SCOREBASE, SCIP_BOUNDTYPE_UPPER, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPvarGetType(), and SCIPvarGetUbLocal().

Referenced by initBounds().

◆ getNLPVarsNonConvexity()

SCIP_RETCODE getNLPVarsNonConvexity ( SCIP * scip,
unsigned int * nccounts )
static

count how often each variable is used in a nonconvex term

Parameters
scipSCIP data structure
nccountsstore the number each variable appears in a non-convex term

Definition at line 2703 of file prop_obbt.c.

References assert(), BMSclearMemoryArray, i, NULL, nvars, SCIP_OKAY, SCIPconshdlrGetNConss(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPgetExprNSepaUsesActivityNonlinear(), SCIPgetNVars(), SCIPgetVarExprHashmapNonlinear(), SCIPgetVars(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisExprVar(), SCIPvarGetName(), SCIPvarGetProbindex(), and var.

Referenced by initBounds().

◆ getNVarsIndicators()

SCIP_RETCODE getNVarsIndicators ( SCIP * scip,
int * nindcount )
static

computes for each variable the number of indicator constraints in which the variable appears

Parameters
scipSCIP data structure
nindcountarray that stores in how many indicator conss each variable appears

Definition at line 2761 of file prop_obbt.c.

References assert(), BMSclearMemoryArray, i, NULL, nvars, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfindConshdlr(), SCIPgetLinearConsIndicator(), SCIPgetNVars(), SCIPgetNVarsLinear(), SCIPgetSlackVarIndicator(), SCIPgetVarsLinear(), SCIPvarGetProbindex(), and SCIPvarGetStatus().

Referenced by initBounds().

◆ varIsInteresting()

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

determines whether a variable is interesting

Parameters
scipSCIP data structure
varvariable to check
nlcountnumber of nonlinear constraints containing the variable or number of non-convex terms containing the variable (depends on propdata->onlynonconvexvars)
nindcountnumber of indicator constraints containing the variable or 0 (depends on propdata->indicators)

Definition at line 2821 of file prop_obbt.c.

References assert(), SCIP_Bool, SCIP_VARSTATUS_COLUMN, SCIPgetDepth(), SCIPvarGetStatus(), SCIPvarIsBinary(), var, and varIsFixedLocal().

Referenced by initBounds().

◆ initBounds()

◆ SCIP_DECL_PROPCOPY()

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

References assert(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePropObbt(), and SCIPpropGetName().

◆ SCIP_DECL_PROPINITSOL()

SCIP_DECL_PROPINITSOL ( propInitsolObbt )
static

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

Definition at line 3079 of file prop_obbt.c.

References assert(), DEFAULT_RANDSEED, GENVBOUND_PROP_NAME, NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPdebugMsg, SCIPfindProp(), SCIPpropGetData(), SCIPpropGetName(), and TRUE.

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPRESPROP()

SCIP_DECL_PROPRESPROP ( propRespropObbt )
static

propagation conflict resolving method of propagator

Definition at line 3226 of file prop_obbt.c.

References result, SCIP_DIDNOTFIND, and SCIP_OKAY.

◆ SCIP_DECL_PROPEXITSOL()

SCIP_DECL_PROPEXITSOL ( propExitsolObbt )
static

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

Definition at line 3235 of file prop_obbt.c.

References assert(), i, NULL, PROP_NAME, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeRandom(), SCIPpropGetData(), SCIPpropGetName(), SCIPreleaseExpr(), and SCIPstatisticMessage.

◆ SCIP_DECL_PROPFREE()

SCIP_DECL_PROPFREE ( propFreeObbt )
static

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

Definition at line 3298 of file prop_obbt.c.

References assert(), NULL, PROP_NAME, SCIP_OKAY, SCIPfreeBlockMemory, SCIPpropGetData(), SCIPpropGetName(), and SCIPpropSetData().