optimization-based bound tightening propagator
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 |
#define PROP_NAME "obbt" |
Definition at line 83 of file prop_obbt.c.
#define PROP_DESC "optimization-based bound tightening propagator" |
Definition at line 84 of file prop_obbt.c.
#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP |
Definition at line 85 of file prop_obbt.c.
#define PROP_PRIORITY -1000000 |
propagator priority
Definition at line 86 of file prop_obbt.c.
#define PROP_FREQ 0 |
propagator frequency
Definition at line 87 of file prop_obbt.c.
#define PROP_DELAY TRUE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 88 of file prop_obbt.c.
#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().
#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().
#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().
#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().
#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().
#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().
#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().
#define DEFAULT_BOUNDSTREPS 0.001 |
minimal relative improve for strengthening bounds
Definition at line 101 of file prop_obbt.c.
Referenced by SCIPincludePropObbt().
#define DEFAULT_FILTERING_MIN 2 |
minimal number of filtered bounds to apply another filter round
Definition at line 102 of file prop_obbt.c.
Referenced by SCIPincludePropObbt().
#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.
#define DEFAULT_MINITLIMIT 5000L |
minimum LP iteration limit
Definition at line 106 of file prop_obbt.c.
Referenced by SCIPincludePropObbt().
#define DEFAULT_ONLYNONCONVEXVARS TRUE |
only apply obbt on non-convex variables
Definition at line 107 of file prop_obbt.c.
Referenced by SCIPincludePropObbt().
#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().
#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().
#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().
#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().
#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().
#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().
#define GENVBOUND_PROP_NAME "genvbounds" |
Definition at line 118 of file prop_obbt.c.
Referenced by SCIP_DECL_PROPINITSOL().
#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().
#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().
#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().
#define DEFAULT_GENVBDSDURINGSEPA TRUE |
try to create genvbounds during separation process?
Definition at line 125 of file prop_obbt.c.
Referenced by SCIPincludePropObbt().
#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().
#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().
#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().
#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().
#define DEFAULT_MINNONCONVEXITY 1e-1 |
minimum nonconvexity for choosing a bilinear term
Definition at line 131 of file prop_obbt.c.
Referenced by SCIPincludePropObbt().
#define DEFAULT_RANDSEED 149 |
initial random seed
Definition at line 132 of file prop_obbt.c.
Definition at line 152 of file prop_obbt.c.
Definition at line 163 of file prop_obbt.c.
typedef struct BilinBound BILINBOUND |
Definition at line 173 of file prop_obbt.c.
enum Corner |
Enumerator | |
---|---|
LEFTBOTTOM | |
RIGHTBOTTOM | |
RIGHTTOP | |
LEFTTOP | |
FILTERED |
Definition at line 155 of file prop_obbt.c.
|
static |
solves the LP and handles errors
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 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().
|
static |
adds the objective cutoff to the LP; must be in probing mode
scip | SCIP data structure |
propdata | data 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().
determines, whether a variable is already locally fixed
scip | SCIP data structure |
var | variable 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().
|
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().
determines whether variable should be included in the right-hand side of the generalized variable bound
scip | SCIP data structure |
var | variable 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().
|
static |
returns number of LP iterations left (-1: no limit )
scip | SCIP data structure |
nolditerations | iterations count at the beginning of the corresponding function |
itlimit | LP 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().
|
static |
returns the objective coefficient for a variable's bound that will be chosen during filtering
scip | SCIP data structure |
propdata | data of the obbt propagator |
var | variable |
boundtype | boundtype 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().
|
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.
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 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().
|
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
propdata | propagator data |
i | bound that was filtered or processed |
Definition at line 743 of file prop_obbt.c.
Referenced by filterExistingLP(), and findNewBounds().
|
static |
helper function to return a corner of the domain of two variables
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 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().
|
static |
helper function to return the two end points of a diagonal
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 804 of file prop_obbt.c.
References assert(), FILTERED, getCorner(), LEFTBOTTOM, LEFTTOP, NULL, RIGHTBOTTOM, RIGHTTOP, SCIP_Real, SCIPABORT, x, and y.
Referenced by applyObbtBilinear().
|
static |
returns the first variable of a bilinear bound
bilinbound | bilinear 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().
|
static |
returns the second variable of a bilinear bound
bilinbound | bilinear 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().
|
static |
returns the negative locks of the expression in a bilinear bound
bilinbound | bilinear bound |
Definition at line 870 of file prop_obbt.c.
References assert(), BilinBound::expr, NULL, and SCIPgetExprNLocksNegNonlinear().
Referenced by applyObbtBilinear(), and bilinboundGetScore().
|
static |
returns the positive locks of the expression in a bilinear bound
bilinbound | bilinear bound |
Definition at line 881 of file prop_obbt.c.
References assert(), BilinBound::expr, NULL, and SCIPgetExprNLocksPosNonlinear().
Referenced by applyObbtBilinear(), and bilinboundGetScore().
|
static |
computes the score of a bilinear term bound
scip | SCIP data structure |
randnumgen | random number generator |
bilinbound | bilinear 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().
|
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.
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 941 of file prop_obbt.c.
References FALSE, SCIP_Bool, SCIP_Real, SCIPisLE(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by filterBounds(), and initBounds().
|
static |
trying to filter some bounds using the existing LP solution
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 964 of file prop_obbt.c.
References assert(), bilinboundGetX(), bilinboundGetY(), bound, createGenVBound(), BilinBound::done, exchangeBounds(), FILTERED, BilinBound::filtered, getCorner(), i, 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, var, x, and y.
Referenced by applyObbt(), and findNewBounds().
|
static |
enforces one round of filtering
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 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().
|
static |
filter some bounds that are not improvable by solving auxiliary LPs
scip | SCIP data structure |
propdata | data of the obbt propagator |
itlimit | LP 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().
|
static |
applies possible bound changes that were found
scip | SCIP data structure |
propdata | data of the obbt propagator |
result | result 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().
|
static |
tries to tighten a bound in probing mode
scip | SCIP data structure |
bound | bound that could be tightened |
newval | new bound value |
tightened | was 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().
|
static |
comparison method for two bounds w.r.t. their scores
Definition at line 1595 of file prop_obbt.c.
References Bound::score.
|
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.
|
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.
|
static |
sort the propdata->bounds array with their distance or their boundtype key
scip | SCIP data structure |
propdata | propagator data |
Definition at line 1641 of file prop_obbt.c.
References assert(), NULL, SCIP_OKAY, SCIPdebugMsg, and SCIPsortDownPtr().
Referenced by findNewBounds().
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().
|
static |
returns the index of the next undone and unfiltered bound with the smallest distance
scip | SCIP data structure |
propdata | data of the obbt propagator |
convexphase | consider 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().
|
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
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 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().
|
static |
finds new variable bounds until no iterations left or all bounds have been checked
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 1808 of file prop_obbt.c.
References applySeparation(), assert(), Bound::boundtype, createGenVBound(), cutoff, 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().
|
static |
main function of obbt
scip | SCIP data structure |
propdata | data of the obbt propagator |
itlimit | LP iteration limit (-1: no limit) |
result | result pointer |
Definition at line 2047 of file prop_obbt.c.
References addObjCutoff(), applyBoundChgs(), assert(), bound, FALSE, filterBounds(), filterExistingLP(), findNewBounds(), i, MAX, MIN, NULL, nvars, result, 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, varIsFixedLocal(), and vars.
Referenced by SCIP_DECL_PROPEXEC().
|
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
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 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().
|
static |
scip | SCIP data structure |
propdata | data of the obbt propagator |
itlimit | LP iteration limit (-1: no limit) |
result | result pointer |
Definition at line 2449 of file prop_obbt.c.
References addObjCutoff(), assert(), bilinboundGetLocksNeg(), bilinboundGetLocksPos(), bilinboundGetX(), bilinboundGetY(), BilinBound::done, BilinBound::expr, FALSE, FILTERED, BilinBound::filtered, getCorners(), getIterationsLeft(), i, LEFTBOTTOM, LEFTTOP, lperror, NULL, nvars, REALABS, result, 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, vars, x, and y.
Referenced by SCIP_DECL_PROPEXEC().
|
static |
computes the score of a bound
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 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().
|
static |
count how often each variable is used in a nonconvex term
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 assert(), BMSclearMemoryArray, i, NULL, nvars, SCIP_OKAY, SCIPconshdlrGetNConss(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPgetExprNSepaUsesActivityNonlinear(), SCIPgetNVars(), SCIPgetVarExprHashmapNonlinear(), SCIPgetVars(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisExprVar(), SCIPvarGetName(), SCIPvarGetProbindex(), and var.
Referenced by initBounds().
|
static |
computes for each variable the number of indicator constraints in which the variable appears
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 assert(), BMSclearMemoryArray, i, NULL, nvars, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfindConshdlr(), SCIPgetLinearConsIndicator(), SCIPgetNVars(), SCIPgetNVarsLinear(), SCIPgetSlackVarIndicator(), SCIPgetVarsLinear(), SCIPvarGetProbindex(), and SCIPvarGetStatus().
Referenced by initBounds().
|
static |
determines whether a variable is interesting
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 assert(), SCIP_Bool, SCIP_VARSTATUS_COLUMN, SCIPgetDepth(), SCIPvarGetStatus(), SCIPvarIsBinary(), var, and varIsFixedLocal().
Referenced by initBounds().
|
static |
initializes interesting bounds
scip | SCIP data structure |
propdata | data of the obbt propagator |
Definition at line 2839 of file prop_obbt.c.
References assert(), bilinboundGetScore(), BMSclearMemory, BMSclearMemoryArray, BilinBound::expr, FALSE, getNLPVarsNonConvexity(), getNVarsIndicators(), getScore(), i, indicatorVarIsInteresting(), MIN, NULL, nvars, 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(), vars, x, and y.
Referenced by SCIP_DECL_PROPEXEC().
|
static |
copy method for propagator plugins (called when SCIP copies plugins)
Definition at line 3065 of file prop_obbt.c.
References assert(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPincludePropObbt(), and SCIPpropGetName().
|
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.
|
static |
execution method of propagator
Definition at line 3110 of file prop_obbt.c.
References applyObbt(), applyObbtBilinear(), assert(), initBounds(), MAX, NULL, PROP_NAME, result, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPallColsInLP(), SCIPallowWeakDualReds(), SCIPconshdlrGetNConss(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPSolstat(), SCIPgetNRootLPIterations(), SCIPgetProbName(), SCIPgetStage(), SCIPgetSubscipDepth(), SCIPinProbing(), SCIPinRepropagation(), SCIPisNLPConstructed(), SCIPnodeGetNumber(), SCIPpropGetData(), and SCIPpropGetName().
|
static |
propagation conflict resolving method of propagator
Definition at line 3226 of file prop_obbt.c.
References result, SCIP_DIDNOTFIND, and SCIP_OKAY.
|
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.
|
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().