# 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-2015 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 extern 59  SCIP* scip /**< SCIP data structure */ 60  ); 61  62 #ifdef __cplusplus 63 } 64 #endif 65  66 #endif SCIP_RETCODEenum SCIP_Retcode SCIP_RETCODEDefinition: type_retcode.h:53 SCIPincludePropObbtSCIP_RETCODE SCIPincludePropObbt(SCIP *scip) SCIPstruct Scip SCIPDefinition: type_scip.h:30 scip.hSCIP callable library. Generated on Wed Jul 22 2015 for SCIP Doxygen Documentation by doxygen (1.8.6) © 2024 by Zuse Institute Berlin (ZIB), Imprint designed with Bootstrap