Scippy

SCIP

Solving Constraint Integer Programs

prop_obbt.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file prop_obbt.h
17  * @ingroup PROPAGATORS
18  * @brief optimization-based bound tightening propagator
19  * @author Stefan Weltge
20  *
21  * In Optimization-Based Bound Tightening (OBBT), we solve auxiliary LPs of the form
22  * \f[
23  * \min / \max \, \{ x_i \mid x \in P' \},
24  * \f]
25  * where \f$P'\f$ is the current LP relaxation restricted by the primal cutoff constraint \f$c^T x <= z\f$, \f$z\f$ the
26  * current cutoff bound. Trivially, the optimal objective value of this LP provides a valid lower/upper bound on
27  * variable \f$x_i\f$.
28  *
29  * Since solving LPs may be expensive, the propagator inspects solutions \f$x \in P'\f$ and does not run for variable
30  * bounds which are tight at \f$x\f$: First, we check SCIP's last LP relaxation solution. Second, we solve a sequence of
31  * filtering LP's \f$\min / \max \, \{ \sum w_i \, x_i \mid x \in P' \}\f$ in order to push several variables towards
32  * one of their bounds in one LP solve. Third, we inspect all solutions of the auxiliary LPs solved along the way.
33  *
34  * By default, OBBT is only applied for nonbinary variables that occur in nonlinear constraints.
35  *
36  * Additionally, the propagator uses the dual solution of the auxiliary LPs to construct globally valid generalized
37  * variable bounds which may be propagated during the branch-and-bound search.
38  */
39 
40 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
41 
42 #ifndef __SCIP_PROP_OBBT_H__
43 #define __SCIP_PROP_OBBT_H__
44 
45 
46 #include "scip/scip.h"
47 
48 #ifdef __cplusplus
49 extern "C" {
50 #endif
51 
52 /** creates the obbt propagator and includes it in SCIP */
53 extern
55  SCIP* scip /**< SCIP data structure */
56  );
57 
58 #ifdef __cplusplus
59 }
60 #endif
61 
62 #endif
63