# 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  Generated on Wed Apr 2 2014 for SCIP Doxygen Documentation by doxygen (1.8.2) © 2020 by Zuse Institute Berlin (ZIB), Imprint designed with Bootstrap