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-2017 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  * After we learned a better variable bound the propagator tries to separate the solution of the current OBBT LP with
37  * the refined outer approximation in order to strengthen the learned bound. Additionally, we trigger a
38  * propagation round of SCIP after a fixed number of learned bound tightenings.
39  *
40  * Additionally, the propagator uses the dual solution of the auxiliary LPs to construct globally valid generalized
41  * variable bounds which may be propagated during the branch-and-bound search.
42  */
43 
44 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
45 
46 #ifndef __SCIP_PROP_OBBT_H__
47 #define __SCIP_PROP_OBBT_H__
48 
49 
50 #include "scip/scip.h"
51 
52 #ifdef __cplusplus
53 extern "C" {
54 #endif
55 
56 /** creates the obbt propagator and includes it in SCIP
57  *
58  * @ingroup PropagatorIncludes
59  */
60 extern
62  SCIP* scip /**< SCIP data structure */
63  );
64 
65 #ifdef __cplusplus
66 }
67 #endif
68 
69 #endif
SCIP_RETCODE SCIPincludePropObbt(SCIP *scip)
Definition: prop_obbt.c:2497
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP callable library.