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.
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
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
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
Note: See TracBrowser for help on using the repository browser.