SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
optimization-based bound tightening propagator
In Optimization-Based Bound Tightening (OBBT), we solve auxiliary LPs of the form
\[ \min / \max \, \{ x_i \mid x \in P' \}, \]
where \(P'\) is the current LP relaxation restricted by the primal cutoff constraint \(c^T x <= z\), \(z\) the current cutoff bound. Trivially, the optimal objective value of this LP provides a valid lower/upper bound on variable \(x_i\).
Since solving LPs may be expensive, the propagator inspects solutions \(x \in P'\) and does not run for variable bounds which are tight at \(x\): First, we check SCIP's last LP relaxation solution. Second, we solve a sequence of filtering LP's \(\min / \max \, \{ \sum w_i \, x_i \mid x \in P' \}\) in order to push several variables towards one of their bounds in one LP solve. Third, we inspect all solutions of the auxiliary LPs solved along the way.
By default, OBBT is only applied for nonbinary variables that occur in nonlinear constraints.
After we learned a better variable bound the propagator tries to separate the solution of the current OBBT LP with the refined outer approximation in order to strengthen the learned bound. Additionally, we trigger a propagation round of SCIP after a fixed number of learned bound tightenings.
Additionally, the propagator uses the dual solution of the auxiliary LPs to construct globally valid generalized variable bounds which may be propagated during the branch-and-bound search.
Definition in file prop_obbt.h.
#include "scip/scip.h"Go to the source code of this file.
Functions | |
| SCIP_RETCODE | SCIPincludePropObbt (SCIP *scip) |