Toggle navigation
SCIP Optimization Suite
SCIP
SoPlex
ZIMPL
UG
GCG
Documentation
SCIP 9.2.0
SCIP 8.1.0
SCIP 7.0.3
SCIP 6.0.2
SCIP 5.0.1
SCIP 4.0.1
SCIP 3.2.1
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
61
SCIP_RETCODE
SCIPincludePropObbt
(
62
SCIP
*
scip
/**< SCIP data structure */
63
);
64
65
#ifdef __cplusplus
66
}
67
#endif
68
69
#endif
Scip
Definition:
struct_scip.h:58
SCIPincludePropObbt
SCIP_RETCODE SCIPincludePropObbt(SCIP *scip)
Definition:
prop_obbt.c:2497
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition:
type_retcode.h:53
scip
Definition:
objbranchrule.h:33
scip.h
SCIP callable library.