# source:stable/0.1/Couenne/src/bound_tightening/tightenBounds.cpp@132

Last change on this file since 132 was 132, checked in by pbelotti, 13 years ago

merged changes from trunk/131 on bound tightening. Not yet solved optimum cutting in reformulated stockcycle

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