source: trunk/Couenne/src/bound_tightening/tightenBounds.cpp @ 112

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

isolate restoreUnused to when there is at least one unused -- takes care of reformulated stockcycle problem (thanks to C. D'Ambrosio for the bug report). Check linear terms before adding a full exprGroup -- need a constructor pilot. Quicker solution feasibility check (with initial integrality check).

File size: 6.6 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.
7 * This file is licensed under the Common Public License (CPL)
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_DETAILED, J_BOUNDTIGHTENING)) {
30    // ToDo: Pipe all output through journalist
31    Jnlst()->Printf(J_DETAILED, 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_VECTOR, J_BOUNDTIGHTENING,
37                        "x_%03d [%+10g %+10g] ", i, 
38                        domain_. lb (i),
39                        domain_. ub (i));
40        if (!(++j % 6)) Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING,"\n  ");
41    }
42    if (j % 6) Jnlst()->Printf(J_VECTOR, 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) || 
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      Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,"\n");
70        //}
71
72      return -1; // declare this node infeasible
73    }
74
75    /*if ((Var (i) -> Type () == VAR) &&
76        (Var (i) -> isInteger ())) {
77      Lb (i) = ceil  (Lb (i) - COUENNE_EPS);
78      Ub (i) = floor (Ub (i) + COUENNE_EPS);
79      }*/
80
81    if (Var (i) -> Type         () == AUX) {
82        // TODO: also test if any indep variable of this expression
83        // have changed. If not, skip
84
85      CouNumber ll, uu; 
86      //ll = (*(variables_ [i] -> Lb ())) (),
87      //uu = (*(variables_ [i] -> Ub ())) ();
88
89      variables_ [i] -> Image () -> getBounds (ll, uu);
90
91      if (variables_ [i] -> isInteger ()) {
92        ll = ceil  (ll - COUENNE_EPS);
93        uu = floor (uu + COUENNE_EPS);
94      }
95
96      if (ll > uu + COUENNE_EPS) {
97
98        //if (Jnlst()->ProduceOutput(J_ITERSUMMARY, J_BOUNDTIGHTENING)) {
99
100        Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,
101                        "w_%d has infeasible bounds [%g,%g]: ", i, ll, uu);
102
103        if (Jnlst()->ProduceOutput(J_DETAILED, J_BOUNDTIGHTENING)) {
104          Var (i) -> Lb () -> print (std::cout);
105          Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
106          Var (i) -> Ub () -> print (std::cout);
107        }
108
109        Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,"\n");
110          //}
111
112        return -1; // declare this node infeasible
113      }
114
115      // check if lower bound got higher
116      if ((ll > - COUENNE_INFINITY) && 
117          (ll >= Lb (i) + COUENNE_EPS) &&
118          ((fabs (ll)        < COUENNE_EPS) || 
119           (fabs (Lb (i)) < COUENNE_EPS) ||
120           (fabs (ll / (Lb (i)) - 1) > COUENNE_EPS)) ) {
121
122        if (Jnlst()->ProduceOutput(J_DETAILED, J_BOUNDTIGHTENING)) {
123
124          Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
125                          "  prop L %2d [%g,(%g)] -> [%g,(%g)] (%g) ", 
126                          i, Lb (i), Ub (i), ll, uu, Lb (i) - ll);
127          Var (i) -> print (std::cout);
128
129          if (Jnlst()->ProduceOutput(J_MOREDETAILED, J_BOUNDTIGHTENING)) {
130            Jnlst()->Printf(J_MOREDETAILED, J_BOUNDTIGHTENING," := ");
131            Var (i) -> Image () -> print (std::cout);
132          }
133
134          Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
135
136          if (optimum_ && 
137              (optimum_ [i] >= Lb (i)) && 
138              (optimum_ [i] <= ll - COUENNE_EPS)) {
139
140            Jnlst()->Printf(J_STRONGWARNING, J_BOUNDTIGHTENING,
141                            "Couenne: propagating l_%d cuts optimum: [%g --> %g -X-> %g] :: ", 
142                            i, Lb (i), optimum_ [i], ll);
143            Var (i) -> Lb () -> print (std::cout);
144            Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
145            Var (i) -> Ub () -> print (std::cout);
146            Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
147          }
148        }
149
150        Lb (i) = ll;
151
152        if (ll > Ub (i) + COUENNE_EPS) {
153          Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
154                              "just-check: w_%d has infeasible bounds [%g,%g]. ", i, Lb (i), Ub (i));
155          return -1;
156        }
157
158        chg_bds [i].setLower(t_chg_bounds::CHANGED);
159        nchg++;
160      }
161
162      // check if upper bound got lower
163      if ((uu < COUENNE_INFINITY) && 
164          (uu <= Ub (i) - COUENNE_EPS) &&
165          ((fabs (uu)      < COUENNE_EPS) || 
166           (fabs (Ub (i)) < COUENNE_EPS) ||
167           (fabs (uu / (Ub (i)) - 1) > COUENNE_EPS)) ) {
168        //      if ((uu < COUENNE_INFINITY) && (uu <= ub_ [i+j] - COUENNE_EPS)) {
169
170        /*printf ("update ubound %d: %.10e <= %.10e - %.12e (%.12e)\n",
171          i+j, uu, ub_ [i+j], COUENNE_EPS, uu - ub_ [i+j]);*/
172        /*printf ("update ubound %d: %g >= %g\n",
173          i+j, uu, ub_ [i+j]);*/
174
175        if (Jnlst()->ProduceOutput(J_DETAILED, J_BOUNDTIGHTENING)) {
176
177          Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
178                          "  prop U %2d [(%g),%g] -> [(%g),%g] (%g) ", 
179                          i, Lb (i), Ub (i), ll, uu, Ub (i) - uu);
180          Var (i) -> print (std::cout);
181
182          if (Jnlst()->ProduceOutput(J_VECTOR, J_BOUNDTIGHTENING)) {
183            Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING," := ");
184            Var (i) -> Image () -> print (std::cout);
185          }
186
187          Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
188
189          if (optimum_ && 
190              (optimum_ [i] <= Ub (i)) && 
191              (optimum_ [i] >= uu + COUENNE_EPS)) {
192
193            Jnlst()->Printf(J_STRONGWARNING, J_BOUNDTIGHTENING,
194                            "Couenne: propagating u_%d cuts optimum: [%g <-X- %g <-- %g] :: ", 
195                            i, uu, optimum_ [i], Ub (i));
196            Var (i) -> Lb () -> print (std::cout);
197            Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
198            Var (i) -> Ub () -> print (std::cout);
199            Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
200          }
201        }
202
203        Ub (i) = uu;
204
205        if (uu < Lb (i) - COUENNE_EPS) {
206          Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
207                              "just-check: w_%d has infeasible bounds [%g,%g]. ", i, Lb (i), Ub (i));
208          return -1;
209        }
210
211        chg_bds [i].setUpper(t_chg_bounds::CHANGED);
212        nchg++;
213      }
214
215      // useless if assume expression::[lu]b_ etc already point to
216      // problem::[lu]b_
217    }
218  }
219
220  if (nchg)
221    Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
222                        "  forward tightening %d changes\n", nchg);
223
224  return nchg;
225}
Note: See TracBrowser for help on using the repository browser.