SCIP
Solving Constraint Integer Programs
prop_obbt.c File Reference
Detailed Description
optimization-based bound tightening propagator
Definition in file prop_obbt.c.
#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 |
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 } |
Macro Definition Documentation
◆ PROP_NAME
| #define PROP_NAME "obbt" |
Definition at line 80 of file prop_obbt.c.
◆ PROP_DESC
| #define PROP_DESC "optimization-based bound tightening propagator" |
Definition at line 81 of file prop_obbt.c.
◆ PROP_TIMING
| #define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 82 of file prop_obbt.c.
◆ PROP_PRIORITY
| #define PROP_PRIORITY -1000000 |
propagator priority
Definition at line 83 of file prop_obbt.c.
◆ PROP_FREQ
| #define PROP_FREQ 0 |
propagator frequency
Definition at line 84 of file prop_obbt.c.
◆ PROP_DELAY
| #define PROP_DELAY TRUE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 86 of file prop_obbt.c.
◆ DEFAULT_CREATE_GENVBOUNDS
| #define DEFAULT_CREATE_GENVBOUNDS TRUE |
should obbt try to provide genvbounds if possible?
Definition at line 88 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 90 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 92 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 93 of file prop_obbt.c.
◆ DEFAULT_GENVBDSDURINGFILTER
| #define DEFAULT_GENVBDSDURINGFILTER TRUE |
try to genrate genvbounds during trivial and aggressive filtering?
Definition at line 94 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 96 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 97 of file prop_obbt.c.
◆ DEFAULT_BOUNDSTREPS
| #define DEFAULT_BOUNDSTREPS 0.001 |
minimal relative improve for strengthening bounds
Definition at line 98 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 100 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 102 of file prop_obbt.c.
◆ DEFAULT_MINITLIMIT
| #define DEFAULT_MINITLIMIT 5000L |
minimum LP iteration limit
Definition at line 103 of file prop_obbt.c.
◆ DEFAULT_ONLYNONCONVEXVARS
| #define DEFAULT_ONLYNONCONVEXVARS TRUE |
only apply obbt on non-convex variables
Definition at line 104 of file prop_obbt.c.
◆ DEFAULT_INDICATORS
| #define DEFAULT_INDICATORS FALSE |
apply obbt on variables of indicator constraints? (independent of convexity)
Definition at line 105 of file prop_obbt.c.
◆ 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 107 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 109 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 111 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 113 of file prop_obbt.c.
◆ OBBT_SCOREBASE
| #define OBBT_SCOREBASE 5 |
base that is used to calculate a bounds score value
Definition at line 114 of file prop_obbt.c.
◆ GENVBOUND_PROP_NAME
| #define GENVBOUND_PROP_NAME "genvbounds" |
Definition at line 115 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 120 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 121 of file prop_obbt.c.
◆ DEFAULT_GENVBDSDURINGSEPA
| #define DEFAULT_GENVBDSDURINGSEPA TRUE |
try to create genvbounds during separation process?
Definition at line 122 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 124 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 125 of file prop_obbt.c.
◆ DEFAULT_CREATE_LINCONS
| #define DEFAULT_CREATE_LINCONS FALSE |
create linear constraints from inequalities for bilinear terms?
Definition at line 126 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 127 of file prop_obbt.c.
◆ DEFAULT_MINNONCONVEXITY
| #define DEFAULT_MINNONCONVEXITY 1e-1 |
minimum nonconvexity for choosing a bilinear term
Definition at line 128 of file prop_obbt.c.
◆ DEFAULT_RANDSEED
| #define DEFAULT_RANDSEED 149 |
initial random seed
Definition at line 129 of file prop_obbt.c.
Typedef Documentation
◆ BOUND
Definition at line 149 of file prop_obbt.c.
◆ CORNER
Definition at line 160 of file prop_obbt.c.
◆ BILINBOUND
| typedef struct BilinBound BILINBOUND |
Definition at line 170 of file prop_obbt.c.
Enumeration Type Documentation
◆ Corner
| enum Corner |
| Enumerator | |
|---|---|
| LEFTBOTTOM | |
| RIGHTBOTTOM | |
| RIGHTTOP | |
| LEFTTOP | |
| FILTERED | |
Definition at line 152 of file prop_obbt.c.
Function Documentation
◆ solveLP()
|
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 244 of file prop_obbt.c.
References FALSE, NULL, SCIP_LPSOLSTAT_ERROR, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_LPSOLSTAT_NOTSOLVED, SCIP_LPSOLSTAT_OBJLIMIT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_TIMELIMIT, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIPdebugMsg, SCIPgetLPSolstat(), SCIPsolveProbingLP(), SCIPwarningMessage(), and TRUE.
Referenced by applySeparation(), filterExistingLP(), filterRound(), and findNewBounds().
◆ addObjCutoff()
|
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 316 of file prop_obbt.c.
References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddRowProbing(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowUnspec(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetCutoffbound(), SCIPgetVarsData(), SCIPinfinity(), SCIPinProbing(), SCIPisInfinity(), SCIProwIsInLP(), SCIPsnprintf(), and SCIPvarGetObj().
Referenced by applyObbt(), and applyObbtBilinear().
◆ varIsFixedLocal()
determines, whether a variable is already locally fixed
- Parameters
-
scip SCIP data structure var variable to check
Definition at line 366 of file prop_obbt.c.
References SCIPisFeasEQ(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by applyObbt(), getFilterCoef(), and varIsInteresting().
◆ setObjProbing()
|
static |
sets objective to minimize or maximize a single variable
Definition at line 376 of file prop_obbt.c.
References bound, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIPchgVarObjProbing(), SCIPgetNVars(), SCIPgetVarObjProbing(), and SCIPgetVars().
Referenced by filterExistingLP(), filterRound(), and findNewBounds().
◆ includeVarGenVBound()
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 423 of file prop_obbt.c.
References FALSE, NULL, SCIP_INVALID, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPdualfeastol(), SCIPgetVarRedcost(), SCIPvarGetStatus(), and TRUE.
Referenced by createGenVBound().
◆ getIterationsLeft()
|
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 450 of file prop_obbt.c.
References MAX, MIN, NULL, SCIP_Longint, SCIPdebugMsg, and SCIPgetNLPIterations().
Referenced by applyObbtBilinear(), filterBounds(), and findNewBounds().
◆ getFilterCoef()
|
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 480 of file prop_obbt.c.
References NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_Real, SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and varIsFixedLocal().
Referenced by filterBounds().
◆ createGenVBound()
|
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 554 of file prop_obbt.c.
References bound, EPSZ, FALSE, includeVarGenVBound(), NULL, 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(), and TRUE.
Referenced by applySeparation(), filterExistingLP(), filterRound(), and findNewBounds().
◆ exchangeBounds()
|
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 740 of file prop_obbt.c.
Referenced by filterExistingLP(), and findNewBounds().
◆ getCorner()
|
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 763 of file prop_obbt.c.
References FILTERED, LEFTBOTTOM, LEFTTOP, NULL, RIGHTBOTTOM, RIGHTTOP, SCIPABORT, SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), x, and y.
Referenced by filterExistingLP(), and getCorners().
◆ getCorners()
|
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 801 of file prop_obbt.c.
References FILTERED, getCorner(), LEFTBOTTOM, LEFTTOP, NULL, RIGHTBOTTOM, RIGHTTOP, SCIPABORT, x, and y.
Referenced by applyObbtBilinear().
◆ bilinboundGetX()
|
static |
returns the first variable of a bilinear bound
- Parameters
-
bilinbound bilinear bound
Definition at line 843 of file prop_obbt.c.
References BilinBound::expr, NULL, SCIPexprGetChildren(), SCIPexprGetNChildren(), and SCIPgetExprAuxVarNonlinear().
Referenced by applyObbtBilinear(), bilinboundGetScore(), and filterExistingLP().
◆ bilinboundGetY()
|
static |
returns the second variable of a bilinear bound
- Parameters
-
bilinbound bilinear bound
Definition at line 855 of file prop_obbt.c.
References BilinBound::expr, NULL, SCIPexprGetChildren(), SCIPexprGetNChildren(), and SCIPgetExprAuxVarNonlinear().
Referenced by applyObbtBilinear(), bilinboundGetScore(), and filterExistingLP().
◆ bilinboundGetLocksNeg()
|
static |
returns the negative locks of the expression in a bilinear bound
- Parameters
-
bilinbound bilinear bound
Definition at line 867 of file prop_obbt.c.
References BilinBound::expr, NULL, and SCIPgetExprNLocksNegNonlinear().
Referenced by applyObbtBilinear(), and bilinboundGetScore().
◆ bilinboundGetLocksPos()
|
static |
returns the positive locks of the expression in a bilinear bound
- Parameters
-
bilinbound bilinear bound
Definition at line 878 of file prop_obbt.c.
References BilinBound::expr, NULL, and SCIPgetExprNLocksPosNonlinear().
Referenced by applyObbtBilinear(), and bilinboundGetScore().
◆ bilinboundGetScore()
|
static |
computes the score of a bilinear term bound
- Parameters
-
scip SCIP data structure randnumgen random number generator bilinbound bilinear bound
Definition at line 889 of file prop_obbt.c.
References 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()
|
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
-
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) nindcount number of indicator constraints containing the variable or 0 (depends on propdata->indicators) threshold variables with smaller upper bound are not interesting
Definition at line 938 of file prop_obbt.c.
References FALSE, SCIPisLE(), SCIPvarGetUbLocal(), and TRUE.
Referenced by filterBounds(), and initBounds().
◆ filterExistingLP()
|
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 961 of file prop_obbt.c.
References bilinboundGetX(), bilinboundGetY(), bound, createGenVBound(), BilinBound::done, exchangeBounds(), FILTERED, BilinBound::filtered, getCorner(), LEFTBOTTOM, LEFTTOP, NULL, REALABS, RIGHTBOTTOM, RIGHTTOP, SCIP_BASESTAT_BASIC, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALID, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPchgVarObjProbing(), SCIPcolGetBasisStatus(), SCIPdebug, SCIPdebugMessage, SCIPdebugMsg, SCIPgetDepth(), SCIPgetLPSolstat(), SCIPgetNLPIterations(), SCIPgetNVars(), SCIPgetVarObjProbing(), SCIPgetVars(), SCIPinProbing(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), setObjProbing(), solveLP(), TRUE, Bound::var, x, and y.
Referenced by applyObbt(), and findNewBounds().
◆ filterRound()
|
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 1134 of file prop_obbt.c.
References bound, createGenVBound(), Bound::filtered, NULL, 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, and Bound::var.
Referenced by filterBounds().
◆ filterBounds()
|
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 1294 of file prop_obbt.c.
References bound, filterRound(), getFilterCoef(), getIterationsLeft(), indicatorVarIsInteresting(), NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPchgVarObjProbing(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPIterations(), SCIPgetVarObjProbing(), SCIPgetVarsData(), SCIPinProbing(), SCIPisZero(), and TRUE.
Referenced by applyObbt().
◆ applyBoundChgs()
|
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 1456 of file prop_obbt.c.
References bound, FALSE, NULL, 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()
|
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 1531 of file prop_obbt.c.
References bound, FALSE, NULL, 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]
|
static |
comparison method for two bounds w.r.t. their scores
Definition at line 1592 of file prop_obbt.c.
References Bound::score.
◆ SCIP_DECL_SORTPTRCOMP() [2/3]
|
static |
comparison method for two bilinear term bounds w.r.t. their scores
Definition at line 1602 of file prop_obbt.c.
References BilinBound::score.
◆ SCIP_DECL_SORTPTRCOMP() [3/3]
|
static |
comparison method for two bounds w.r.t. their boundtype
Definition at line 1612 of file prop_obbt.c.
References Bound::boundtype, Bound::done, Bound::filtered, SCIP_BOUNDTYPE_LOWER, and Bound::score.
◆ sortBounds()
|
static |
sort the propdata->bounds array with their distance or their boundtype key
- Parameters
-
scip SCIP data structure propdata propagator data
Definition at line 1637 of file prop_obbt.c.
References NULL, SCIP_OKAY, SCIPdebugMsg, and SCIPsortDownPtr().
Referenced by findNewBounds().
◆ evalBound()
evaluates a bound for the current LP solution
Definition at line 1653 of file prop_obbt.c.
References bound, NULL, REALABS, SCIP_BOUNDTYPE_LOWER, SCIPvarGetLbLocal(), SCIPvarGetLPSol(), and SCIPvarGetUbLocal().
Referenced by nextBound().
◆ nextBound()
|
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 1669 of file prop_obbt.c.
References Bound::done, evalBound(), Bound::filtered, Bound::indicator, Bound::nonconvex, NULL, SCIP_Real, and SCIPinfinity().
Referenced by findNewBounds().
◆ applySeparation()
|
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 1722 of file prop_obbt.c.
References createGenVBound(), FALSE, 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()
|
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 1804 of file prop_obbt.c.
References applySeparation(), Bound::boundtype, createGenVBound(), Bound::done, exchangeBounds(), FALSE, Bound::filtered, filterExistingLP(), Bound::found, getIterationsLeft(), Bound::newval, nextBound(), NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPchgVarObjProbing(), SCIPdebugMsg, SCIPfloor(), SCIPgetDepth(), SCIPgetNLPIterations(), SCIPinProbing(), SCIPisGT(), SCIPisLT(), SCIPisStopped(), SCIPpropagateProbing(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), setObjProbing(), solveLP(), sortBounds(), tightenBoundProbing(), TRUE, and Bound::var.
Referenced by applyObbt().
◆ applyObbt()
|
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 2043 of file prop_obbt.c.
References addObjCutoff(), applyBoundChgs(), bound, FALSE, filterBounds(), filterExistingLP(), findNewBounds(), MAX, MIN, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPallocBufferArray, SCIPchgDualfeastol(), SCIPchgVarObjProbing(), SCIPdebugMsg, SCIPdualfeastol(), SCIPendProbing(), SCIPfreeBufferArrayNull, SCIPgetCurrentNode(), SCIPgetIntParam(), SCIPgetNVars(), SCIPgetRealParam(), SCIPgetVars(), SCIPisEQ(), SCIPisLbBetter(), SCIPisUbBetter(), SCIPnodeGetNumber(), SCIPreleaseRow(), SCIProwIsInLP(), SCIPsetIntParam(), SCIPsetRealParam(), SCIPstartProbing(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPwarningMessage(), TRUE, and varIsFixedLocal().
Referenced by SCIP_DECL_PROPEXEC().
◆ solveBilinearLP()
|
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
-
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) nnonzduals buffer to store the number of non-zero dual multipliers except for the auxiliary row (NULL if not needed)
Definition at line 2297 of file prop_obbt.c.
References FALSE, MAX3, MIN, NULL, r, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALID, 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()
|
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 2445 of file prop_obbt.c.
References addObjCutoff(), bilinboundGetLocksNeg(), bilinboundGetLocksPos(), bilinboundGetX(), bilinboundGetY(), BilinBound::done, BilinBound::expr, FALSE, FILTERED, BilinBound::filtered, getCorners(), getIterationsLeft(), LEFTBOTTOM, LEFTTOP, NULL, REALABS, RIGHTBOTTOM, RIGHTTOP, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPaddCons(), SCIPaddIneqBilinear(), SCIPchgRelaxfeastol(), SCIPchgVarObjProbing(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPendProbing(), SCIPfeastol(), SCIPfindConshdlr(), SCIPfindNlhdlrNonlinear(), SCIPgetDepth(), SCIPgetNLPIterations(), SCIPgetNVars(), SCIPgetVars(), SCIPinfinity(), SCIPisFeasGT(), SCIPisFeasZero(), SCIPisHugeValue(), SCIPisStopped(), SCIPreleaseCons(), SCIPreleaseRow(), SCIProwIsInLP(), SCIPsnprintf(), SCIPsolveProbingLP(), SCIPstartProbing(), SCIPvarGetName(), solveBilinearLP(), SQR, TRUE, x, and y.
Referenced by SCIP_DECL_PROPEXEC().
◆ getScore()
|
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 nindcount number of indicator constraints containing the bounds variable maxnlcount maximal number of nonlinear and indicator constraints a variable appears in smallub variables with upper bound smaller than this value are counted in half iff part of indicator constraints
Definition at line 2640 of file prop_obbt.c.
References bound, NULL, OBBT_SCOREBASE, SCIP_BOUNDTYPE_UPPER, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIPABORT, SCIPerrorMessage, SCIPvarGetType(), SCIPvarGetUbLocal(), and SCIPvarIsImpliedIntegral().
Referenced by initBounds().
◆ getNLPVarsNonConvexity()
|
static |
count how often each variable is used in a nonconvex term
- Parameters
-
scip SCIP data structure nccounts store the number each variable appears in a non-convex term
Definition at line 2703 of file prop_obbt.c.
References BMSclearMemoryArray, NULL, SCIP_OKAY, SCIPconshdlrGetNConss(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPgetExprNSepaUsesActivityNonlinear(), SCIPgetNVars(), SCIPgetVarExprHashmapNonlinear(), SCIPgetVars(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisExprVar(), SCIPvarGetName(), and SCIPvarGetProbindex().
Referenced by initBounds().
◆ getNVarsIndicators()
|
static |
computes for each variable the number of indicator constraints in which the variable appears
- Parameters
-
scip SCIP data structure nindcount array that stores in how many indicator conss each variable appears
Definition at line 2761 of file prop_obbt.c.
References BMSclearMemoryArray, NULL, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfindConshdlr(), SCIPgetLinearConsIndicator(), SCIPgetNVars(), SCIPgetNVarsLinear(), SCIPgetSlackVarIndicator(), SCIPgetVarsLinear(), SCIPvarGetProbindex(), and SCIPvarGetStatus().
Referenced by initBounds().
◆ varIsInteresting()
|
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) nindcount number of indicator constraints containing the variable or 0 (depends on propdata->indicators)
Definition at line 2821 of file prop_obbt.c.
References SCIP_VARSTATUS_COLUMN, SCIPgetDepth(), SCIPvarGetStatus(), SCIPvarIsBinary(), and varIsFixedLocal().
Referenced by initBounds().
◆ initBounds()
|
static |
initializes interesting bounds
- Parameters
-
scip SCIP data structure propdata data of the obbt propagator
Definition at line 2839 of file prop_obbt.c.
References bilinboundGetScore(), BMSclearMemory, BMSclearMemoryArray, BilinBound::expr, FALSE, getNLPVarsNonConvexity(), getNVarsIndicators(), getScore(), indicatorVarIsInteresting(), MIN, NULL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcaptureExpr(), SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPfindConshdlr(), SCIPfindNlhdlrNonlinear(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetExprAuxVarNonlinear(), SCIPgetExprsBilinear(), SCIPgetNExprsBilinear(), SCIPgetNLPVarsNonlinearity(), SCIPgetNNLPVars(), SCIPgetRealParam(), SCIPgetVarsData(), SCIPisNLPConstructed(), SCIPsortDownPtr(), SCIPvarGetName(), BilinBound::score, varIsInteresting(), x, and y.
Referenced by SCIP_DECL_PROPEXEC().
◆ SCIP_DECL_PROPCOPY()
|
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 NULL, PROP_NAME, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_STRINGEQ, SCIPincludePropObbt(), and SCIPpropGetName().
◆ SCIP_DECL_PROPINITSOL()
|
static |
solving process initialization method of propagator (called when branch and bound process is about to begin)
Definition at line 3080 of file prop_obbt.c.
References DEFAULT_RANDSEED, GENVBOUND_PROP_NAME, NULL, PROP_NAME, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_STRINGEQ, SCIPcreateRandom(), SCIPdebugMsg, SCIPfindProp(), SCIPpropGetData(), SCIPpropGetName(), and TRUE.
◆ SCIP_DECL_PROPEXEC()
|
static |
execution method of propagator
Definition at line 3112 of file prop_obbt.c.
References applyObbt(), applyObbtBilinear(), initBounds(), MAX, NULL, PROP_NAME, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_INVALIDCALL, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIP_STRINGEQ, SCIPallColsInLP(), SCIPallowWeakDualReds(), SCIPconshdlrGetNConss(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPSolstat(), SCIPgetNRootLPIterations(), SCIPgetProbName(), SCIPgetStage(), SCIPgetSubscipDepth(), SCIPinProbing(), SCIPinRepropagation(), SCIPisNLPConstructed(), SCIPnodeGetNumber(), SCIPpropGetData(), and SCIPpropGetName().
◆ SCIP_DECL_PROPRESPROP()
|
static |
propagation conflict resolving method of propagator
Definition at line 3229 of file prop_obbt.c.
References SCIP_DIDNOTFIND, and SCIP_OKAY.
◆ SCIP_DECL_PROPEXITSOL()
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 3238 of file prop_obbt.c.
References NULL, PROP_NAME, SCIP_CALL, SCIP_INVALIDCALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_STRINGEQ, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeRandom(), SCIPpropGetData(), SCIPpropGetName(), SCIPreleaseExpr(), and SCIPstatisticMessage.
◆ SCIP_DECL_PROPFREE()
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 3302 of file prop_obbt.c.
References NULL, PROP_NAME, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_STRINGEQ, SCIPfreeBlockMemory, SCIPpropGetData(), SCIPpropGetName(), and SCIPpropSetData().