/home/coin/SVN-release/OS-2.0.1/Couenne/src/bound_tightening/tightenBounds.cpp

Go to the documentation of this file.
00001 /* $Id: tightenBounds.cpp 141 2009-06-03 04:19:19Z pbelotti $ */
00002 /*
00003  * Name:    tightenBounds.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: bound tightening for current linear relaxation
00006  *
00007  * (C) Carnegie-Mellon University, 2006-08. 
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include "CglCutGenerator.hpp"
00012 #include "CouenneCutGenerator.hpp"
00013 #include "CouenneProblem.hpp"
00014 
00015 //#define DEBUG
00016 
00018 
00019 int CouenneProblem::tightenBounds (t_chg_bounds *chg_bds) const {
00020 
00021   int nchg = 0; //< number of bounds changed for propagation
00022 
00023   // update bounding box (which may depend on the original
00024   // variables' box) for the variables whose bound is looser. 
00025 
00026   // check all auxiliary variables for changes in their upper,
00027   // lower bound, depending on the bound changes of the variables
00028   // they depend on
00029 
00030   if (Jnlst () -> ProduceOutput (J_DETAILED, J_BOUNDTIGHTENING)) {
00031     // ToDo: Pipe all output through journalist
00032     Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
00033                     "  forward  =====================\n  ");
00034     int j=0;
00035     for (int i=0; i < nVars (); i++) 
00036       if (variables_ [i] -> Multiplicity () >= 0) {
00037         Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING,
00038                         "x_%03d [%+10g %+10g] ", i, 
00039                         domain_. lb (i),
00040                         domain_. ub (i));
00041         if (!(++j % 6)) Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING,"\n  ");
00042     }
00043     if (j % 6) Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING,"\n");
00044   }
00045 
00046   for (int ii = 0, j = nVars (); j--; ii++) {
00047 
00048     int i = numbering_ [ii];
00049 
00050     if (Var (i) -> Multiplicity () <= 0) 
00051       continue;
00052 
00053     CouNumber &lower_i = Lb (i);
00054     CouNumber &upper_i = Ub (i);
00055 
00056     // early test to avoid a loop
00057 
00058     if ((lower_i > upper_i + COUENNE_EPS * (1 + CoinMin (fabs (lower_i), fabs (upper_i)))) || 
00059         (upper_i < - MAX_BOUND) ||
00060         (lower_i >   MAX_BOUND)) {
00061 
00062       if (Jnlst()->ProduceOutput(J_ITERSUMMARY, J_BOUNDTIGHTENING)) {
00063 
00064         Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,
00065                         "pre-check: w_%d has infeasible bounds [%.10e,%.10e]. ", i, lower_i, upper_i);
00066 
00067         if (Jnlst()->ProduceOutput(J_DETAILED, J_BOUNDTIGHTENING)) {
00068           Var (i) -> Lb () -> print (std::cout);
00069           Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
00070           Var (i) -> Ub () -> print (std::cout);
00071         }
00072 
00073         Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,"\n");
00074       }
00075 
00076       return -1; // declare this node infeasible
00077     }
00078 
00079     /*if ((Var (i) -> Type () == VAR) &&
00080         (Var (i) -> isInteger ())) {
00081       lower_i = ceil  (lower_i - COUENNE_EPS);
00082       upper_i = floor (upper_i + COUENNE_EPS);
00083       }*/
00084 
00085     if (Var (i) -> Type () == AUX) {
00086       // TODO: also test if any indep variable of this expression
00087       // have changed. If not, skip
00088 
00089       CouNumber ll, uu; 
00090       //ll = (*(variables_ [i] -> Lb ())) (),
00091       //uu = (*(variables_ [i] -> Ub ())) ();
00092 
00093       variables_ [i] -> Image () -> getBounds (ll, uu);
00094 
00095       if (variables_ [i] -> isInteger ()) {
00096         ll = ceil  (ll - COUENNE_EPS);
00097         uu = floor (uu + COUENNE_EPS);
00098       }
00099 
00100       if (ll - uu > COUENNE_EPS * (1 + CoinMin (fabs (ll), fabs (uu)))) {
00101 
00102         //if (Jnlst()->ProduceOutput(J_ITERSUMMARY, J_BOUNDTIGHTENING)) {
00103 
00104         Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,
00105                         "w_%d has infeasible bounds [%g,%g]: ", i, ll, uu);
00106 
00107         if (Jnlst()->ProduceOutput(J_DETAILED, J_BOUNDTIGHTENING)) {
00108           Var (i) -> Lb () -> print (std::cout);
00109           Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
00110           Var (i) -> Ub () -> print (std::cout);
00111         }
00112 
00113         Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,"\n");
00114           //}
00115 
00116         return -1; // declare this node infeasible
00117       }
00118 
00119       // check if lower bound got higher
00120       if ((ll > - COUENNE_INFINITY) && 
00121           (ll >= lower_i + COUENNE_EPS) &&
00122           ((fabs (ll)        < COUENNE_EPS) || 
00123            (fabs (lower_i) < COUENNE_EPS) ||
00124            (fabs (ll / (lower_i) - 1) > COUENNE_EPS)) ) {
00125 
00126         if (Jnlst()->ProduceOutput(J_DETAILED, J_BOUNDTIGHTENING)) {
00127 
00128           Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
00129                           "  prop L %2d [%g,(%g)] -> [%g,(%g)] (%g) ", 
00130                           i, lower_i, upper_i, ll, uu, lower_i - ll);
00131           Var (i) -> print (std::cout);
00132 
00133           if (Jnlst()->ProduceOutput(J_MOREDETAILED, J_BOUNDTIGHTENING)) {
00134             Jnlst()->Printf(J_MOREDETAILED, J_BOUNDTIGHTENING," := ");
00135             Var (i) -> Image () -> print (std::cout);
00136           }
00137 
00138           Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
00139 
00140           if (optimum_ && 
00141               (optimum_ [i] >= lower_i) && 
00142               (optimum_ [i] <= ll - COUENNE_EPS)) {
00143 
00144             Jnlst()->Printf(J_STRONGWARNING, J_BOUNDTIGHTENING,
00145                             "Couenne: propagating l_%d cuts optimum: [%g --> %g -X-> %g] :: ", 
00146                             i, lower_i, optimum_ [i], ll);
00147             Var (i) -> Lb () -> print (std::cout);
00148             Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
00149             Var (i) -> Ub () -> print (std::cout);
00150             Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
00151           }
00152         }
00153 
00154         lower_i = ll;
00155 
00156         if (ll > upper_i + COUENNE_EPS * (1. + CoinMin (fabs (ll), fabs (upper_i)))) {
00157           Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
00158                               "just-check: w_%d has infeasible bounds [%g,%g]. ", i, lower_i, upper_i);
00159           return -1;
00160         }
00161 
00162         chg_bds [i].setLower(t_chg_bounds::CHANGED);
00163         nchg++;
00164       }
00165 
00166       // check if upper bound got lower
00167       if ((uu < COUENNE_INFINITY) && 
00168           (uu <= upper_i - COUENNE_EPS) &&
00169           ((fabs (uu)      < COUENNE_EPS) || 
00170            (fabs (upper_i) < COUENNE_EPS) ||
00171            (fabs (uu / (upper_i) - 1) > COUENNE_EPS)) ) {
00172         //      if ((uu < COUENNE_INFINITY) && (uu <= ub_ [i+j] - COUENNE_EPS)) {
00173 
00174         /*printf ("update ubound %d: %.10e <= %.10e - %.12e (%.12e)\n", 
00175           i+j, uu, ub_ [i+j], COUENNE_EPS, uu - ub_ [i+j]);*/
00176         /*printf ("update ubound %d: %g >= %g\n", 
00177           i+j, uu, ub_ [i+j]);*/
00178 
00179         if (Jnlst()->ProduceOutput(J_DETAILED, J_BOUNDTIGHTENING)) {
00180 
00181           Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
00182                           "  prop U %2d [(%g),%g] -> [(%g),%g] (%g) ", 
00183                           i, lower_i, upper_i, ll, uu, upper_i - uu);
00184           Var (i) -> print (std::cout);
00185 
00186           if (Jnlst()->ProduceOutput(J_VECTOR, J_BOUNDTIGHTENING)) {
00187             Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING," := ");
00188             Var (i) -> Image () -> print (std::cout);
00189           }
00190 
00191           Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
00192 
00193           if (optimum_ && 
00194               (optimum_ [i] <= upper_i) && 
00195               (optimum_ [i] >= uu + COUENNE_EPS)) {
00196 
00197             Jnlst()->Printf(J_STRONGWARNING, J_BOUNDTIGHTENING,
00198                             "Couenne: propagating u_%d cuts optimum: [%g <-X- %g <-- %g] :: ", 
00199                             i, uu, optimum_ [i], upper_i);
00200             Var (i) -> Lb () -> print (std::cout);
00201             Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
00202             Var (i) -> Ub () -> print (std::cout);
00203             Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
00204           }
00205         }
00206 
00207         upper_i = uu;
00208 
00209         if (uu < lower_i - COUENNE_EPS) {
00210           Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
00211                               "just-check: w_%d has infeasible bounds [%g,%g]. ", i, lower_i, upper_i);
00212           return -1;
00213         }
00214 
00215         chg_bds [i].setUpper(t_chg_bounds::CHANGED);
00216         nchg++;
00217       }
00218 
00219       // useless if assume expression::[lu]b_ etc already point to
00220       // problem::[lu]b_
00221     }
00222   }
00223 
00224   if (nchg)
00225     Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
00226                         "  forward tightening %d changes\n", nchg);
00227 
00228   return nchg;
00229 }

Generated on Thu Oct 8 03:02:55 2009 by  doxygen 1.4.7