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 |
| #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.
Definition at line 128 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 190 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 262 of file prop_obbt.c.
determines, whether a variable is already locally fixed
| scip | SCIP data structure |
| var | variable to check |
Definition at line 312 of file prop_obbt.c.
|
static |
sets objective to minimize or maximize a single variable
Definition at line 322 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 369 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 396 of file prop_obbt.c.
References Bound::boundtype, getFilterCoef(), MAX, MIN, NULL, 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 426 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 500 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 672 of file prop_obbt.c.
References NULL.
Referenced by filterExistingLP().
|
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 695 of file prop_obbt.c.
References bound, 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(), SCIPdebugMsg, SCIPgetDepth(), SCIPgetNLPIterations(), SCIPgetNVars(), SCIPgetVarObjProbing(), SCIPgetVars(), SCIPinProbing(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetCol(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetName(), SCIPvarGetUbLocal(), setObjProbing(), solveLP(), TRUE, and Bound::var.
|
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 814 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 975 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 1119 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 1186 of file prop_obbt.c.
|
static |
comparison method for two bounds w.r.t. their scores
Definition at line 1247 of file prop_obbt.c.
|
static |
comparison method for two bounds w.r.t. their boundtype
Definition at line 1257 of file prop_obbt.c.
References NULL, 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 1283 of file prop_obbt.c.
References Bound::boundtype, NULL, REALABS, SCIP_BOUNDTYPE_LOWER, SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetUbLocal(), and Bound::var.
evaluates a bound for the current LP solution
Definition at line 1299 of file prop_obbt.c.
|
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 1315 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 1367 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 1449 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 1688 of file prop_obbt.c.
Referenced by SCIP_DECL_PROPEXEC().
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 1910 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 1953 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 2023 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 2165 of file prop_obbt.c.
|
static |
initializes interesting bounds
| scip | SCIP data structure |
| propdata | data of the obbt propagator |
Definition at line 2181 of file prop_obbt.c.
Referenced by SCIP_DECL_PROPEXEC().
|
static |
solving process initialization method of propagator (called when branch and bound process is about to begin)
Definition at line 2300 of file prop_obbt.c.
|
static |
execution method of propagator
Definition at line 2328 of file prop_obbt.c.
References applyObbt(), initBounds(), MAX, NULL, 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 2426 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 2435 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 2474 of file prop_obbt.c.