SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
optimization-based bound tightening propagator
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.
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 } |
| #define PROP_NAME "obbt" |
Definition at line 49 of file prop_obbt.c.
Referenced by SCIP_DECL_PROPCOPY().
| #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 DEFAULT_CREATE_BILININEQS TRUE |
solve auxiliary LPs in order to find valid inequalities for bilinear terms?
Definition at line 104 of file prop_obbt.c.
| #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 105 of file prop_obbt.c.
| #define DEFAULT_MINNONCONVEXITY 1e-1 |
minimum nonconvexity for choosing a bilinear term
Definition at line 106 of file prop_obbt.c.
| #define DEFAULT_RANDSEED 149 |
initial random seed
Definition at line 107 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 114 of file prop_obbt.c.
Definition at line 133 of file prop_obbt.c.
Definition at line 144 of file prop_obbt.c.
| typedef struct BilinBound BILINBOUND |
Definition at line 158 of file prop_obbt.c.
| enum Corner |
| Enumerator | |
|---|---|
| LEFTBOTTOM | |
| RIGHTBOTTOM | |
| RIGHTTOP | |
| LEFTTOP | |
| FILTERED | |
Definition at line 136 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 228 of file prop_obbt.c.
Referenced by filterExistingLP().
|
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 300 of file prop_obbt.c.
determines, whether a variable is already locally fixed
| scip | SCIP data structure |
| var | variable to check |
Definition at line 350 of file prop_obbt.c.
|
static |
sets objective to minimize or maximize a single variable
Definition at line 360 of file prop_obbt.c.
Referenced by filterExistingLP().
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 407 of file prop_obbt.c.
|
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 434 of file prop_obbt.c.
References Bound::boundtype, getFilterCoef(), MAX, SCIP_Real, SCIPdebugMsg, and SCIPgetNLPIterations().
|
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 464 of file prop_obbt.c.
Referenced by getIterationsLeft().
|
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 538 of file prop_obbt.c.
Referenced by filterExistingLP().
|
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 710 of file prop_obbt.c.
Referenced by filterExistingLP().
|
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 733 of file prop_obbt.c.
References FILTERED, getCorners(), LEFTBOTTOM, LEFTTOP, RIGHTBOTTOM, RIGHTTOP, SCIP_Real, SCIPABORT, SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().
Referenced by filterExistingLP().
|
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 771 of file prop_obbt.c.
Referenced by getCorner().
|
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 813 of file prop_obbt.c.
References bound, Bound::boundtype, createGenVBound(), Bound::done, BilinBound::done, exchangeBounds(), Bound::filtered, FILTERED, BilinBound::filtered, filterRound(), Bound::found, getCorner(), LEFTBOTTOM, LEFTTOP, REALABS, RIGHTBOTTOM, RIGHTTOP, SCIP_BASESTAT_BASIC, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPchgVarObjProbing(), SCIPcolGetBasisStatus(), SCIPdebug, SCIPdebugMessage, SCIPdebugMsg, SCIPgetDepth(), SCIPgetNLPIterations(), SCIPgetNVars(), SCIPgetVarObjProbing(), SCIPgetVars(), SCIPinProbing(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), setObjProbing(), solveLP(), TRUE, Bound::var, BilinBound::x, and BilinBound::y.
|
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 986 of file prop_obbt.c.
Referenced by filterExistingLP().
|
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 1147 of file prop_obbt.c.
|
static |
applies possible bound changes that were found
| scip | SCIP data structure |
| propdata | data of the obbt propagator |
| result | result pointer |
Definition at line 1291 of file prop_obbt.c.
|
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 1358 of file prop_obbt.c.
|
static |
comparison method for two bounds w.r.t. their scores
Definition at line 1419 of file prop_obbt.c.
|
static |
comparison method for two bilinear term bounds w.r.t. their scores
Definition at line 1429 of file prop_obbt.c.
|
static |
comparison method for two bounds w.r.t. their boundtype
Definition at line 1439 of file prop_obbt.c.
References SCIP_OKAY, SCIPdebugMsg, and SCIPsortDownPtr().
|
static |
sort the propdata->bounds array with their distance or their boundtype key
| scip | SCIP data structure |
| propdata | propagator data |
Definition at line 1465 of file prop_obbt.c.
References Bound::boundtype, REALABS, SCIP_BOUNDTYPE_LOWER, SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetUbLocal(), and Bound::var.
evaluates a bound for the current LP solution
Definition at line 1481 of file prop_obbt.c.
References SCIP_Real.
|
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 1497 of file prop_obbt.c.
|
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 1549 of file prop_obbt.c.
|
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 1631 of file prop_obbt.c.
|
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 1870 of file prop_obbt.c.
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) |
Definition at line 2124 of file prop_obbt.c.
References applyObbtBilinear(), FALSE, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPaddRowProbing(), SCIPaddVarToRow(), SCIPbacktrackProbing(), SCIPchgVarObjProbing(), SCIPcreateEmptyRowUnspec(), SCIPdebugMsg, SCIPgetLPSolstat(), SCIPinProbing(), SCIPisFeasEQ(), SCIPisFeasZero(), SCIPisHugeValue(), SCIPnewProbingNode(), SCIPreleaseRow(), SCIProwGetDualsol(), SCIPsolveProbingLP(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPwarningMessage(), and TRUE.
|
static |
| scip | SCIP data structure |
| propdata | data of the obbt propagator |
| itlimit | LP iteration limit (-1: no limit) |
| result | result pointer |
Definition at line 2253 of file prop_obbt.c.
Referenced by SCIP_DECL_PROPEXEC(), and solveBilinearLP().
computes the score of a bound
| scip | SCIP data structure |
| bound | pointer of bound |
| nlcount | number of nonlinear constraints containing the bounds variable |
| maxnlcount | maximal number of nonlinear constraints a variable appears in |
Definition at line 2413 of file prop_obbt.c.
|
static |
computes the score of a bilinear term bound
| scip | SCIP data structure |
| randnumgen | random number generator |
| bilinbound | bilinear term bound |
| nbilinterms | maximal number of bilinear terms in all quadratic constraints |
Definition at line 2456 of file prop_obbt.c.
|
static |
count the variables which appear in non-convex term of nlrow
| scip | SCIP data structure |
| nlcounts | store the number each variable appears in a non-convex term |
| nlrow | nonlinear row |
Definition at line 2501 of file prop_obbt.c.
|
static |
count how often each variable appears in a non-convex term
| scip | SCIP data structure |
| nlcounts | store the number each variable appears in a non-convex term |
Definition at line 2571 of file prop_obbt.c.
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) |
Definition at line 2729 of file prop_obbt.c.
|
static |
initializes interesting bounds
| scip | SCIP data structure |
| propdata | data of the obbt propagator |
Definition at line 2745 of file prop_obbt.c.
Referenced by SCIP_DECL_PROPEXEC().
|
static |
copy method for propagator plugins (called when SCIP copies plugins)
Definition at line 2951 of file prop_obbt.c.
References PROP_NAME, SCIPpropGetData(), and SCIPpropGetName().
|
static |
solving process initialization method of propagator (called when branch and bound process is about to begin)
Definition at line 2965 of file prop_obbt.c.
|
static |
execution method of propagator
Definition at line 2996 of file prop_obbt.c.
References applyObbt(), applyObbtBilinear(), initBounds(), MAX, SCIP_CALL, SCIP_DECL_PROPEXITSOL(), SCIP_DECL_PROPRESPROP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIPallColsInLP(), SCIPallowObjProp(), SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPSolstat(), SCIPgetNRootLPIterations(), SCIPgetProbName(), SCIPinProbing(), SCIPnodeGetNumber(), and SCIPpropGetData().
|
static |
propagation conflict resolving method of propagator
Definition at line 3112 of file prop_obbt.c.
Referenced by SCIP_DECL_PROPEXEC().
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 3121 of file prop_obbt.c.
Referenced by SCIP_DECL_PROPEXEC().
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 3177 of file prop_obbt.c.