Solving Constraint Integer Programs

prop_obbt.h File Reference

Detailed Description

optimization-based bound tightening propagator

Stefan Weltge

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.

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.


SCIP_RETCODE SCIPincludePropObbt (SCIP *scip)

Function Documentation

SCIP_RETCODE SCIPincludePropObbt ( SCIP scip)

creates the obbt propagator and includes it in SCIP

scipSCIP data structure