# source:trunk/Couenne/src/bound_tightening/twoImpliedBT/CouenneTwoImplied.hpp@945

Last change on this file since 945 was 945, checked in by stefan, 8 years ago

generateCuts in Cgl >= 0.58 will not be const anymore

• Property svn:eol-style set to native
• Property svn:keywords set to Author Date Id Revision
File size: 7.8 KB
Line
1/* $Id: CouenneTwoImplied.hpp 945 2013-04-06 20:25:21Z 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.
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
21namespace Ipopt {
22  template <class T> class SmartPtr;
23  class OptionsList;
24}
25
26namespace 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
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
Note: See TracBrowser for help on using the repository browser.