Scippy

SCIP

Solving Constraint Integer Programs

prop_obbt.c File Reference

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/prop_obbt.h"
#include "scip/prop_genvbounds.h"
#include "scip/debug.h"
#include "scip/cons_quadratic.h"
#include "scip/cons_nonlinear.h"
#include "scip/cons_abspower.h"
#include "scip/cons_bivariate.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_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 infty2infty(infty1, infty2, val)   ((val) >= (infty1) ? (infty2) : (val))
 

Typedefs

typedef struct Bound BOUND
 

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 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 (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 unsigned int getScore (SCIP *scip, BOUND *bound, int nlcount, int maxnlcount)
 
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_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 49 of file prop_obbt.c.

#define PROP_DESC   "optimization-based bound tightening propagator"

Definition at line 50 of file prop_obbt.c.

#define PROP_TIMING   SCIP_PROPTIMING_AFTERLPLOOP

Definition at line 51 of file prop_obbt.c.

#define PROP_PRIORITY   -1000000

propagator priority

Definition at line 52 of file prop_obbt.c.

#define PROP_FREQ   0

propagator frequency

Definition at line 53 of file prop_obbt.c.

#define PROP_DELAY   TRUE

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

Definition at line 54 of file prop_obbt.c.

#define DEFAULT_CREATE_GENVBOUNDS   TRUE

should obbt try to provide genvbounds if possible?

Definition at line 58 of file prop_obbt.c.

#define DEFAULT_FILTERING_NORM   TRUE

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

Definition at line 59 of file prop_obbt.c.

#define DEFAULT_APPLY_FILTERROUNDS   FALSE

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

Definition at line 62 of file prop_obbt.c.

#define DEFAULT_APPLY_TRIVIALFITLERING   TRUE

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

Definition at line 65 of file prop_obbt.c.

#define DEFAULT_GENVBDSDURINGFILTER   TRUE

try to genrate genvbounds during trivial and aggressive filtering?

Definition at line 66 of file prop_obbt.c.

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

#define DEFAULT_CONDITIONLIMIT   -1.0

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

Definition at line 70 of file prop_obbt.c.

#define DEFAULT_BOUNDSTREPS   0.001

minimal relative improve for strengthening bounds

Definition at line 71 of file prop_obbt.c.

#define DEFAULT_FILTERING_MIN   2

minimal number of filtered bounds to apply another filter round

Definition at line 72 of file prop_obbt.c.

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

#define DEFAULT_MINITLIMIT   5000L

minimum LP iteration limit

Definition at line 78 of file prop_obbt.c.

#define DEFAULT_ONLYNONCONVEXVARS   FALSE

only apply obbt on non-convex variables

Definition at line 79 of file prop_obbt.c.

#define DEFAULT_TIGHTINTBOUNDSPROBING   TRUE

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

Definition at line 80 of file prop_obbt.c.

#define DEFAULT_TIGHTCONTBOUNDSPROBING   FALSE

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

Definition at line 83 of file prop_obbt.c.

#define DEFAULT_ORDERINGALGO   1

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

Definition at line 86 of file prop_obbt.c.

#define OBBT_SCOREBASE   5

base that is used to calculate a bounds score value

Definition at line 89 of file prop_obbt.c.

#define GENVBOUND_PROP_NAME   "genvbounds"

Definition at line 90 of file prop_obbt.c.

#define INTERVALINFTY   1E+43

value for infinity in interval operations

Definition at line 91 of file prop_obbt.c.

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

#define DEFAULT_SEPAMINITER   0

minimum number of iteration spend to separate an obbt LP solution

Definition at line 98 of file prop_obbt.c.

#define DEFAULT_SEPAMAXITER   10

maximum number of iteration spend to separate an obbt LP solution

Definition at line 99 of file prop_obbt.c.

#define DEFAULT_GENVBDSDURINGSEPA   TRUE

try to create genvbounds during separation process?

Definition at line 100 of file prop_obbt.c.

#define DEFAULT_PROPAGATEFREQ   0

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

Definition at line 101 of file prop_obbt.c.

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

Typedef Documentation

typedef struct Bound BOUND

Definition at line 128 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
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 189 of file prop_obbt.c.

Referenced by filterExistingLP().

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

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

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

Referenced by filterExistingLP().

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

Definition at line 368 of file prop_obbt.c.

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

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

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

Definition at line 425 of file prop_obbt.c.

Referenced by getIterationsLeft().

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

Referenced by filterExistingLP().

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

Definition at line 671 of file prop_obbt.c.

References NULL.

Referenced by 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
sciporiginal SCIP data structure
propdatadata of the obbt propagator
nfilteredhow many bounds were filtered this round?
currboundbound for which OBBT LP was solved (Note: might be NULL)

Definition at line 694 of file prop_obbt.c.

References Bound::boundtype, createGenVBound(), Bound::done, exchangeBounds(), Bound::filtered, filterRound(), Bound::found, NULL, SCIP_BASESTAT_BASIC, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPchgVarObjProbing(), SCIPcolGetBasisStatus(), SCIPdebugMessage, SCIPgetDepth(), SCIPgetNLPIterations(), SCIPgetNVars(), SCIPgetVarObjProbing(), SCIPgetVars(), SCIPinProbing(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisZero(), SCIPvarGetCol(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbLocal(), setObjProbing(), solveLP(), TRUE, and Bound::var.

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

Referenced by filterExistingLP().

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
scipSCIP data structure
propdatadata of the obbt propagator
itlimitLP iteration limit (-1: no limit)

Definition at line 971 of file prop_obbt.c.

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

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

static SCIP_DECL_SORTPTRCOMP ( compBoundsScore  )
static

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

Definition at line 1243 of file prop_obbt.c.

static SCIP_DECL_SORTPTRCOMP ( compBoundsBoundtype  )
static

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

Definition at line 1253 of file prop_obbt.c.

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

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

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

static SCIP_Real evalBound ( SCIP scip,
BOUND bound 
)
static

evaluates a bound for the current LP solution

Definition at line 1295 of file prop_obbt.c.

References NULL, and SCIP_Real.

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

Definition at line 1311 of file prop_obbt.c.

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

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
scipSCIP data structure
propdatadata of the obbt propagator
nleftiterationspointer to store the number of left iterations
convexphaseconsider only convex variables?

Definition at line 1445 of file prop_obbt.c.

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

main function of obbt

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

Definition at line 1684 of file prop_obbt.c.

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
scipSCIP data structure
boundpointer of bound
nlcountnumber of nonlinear constraints containing the bounds variable
maxnlcountmaximal number of nonlinear constraints a variable appears in

Definition at line 1906 of file prop_obbt.c.

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

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

Parameters
scipSCIP data structure
nlcountsstore the number each variable appears in a non-convex term
nlrownonlinear row

Definition at line 1949 of file prop_obbt.c.

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

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

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

Definition at line 2019 of file prop_obbt.c.

static SCIP_Bool varIsInteresting ( SCIP scip,
SCIP_VAR var,
int  nlcount 
)
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)

Definition at line 2161 of file prop_obbt.c.

static SCIP_RETCODE initBounds ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

initializes interesting bounds

Parameters
scipSCIP data structure
propdatadata of the obbt propagator

Definition at line 2177 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPEXEC().

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

static SCIP_DECL_PROPRESPROP ( propRespropObbt  )
static

propagation conflict resolving method of propagator

Definition at line 2420 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPEXEC().

static SCIP_DECL_PROPEXITSOL ( propExitsolObbt  )
static

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

Definition at line 2429 of file prop_obbt.c.

Referenced by SCIP_DECL_PROPEXEC().

static SCIP_DECL_PROPFREE ( propFreeObbt  )
static

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

Definition at line 2468 of file prop_obbt.c.

SCIP_RETCODE SCIPincludePropObbt ( SCIP scip)

creates the obbt propagator and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 2491 of file prop_obbt.c.

Referenced by SCIPincludeDefaultPlugins().