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_nlobbt.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_nlobbt.h
17
* @ingroup PROPAGATORS
18
* @brief nonlinear OBBT propagator
19
* @author Benjamin Mueller
20
*
21
* In Nonlinear Optimization-Based Bound Tightening (NLOBBT), we solve auxiliary NLPs of the form
22
* \f[
23
* \min / \max \, x_i \\
24
* \f]
25
* \f[
26
* s.t. \; g_j(x) \le 0 \, \forall j=1,\ldots,m \\
27
* \f]
28
* \f[
29
* c'x \le \mathcal{U}
30
* \f]
31
* \f[
32
* x \in [\ell,u]
33
* \f]
34
*
35
* where each \f$ g_j \f$ is a convex function and \f$ \mathcal{U} \f$ the solution value of the current
36
* incumbent. Clearly, the optimal objective value of this nonlinear program provides a valid lower/upper bound on
37
* variable \f$ x_i \f$.
38
*
39
* The propagator sorts all variables w.r.t. their occurrences in convex nonlinear constraints and solves sequentially
40
* all convex NLPs. Variables which could be successfully tightened by the propagator will be prioritized in the next
41
* call of a new node in the branch-and-bound tree. By default, the propagator requires at least one nonconvex
42
* constraints to be executed. For purely convex problems, the benefit of having tighter bounds is negligible.
43
*
44
* By default, NLOBBT is only applied for non-binary variables. A reason for this can be found <a
45
* href="http://dx.doi.org/10.1007/s10898-016-0450-4">here </a>. Variables which do not appear non-linearly in the
46
* nonlinear constraints will not be considered even though they might lead to additional tightenings.
47
*
48
* After solving the NLP to optimize \f$ x_i \f$ we try to exploit the dual information to generate a globally valid
49
* inequality, called Generalized Variable Bound (see @ref prop_genvbounds.h). Let \f$ \lambda_j \f$, \f$ \mu \f$, \f$
50
* \alpha \f$, and \f$ \beta \f$ be the dual multipliers for the constraints of the NLP where \f$ \alpha \f$ and \f$
51
* \beta \f$ correspond to the variable bound constraints. Because of the convexity of \f$ g_j \f$ we know that
52
*
53
* \f[
54
* g_j(x) \ge g_j(x^*) + \nabla g_j(x^*)(x-x^*)
55
* \f]
56
*
57
* holds for every \f$ x^* \in [\ell,u] \f$. Let \f$ x^* \f$ be the optimal solution after solving the NLP for the case
58
* of minimizing \f$ x_i \f$ (similiar for the case of maximizing \f$ x_i \f$). Since the NLP is convex we know that the
59
* KKT conditions
60
*
61
* \f[
62
* e_i + \lambda' \nabla g(x^*) + \mu' c + \alpha - \beta = 0
63
* \f]
64
* \f[
65
* \lambda_j g_j(x^*) = 0
66
* \f]
67
*
68
* hold. Aggregating the inequalities \f$ x_i \ge x_i \f$ and \f$ g_j(x) \le 0 \f$ leads to the inequality
69
*
70
* \f[
71
* x_i \ge x_i + \sum_{j} g_j(x_i)
72
* \f]
73
*
74
* Instead of calling the (expensive) propagator during the tree search we can use this inequality to derive further
75
* reductions on \f$ x_i \f$. Multiplying the first KKT condition by \f$ (x - x^*) \f$ and using the fact that each
76
* \f$ g_j \f$ is convex we can rewrite the previous inequality to
77
*
78
* \f[
79
* x_i \ge (\beta - \alpha)'x + (e_i + \alpha - \beta) x^* + \mu \mathcal{U}.
80
* \f]
81
*
82
* which is passed to the genvbounds propagator. Note that if \f$ \alpha_i \neq \beta_i \f$ we know that the bound of
83
* \f$ x_i \f$ is the proof for optimality and thus no useful genvbound can be found.
84
*/
85
86
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
87
88
#ifndef __SCIP_PROP_NLOBBT_H__
89
#define __SCIP_PROP_NLOBBT_H__
90
91
92
#include "
scip/scip.h
"
93
94
#ifdef __cplusplus
95
extern
"C"
{
96
#endif
97
98
/** creates the nlobbt propagator and includes it in SCIP
99
*
100
* @ingroup PropagatorIncludes
101
*/
102
extern
103
SCIP_RETCODE
SCIPincludePropNlobbt
(
104
SCIP
*
scip
/**< SCIP data structure */
105
);
106
107
#ifdef __cplusplus
108
}
109
#endif
110
111
#endif
Scip
Definition:
struct_scip.h:58
SCIPincludePropNlobbt
SCIP_RETCODE SCIPincludePropNlobbt(SCIP *scip)
Definition:
prop_nlobbt.c:702
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition:
type_retcode.h:53
scip
Definition:
objbranchrule.h:33
scip.h
SCIP callable library.