source: trunk/Couenne/src/two_implied_bt/CouenneTwoImplied.hpp @ 577

Last change on this file since 577 was 577, checked in by pbelotti, 10 years ago

restoring FP for tests. Changing branching point on integer variables with integer value. Fixing large branching points for variables with large (upper/lower) bounds and large LP values. Added debug code to twoImplBounds for check against optimal solutions. Added fictitious objective function of 0 when none is defined. Redeclared size_t in invmap.cpp for compatibility with MSVS.

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