1 | /* $Id: CouenneTwoImplied.hpp 946 2013-04-15 22:20:38Z stefan $ |
---|
2 | * |
---|
3 | * Name: CouenneTwoImplied.hpp |
---|
4 | * Author: Pietro Belotti |
---|
5 | * Purpose: Bound Tightening using pairs of linear inequalities or equations |
---|
6 | * |
---|
7 | * (C) Pietro Belotti, 2010. |
---|
8 | * This file is licensed under the Eclipse Public License (EPL) |
---|
9 | */ |
---|
10 | |
---|
11 | #ifndef COUENNETWOIMPLIED_HPP |
---|
12 | #define COUENNETWOIMPLIED_HPP |
---|
13 | |
---|
14 | #include "BonRegisteredOptions.hpp" |
---|
15 | |
---|
16 | #include "CglConfig.h" |
---|
17 | #include "CglCutGenerator.hpp" |
---|
18 | #include "OsiRowCut.hpp" |
---|
19 | #include "CouenneJournalist.hpp" |
---|
20 | |
---|
21 | namespace Ipopt { |
---|
22 | template <class T> class SmartPtr; |
---|
23 | class OptionsList; |
---|
24 | } |
---|
25 | |
---|
26 | namespace Couenne { |
---|
27 | |
---|
28 | class CouenneProblem; |
---|
29 | |
---|
30 | /** |
---|
31 | Cut Generator for implied bounds derived from pairs of linear (in)equalities |
---|
32 | |
---|
33 | Implied bounds usually work on a SINGLE inequality of the form |
---|
34 | |
---|
35 | \f$ \ell_j \le \sum_{i \in N_+} a_{ji} x_i |
---|
36 | + \sum_{i \in N_-} a_{ji} x_i \le u_j \f$ |
---|
37 | |
---|
38 | where \f$ a_{ji} > 0 \f$ for \f$ i \in N_+ \f$ and \f$ a_{ji} < 0 \f$ for \f$ i \in N_- \f$ , and allow |
---|
39 | one to infer better bounds \f$ [x^L_i, x^U_i] \f$ on all variables with |
---|
40 | nonzero coefficients: |
---|
41 | |
---|
42 | (1) \f$ x^L_i \ge (\ell_j - \sum_{i \in N_+} a_{ji} x^U_i |
---|
43 | - \sum_{i \in N_-} a_{ji} x^L_i ) / a_{ji} \qquad \forall i \in N_+ \f$ |
---|
44 | |
---|
45 | (2) \f$ x^U_i \le (u_j - \sum_{i \in N_+} a_{ji} x^L_i |
---|
46 | - \sum_{i \in N_-} a_{ji} x^U_i ) / a_{ji} \qquad \forall i \in N_+ \f$ |
---|
47 | |
---|
48 | |
---|
49 | (3) \f$ x^L_i \ge (u_j - \sum_{i \in N_+} a_{ji} x^L_i |
---|
50 | - \sum_{i \in N_-} a_{ji} x^U_i ) / a_{ji} \qquad \forall i \in N_- \f$ |
---|
51 | |
---|
52 | (4) \f$ x^U_i \le (\ell_j - \sum_{i \in N_+} a_{ji} x^U_i |
---|
53 | - \sum_{i \in N_-} a_{ji} x^L_i ) / a_{ji} \qquad \forall i \in N_+ \f$ |
---|
54 | |
---|
55 | Consider now two inequalities: |
---|
56 | |
---|
57 | \f$ \ell_h \le \sum_{i \in N^1_+} a_{hi} x_i + \sum_{i \in N^1_-} a_{hi} x_i \le u_h \f$ |
---|
58 | |
---|
59 | \f$ \ell_k \le \sum_{i \in N^2_+} a_{ki} x_i + \sum_{i \in N^2_-} a_{ki} x_i \le u_k \f$ |
---|
60 | |
---|
61 | and their CONVEX combination using \f$ \alpha \f$ and \f$ 1 - |
---|
62 | \alpha \f$ , where \f$ \alpha \in [0,1] \f$ : |
---|
63 | |
---|
64 | \f$ \ell' \le \sum_{i \in N} b_i x_i \le u' \f$ |
---|
65 | |
---|
66 | with \f$ N = N^1_+\cup N^1_-\cup N^2_+\cup N^2_- \f$ , \f$ \ell' = |
---|
67 | \alpha \ell_h + (1-\alpha) \ell_k \f$ , and \f$ u' = \alpha u_h + (1-\alpha) u_k \f$ . As |
---|
68 | an example where this might be useful, consider |
---|
69 | |
---|
70 | \f$ x + y \ge 2 \f$ |
---|
71 | |
---|
72 | \f$ x - y \ge 1 \f$ |
---|
73 | |
---|
74 | with \f$ x \in [0,4] \f$ and \f$ y \in [0,1] \f$ . (This is similar to an example |
---|
75 | given in Tawarmalani and Sahinidis to explain FBBT != OBBT, I |
---|
76 | believe.) The sum of the two above inequalities gives \f$ x \ge 1.5 \f$ , |
---|
77 | while using only the implied bounds on the single inequalities |
---|
78 | gives \f$ x \ge 1 \f$ . |
---|
79 | |
---|
80 | The key consideration here is that the \f$ b_i \f$ coefficients, \f$ \ell' \f$ , and |
---|
81 | \f$ u' \f$ are functions of \f$ \alpha \f$ , which determines which, among (1)-(4), |
---|
82 | to apply. In general, |
---|
83 | |
---|
84 | if \f$ b_i > 0 \f$ then |
---|
85 | |
---|
86 | \f$ x^L_i \ge (l' - \sum_{j \in N_+'} b_j x^U_j |
---|
87 | - \sum_{j \in N_-'} b_j x^L_j) / b_i \f$ , |
---|
88 | |
---|
89 | \f$ x^U_i \le (u' - \sum_{j \in N_+'} b_j x^L_j |
---|
90 | - \sum_{j \in N_-'} b_j x^U_j) / b_i \f$ ; |
---|
91 | |
---|
92 | if \f$ b_i < 0 \f$ then |
---|
93 | |
---|
94 | \f$ x^L_i \ge (l' - \sum_{j \in N_+'} b_j x^U_j |
---|
95 | - \sum_{j \in N_-'} b_j x^L_j) / b_i \f$ , |
---|
96 | |
---|
97 | \f$ x^U_i \le (u' - \sum_{j \in N_+'} b_j x^L_j |
---|
98 | - \sum_{j \in N_-'} b_j x^U_j) / b_i \f$ . |
---|
99 | |
---|
100 | Each lower/upper bound is therefore a piecewise rational function |
---|
101 | of \f$ \alpha \f$ , given that \f$ b_i \f$ and the content of \f$ |
---|
102 | N_+' \f$ and \f$ N_-' \f$ depend on \f$ \alpha \f$ . These |
---|
103 | functions are continuous (easy to prove) but not differentiable |
---|
104 | at some points of \f$ [0,1] \f$ . |
---|
105 | |
---|
106 | The purpose of this procedure is to find the maximum of the lower |
---|
107 | bounding function and the minimum of the upper bounding function. |
---|
108 | |
---|
109 | Divide the interval \f$ [0,1] \f$ into at most \f$ m+1 \f$ |
---|
110 | intervals (where \f$ m \f$ is the number of coefficients not |
---|
111 | identically zero, or the number of \f$ b_i \f$ that are nonzero |
---|
112 | for at least one value of \f$ \alpha \f$ ). The limits \f$ c_i |
---|
113 | \f$ of the subintervals are the zeros of each coefficient, |
---|
114 | i.e. the values of \f$ \alpha \f$ such that \f$ \alpha a_{ki} + |
---|
115 | (1-\alpha) a_{hi} = 0 \f$ , or \f$ c_i = \frac{-a_{hi}}{a_{ki} - |
---|
116 | a_{hi}} \f$ . |
---|
117 | |
---|
118 | Sorting these values gives us something to do on every interval |
---|
119 | \f$ [c_j, c_{j+1}] \f$ when computing a new value of \f$ x^L_i |
---|
120 | \f$ and \f$ x^U_i \f$ , which I'll denote \f$ L_i \f$ and \f$ |
---|
121 | U_i \f$ in the following. |
---|
122 | |
---|
123 | 0) if \f$ c_j = c_i \f$ then |
---|
124 | - compute \f$ VL = \lim_{c_j \to \alpha} L_i (\alpha) \f$ |
---|
125 | - if \f$ = +\infty \f$ , infeasible |
---|
126 | else compute derivative DL (should be \f$ +\infty \f$ ) |
---|
127 | |
---|
128 | 1) else |
---|
129 | |
---|
130 | - compute \f$ VL = \lim_{\alpha \to c_j} L_i (\alpha) \f$ (can be |
---|
131 | retrieved from previous interval as \f$ L_i (\alpha) \f$ is |
---|
132 | continuous) |
---|
133 | |
---|
134 | - compute \f$ DL = \lim_{\alpha \to c_j} dL_i (\alpha) \f$ |
---|
135 | |
---|
136 | update \f$ x^L \f$ with VL if necessary. |
---|
137 | |
---|
138 | 2) if \f$ c_{j+1} = c_i \f$ then |
---|
139 | |
---|
140 | - compute \f$ VR = \lim_{\alpha \to c_{j+1}} L_i (\alpha) \f$ |
---|
141 | |
---|
142 | - if = \f$ +\infty \f$ , infeasible else compute derivative DR (should be |
---|
143 | \f$ -\infty \f$ ) |
---|
144 | |
---|
145 | 3) else |
---|
146 | - compute \f$ VR = \lim_{\alpha \to c_{j+1}} L_i (\alpha) \f$ |
---|
147 | - compute \f$ DR = \lim_{\alpha \to c_{j+1}} dL_i (\alpha) \f$ |
---|
148 | |
---|
149 | update \f$ x^L \f$ with VR if necessary. |
---|
150 | |
---|
151 | if \f$ DL > 0 \f$ and \f$ DR < 0 \f$ , there might be a maximum |
---|
152 | in between, otherwise continue to next interval |
---|
153 | |
---|
154 | compute internal maximum VI, update \f$ x^L \f$ with VI if |
---|
155 | necessary. |
---|
156 | |
---|
157 | |
---|
158 | Apply a similar procedure for the upper bound |
---|
159 | |
---|
160 | This should be applied for any \f$ h,k,i \f$ , therefore we might |
---|
161 | have a lot to do. First, select possible pairs \f$ (h,k) \f$ |
---|
162 | among those for which there exists at least one variable that |
---|
163 | satisfies neither of the following conditions: |
---|
164 | |
---|
165 | a) same sign coefficient, constraints \f$ (h,k) \f$ both \f$ \ge |
---|
166 | \f$ or both \f$ \le \f$ |
---|
167 | |
---|
168 | b) opposite sign coefficient, constraints \f$ (h,k) \f$ \f$ |
---|
169 | (\le,\ge) \f$ or \f$ (\ge,\le) \f$ |
---|
170 | |
---|
171 | as in those cases, no \f$ c_i \f$ would be in \f$ [0,1] \f$ |
---|
172 | */ |
---|
173 | |
---|
174 | class CouenneTwoImplied: public CglCutGenerator { |
---|
175 | |
---|
176 | public: |
---|
177 | |
---|
178 | /// constructor |
---|
179 | CouenneTwoImplied (CouenneProblem *, |
---|
180 | JnlstPtr, |
---|
181 | const Ipopt::SmartPtr <Ipopt::OptionsList>); |
---|
182 | |
---|
183 | /// copy constructor |
---|
184 | CouenneTwoImplied (const CouenneTwoImplied &); |
---|
185 | |
---|
186 | /// destructor |
---|
187 | ~CouenneTwoImplied (); |
---|
188 | |
---|
189 | /// clone method (necessary for the abstract CglCutGenerator class) |
---|
190 | CouenneTwoImplied *clone () const |
---|
191 | {return new CouenneTwoImplied (*this);} |
---|
192 | |
---|
193 | /// the main CglCutGenerator |
---|
194 | void generateCuts (const OsiSolverInterface &, |
---|
195 | OsiCuts &, |
---|
196 | const CglTreeInfo = CglTreeInfo ()) |
---|
197 | #if CGL_VERSION_MAJOR == 0 && CGL_VERSION_MINOR <= 57 |
---|
198 | const |
---|
199 | #endif |
---|
200 | ; |
---|
201 | |
---|
202 | /// Add list of options to be read from file |
---|
203 | static void registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions); |
---|
204 | |
---|
205 | protected: |
---|
206 | |
---|
207 | /// pointer to problem data structure (used for post-BT) |
---|
208 | CouenneProblem *problem_; |
---|
209 | |
---|
210 | /// Journalist |
---|
211 | JnlstPtr jnlst_; |
---|
212 | |
---|
213 | /// maximum number of trials in every call |
---|
214 | int nMaxTrials_; |
---|
215 | |
---|
216 | /// Total CPU time spent separating cuts |
---|
217 | mutable double totalTime_; |
---|
218 | |
---|
219 | /// CPU time spent columning the row formulation |
---|
220 | mutable double totalInitTime_; |
---|
221 | |
---|
222 | /// first call indicator |
---|
223 | mutable bool firstCall_; |
---|
224 | |
---|
225 | /// Depth of the BB tree where to start decreasing chance of running this |
---|
226 | int depthLevelling_; |
---|
227 | |
---|
228 | /// Depth of the BB tree where stop separation |
---|
229 | int depthStopSeparate_; |
---|
230 | }; |
---|
231 | } |
---|
232 | |
---|
233 | #endif |
---|