source: stable/0.2/Couenne/src/bound_tightening/tightenBounds.cpp @ 159

Last change on this file since 159 was 159, checked in by pbelotti, 11 years ago

created new stable branch 0.2 from trunk (rev. 157)

File size: 6.8 KB
Line 
1/* $Id: tightenBounds.cpp 141 2009-06-03 04:19:19Z pbelotti $ */
2/*
3 * Name:    tightenBounds.cpp
4 * Author:  Pietro Belotti
5 * Purpose: bound tightening for current linear relaxation
6 *
7 * (C) Carnegie-Mellon University, 2006-08.
8 * This file is licensed under the Common Public License (CPL)
9 */
10
11#include "CglCutGenerator.hpp"
12#include "CouenneCutGenerator.hpp"
13#include "CouenneProblem.hpp"
14
15//#define DEBUG
16
17/// Bound propagation for auxiliary variables
18
19int CouenneProblem::tightenBounds (t_chg_bounds *chg_bds) const {
20
21  int nchg = 0; //< number of bounds changed for propagation
22
23  // update bounding box (which may depend on the original
24  // variables' box) for the variables whose bound is looser.
25
26  // check all auxiliary variables for changes in their upper,
27  // lower bound, depending on the bound changes of the variables
28  // they depend on
29
30  if (Jnlst () -> ProduceOutput (J_DETAILED, J_BOUNDTIGHTENING)) {
31    // ToDo: Pipe all output through journalist
32    Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
33                    "  forward  =====================\n  ");
34    int j=0;
35    for (int i=0; i < nVars (); i++) 
36      if (variables_ [i] -> Multiplicity () >= 0) {
37        Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING,
38                        "x_%03d [%+10g %+10g] ", i, 
39                        domain_. lb (i),
40                        domain_. ub (i));
41        if (!(++j % 6)) Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING,"\n  ");
42    }
43    if (j % 6) Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING,"\n");
44  }
45
46  for (int ii = 0, j = nVars (); j--; ii++) {
47
48    int i = numbering_ [ii];
49
50    if (Var (i) -> Multiplicity () <= 0) 
51      continue;
52
53    // early test to avoid a loop
54
55    if ((Lb (i) > Ub (i) + COUENNE_EPS * (1 + CoinMin (fabs (Lb (i)), fabs (Ub (i))))) || 
56        (Ub (i) < - MAX_BOUND) ||
57        (Lb (i) >   MAX_BOUND)) {
58
59      if (Jnlst()->ProduceOutput(J_ITERSUMMARY, J_BOUNDTIGHTENING)) {
60
61        Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,
62                        "pre-check: w_%d has infeasible bounds [%.10e,%.10e]. ", i, Lb (i), Ub (i));
63
64        if (Jnlst()->ProduceOutput(J_DETAILED, J_BOUNDTIGHTENING)) {
65          Var (i) -> Lb () -> print (std::cout);
66          Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
67          Var (i) -> Ub () -> print (std::cout);
68        }
69
70        Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,"\n");
71      }
72
73      return -1; // declare this node infeasible
74    }
75
76    /*if ((Var (i) -> Type () == VAR) &&
77        (Var (i) -> isInteger ())) {
78      Lb (i) = ceil  (Lb (i) - COUENNE_EPS);
79      Ub (i) = floor (Ub (i) + COUENNE_EPS);
80      }*/
81
82    if (Var (i) -> Type () == AUX) {
83        // TODO: also test if any indep variable of this expression
84        // have changed. If not, skip
85
86      CouNumber ll, uu; 
87      //ll = (*(variables_ [i] -> Lb ())) (),
88      //uu = (*(variables_ [i] -> Ub ())) ();
89
90      variables_ [i] -> Image () -> getBounds (ll, uu);
91
92      if (variables_ [i] -> isInteger ()) {
93        ll = ceil  (ll - COUENNE_EPS);
94        uu = floor (uu + COUENNE_EPS);
95      }
96
97      if (ll - uu > COUENNE_EPS * (1 + CoinMin (fabs (ll), fabs (uu)))) {
98
99        //if (Jnlst()->ProduceOutput(J_ITERSUMMARY, J_BOUNDTIGHTENING)) {
100
101        Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,
102                        "w_%d has infeasible bounds [%g,%g]: ", i, ll, uu);
103
104        if (Jnlst()->ProduceOutput(J_DETAILED, J_BOUNDTIGHTENING)) {
105          Var (i) -> Lb () -> print (std::cout);
106          Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
107          Var (i) -> Ub () -> print (std::cout);
108        }
109
110        Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,"\n");
111          //}
112
113        return -1; // declare this node infeasible
114      }
115
116      // check if lower bound got higher
117      if ((ll > - COUENNE_INFINITY) && 
118          (ll >= Lb (i) + COUENNE_EPS) &&
119          ((fabs (ll)        < COUENNE_EPS) || 
120           (fabs (Lb (i)) < COUENNE_EPS) ||
121           (fabs (ll / (Lb (i)) - 1) > COUENNE_EPS)) ) {
122
123        if (Jnlst()->ProduceOutput(J_DETAILED, J_BOUNDTIGHTENING)) {
124
125          Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
126                          "  prop L %2d [%g,(%g)] -> [%g,(%g)] (%g) ", 
127                          i, Lb (i), Ub (i), ll, uu, Lb (i) - ll);
128          Var (i) -> print (std::cout);
129
130          if (Jnlst()->ProduceOutput(J_MOREDETAILED, J_BOUNDTIGHTENING)) {
131            Jnlst()->Printf(J_MOREDETAILED, J_BOUNDTIGHTENING," := ");
132            Var (i) -> Image () -> print (std::cout);
133          }
134
135          Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
136
137          if (optimum_ && 
138              (optimum_ [i] >= Lb (i)) && 
139              (optimum_ [i] <= ll - COUENNE_EPS)) {
140
141            Jnlst()->Printf(J_STRONGWARNING, J_BOUNDTIGHTENING,
142                            "Couenne: propagating l_%d cuts optimum: [%g --> %g -X-> %g] :: ", 
143                            i, Lb (i), optimum_ [i], ll);
144            Var (i) -> Lb () -> print (std::cout);
145            Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
146            Var (i) -> Ub () -> print (std::cout);
147            Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
148          }
149        }
150
151        Lb (i) = ll;
152
153        if (ll > Ub (i) + COUENNE_EPS * (1. + CoinMin (fabs (ll), fabs (Ub (i))))) {
154          Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
155                              "just-check: w_%d has infeasible bounds [%g,%g]. ", i, Lb (i), Ub (i));
156          return -1;
157        }
158
159        chg_bds [i].setLower(t_chg_bounds::CHANGED);
160        nchg++;
161      }
162
163      // check if upper bound got lower
164      if ((uu < COUENNE_INFINITY) && 
165          (uu <= Ub (i) - COUENNE_EPS) &&
166          ((fabs (uu)      < COUENNE_EPS) || 
167           (fabs (Ub (i)) < COUENNE_EPS) ||
168           (fabs (uu / (Ub (i)) - 1) > COUENNE_EPS)) ) {
169        //      if ((uu < COUENNE_INFINITY) && (uu <= ub_ [i+j] - COUENNE_EPS)) {
170
171        /*printf ("update ubound %d: %.10e <= %.10e - %.12e (%.12e)\n",
172          i+j, uu, ub_ [i+j], COUENNE_EPS, uu - ub_ [i+j]);*/
173        /*printf ("update ubound %d: %g >= %g\n",
174          i+j, uu, ub_ [i+j]);*/
175
176        if (Jnlst()->ProduceOutput(J_DETAILED, J_BOUNDTIGHTENING)) {
177
178          Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
179                          "  prop U %2d [(%g),%g] -> [(%g),%g] (%g) ", 
180                          i, Lb (i), Ub (i), ll, uu, Ub (i) - uu);
181          Var (i) -> print (std::cout);
182
183          if (Jnlst()->ProduceOutput(J_VECTOR, J_BOUNDTIGHTENING)) {
184            Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING," := ");
185            Var (i) -> Image () -> print (std::cout);
186          }
187
188          Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
189
190          if (optimum_ && 
191              (optimum_ [i] <= Ub (i)) && 
192              (optimum_ [i] >= uu + COUENNE_EPS)) {
193
194            Jnlst()->Printf(J_STRONGWARNING, J_BOUNDTIGHTENING,
195                            "Couenne: propagating u_%d cuts optimum: [%g <-X- %g <-- %g] :: ", 
196                            i, uu, optimum_ [i], Ub (i));
197            Var (i) -> Lb () -> print (std::cout);
198            Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
199            Var (i) -> Ub () -> print (std::cout);
200            Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
201          }
202        }
203
204        Ub (i) = uu;
205
206        if (uu < Lb (i) - COUENNE_EPS) {
207          Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
208                              "just-check: w_%d has infeasible bounds [%g,%g]. ", i, Lb (i), Ub (i));
209          return -1;
210        }
211
212        chg_bds [i].setUpper(t_chg_bounds::CHANGED);
213        nchg++;
214      }
215
216      // useless if assume expression::[lu]b_ etc already point to
217      // problem::[lu]b_
218    }
219  }
220
221  if (nchg)
222    Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
223                        "  forward tightening %d changes\n", nchg);
224
225  return nchg;
226}
Note: See TracBrowser for help on using the repository browser.