00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include "CglCutGenerator.hpp"
00012 #include "CouenneCutGenerator.hpp"
00013 #include "CouenneProblem.hpp"
00014 #include "CouenneExprVar.hpp"
00015
00016 using namespace Ipopt;
00017 using namespace Couenne;
00018
00020
00021 int CouenneProblem::tightenBounds (t_chg_bounds *chg_bds) const {
00022
00023 int nchg = 0;
00024
00025
00026
00027
00028
00029
00030
00031
00032 CouNumber *knownOptimum = optimum_;
00033
00034 if (optimum_) {
00035
00036 for (int i=nVars(); i--; knownOptimum++)
00037
00038 if (*knownOptimum < Lb (i) ||
00039 *knownOptimum > Ub (i)) {
00040
00041 knownOptimum = NULL;
00042 break;
00043 }
00044
00045 if (knownOptimum)
00046 knownOptimum -= nVars ();
00047 }
00048
00049 bool dbgOutput = Jnlst () -> ProduceOutput (J_DETAILED, J_BOUNDTIGHTENING);
00050
00051 if (dbgOutput) {
00052
00053 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING, " forward =====================\n ");
00054 int j=0;
00055 for (int i=0; i < nVars (); i++)
00056 if (variables_ [i] -> Multiplicity () > 0) {
00057 Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING,
00058 "x_%03d [%+10g %+10g] ", i,
00059 domain_. lb (i),
00060 domain_. ub (i));
00061 if (!(++j % 6)) Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING,"\n ");
00062 }
00063 if (j % 6) Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING,"\n");
00064 }
00065
00066 for (int ii = 0, j = nVars (); j--; ii++) {
00067
00068 int i = numbering_ [ii];
00069
00070 exprVar *var = Var (i);
00071
00072 if (var -> Multiplicity () <= 0)
00073 continue;
00074
00075 CouNumber &lower_i = Lb (i);
00076 CouNumber &upper_i = Ub (i);
00077
00078
00079
00080 if ((fabs (upper_i) < COIN_DBL_MAX / 10) &&
00081 (fabs (lower_i) < COIN_DBL_MAX / 10) &&
00082 (lower_i > upper_i + COUENNE_BOUND_PREC * (1 + CoinMin (fabs (lower_i), fabs (upper_i))))) {
00083
00084
00085
00086 if (Jnlst()->ProduceOutput(J_ITERSUMMARY, J_BOUNDTIGHTENING)) {
00087
00088 Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,
00089 "pre-check: w_%d has infeasible bounds [%.10e,%.10e]. ", i, lower_i, upper_i);
00090
00091 if (dbgOutput) {
00092
00093 var -> Lb () -> print (std::cout);
00094 Jnlst () -> Printf (J_DETAILED, J_BOUNDTIGHTENING," --- ");
00095 var -> Ub () -> print (std::cout);
00096 }
00097
00098 Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,"\n");
00099 }
00100
00101 return -1;
00102 }
00103
00104
00105
00106
00107
00108
00109
00110 if (var -> Type () != AUX)
00111 continue;
00112
00113
00114
00115
00116 CouNumber ll, uu;
00117
00118
00119
00120 var -> Image () -> getBounds (ll, uu);
00121
00122 if (var -> isInteger ()) {
00123 if (var -> sign () != expression::AUX_LEQ) ll = ceil (ll - COUENNE_EPS);
00124 if (var -> sign () != expression::AUX_GEQ) uu = floor (uu + COUENNE_EPS);
00125 }
00126
00127 if (var -> sign () == expression::AUX_LEQ) ll = (*(var -> Lb ())) ();
00128 else if (var -> sign () == expression::AUX_GEQ) uu = (*(var -> Ub ())) ();
00129
00130 if (ll - uu > COUENNE_BOUND_PREC * (1 + CoinMin (fabs (ll), fabs (uu)))) {
00131
00132
00133
00134 Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,
00135 "w_%d has infeasible bounds [%g,%g]: ", i, ll, uu);
00136
00137 if (dbgOutput) {
00138 var -> Lb () -> print (std::cout);
00139 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
00140 var -> Ub () -> print (std::cout);
00141 }
00142
00143 Jnlst()->Printf(J_ITERSUMMARY, J_BOUNDTIGHTENING,"\n");
00144
00145
00146 return -1;
00147 }
00148
00149
00150
00151
00152
00153
00154 if (var -> sign () == expression::AUX_LEQ) ll = -COUENNE_INFINITY;
00155 if (var -> sign () == expression::AUX_GEQ) uu = COUENNE_INFINITY;
00156
00157
00158 if ((ll > - COUENNE_INFINITY) &&
00159 (ll >= lower_i + COUENNE_EPS) &&
00160 ((fabs (ll) < COUENNE_EPS) ||
00161 (fabs (lower_i) < COUENNE_EPS) ||
00162 (fabs (ll / (lower_i) - 1) > COUENNE_EPS)) ) {
00163
00164 if (dbgOutput) {
00165
00166 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
00167 " prop L %2d [%g,(%g)] -> [%g,(%g)] (%g) ",
00168 i, lower_i, upper_i, ll, uu, lower_i - ll);
00169 var -> print (std::cout);
00170
00171 if (Jnlst()->ProduceOutput(J_MOREDETAILED, J_BOUNDTIGHTENING)) {
00172 Jnlst()->Printf(J_MOREDETAILED, J_BOUNDTIGHTENING," := ");
00173 var -> Image () -> print (std::cout);
00174 }
00175
00176 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
00177
00178 if (knownOptimum &&
00179 (knownOptimum [i] >= lower_i) &&
00180 (knownOptimum [i] <= ll - COUENNE_EPS)) {
00181
00182 Jnlst()->Printf(J_STRONGWARNING, J_BOUNDTIGHTENING,
00183 "Couenne: propagating l_%d cuts optimum: [%g --> %g -X-> %g] :: ",
00184 i, lower_i, knownOptimum [i], ll);
00185 var -> Lb () -> print (std::cout);
00186 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
00187 var -> Ub () -> print (std::cout);
00188 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
00189 }
00190 }
00191
00192 lower_i = ll;
00193
00194 if (ll > upper_i + COUENNE_BOUND_PREC * (1. + CoinMin (fabs (ll), fabs (upper_i)))) {
00195 Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
00196 "just-check: w_%d has infeasible bounds [%g,%g]. ", i, lower_i, upper_i);
00197 return -1;
00198 }
00199
00200 chg_bds [i].setLower (t_chg_bounds::CHANGED);
00201 nchg++;
00202 }
00203
00204
00205 if ((uu < COUENNE_INFINITY) &&
00206 (uu <= upper_i - COUENNE_EPS) &&
00207 ((fabs (uu) < COUENNE_EPS) ||
00208 (fabs (upper_i) < COUENNE_EPS) ||
00209 (fabs (uu / (upper_i) - 1) > COUENNE_EPS)) ) {
00210
00211
00212
00213
00214
00215
00216
00217 if (dbgOutput) {
00218
00219 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
00220 " prop U %2d [(%g),%g] -> [(%g),%g] (%g) ",
00221 i, lower_i, upper_i, ll, uu, upper_i - uu);
00222 var -> print (std::cout);
00223
00224 if (Jnlst()->ProduceOutput(J_VECTOR, J_BOUNDTIGHTENING)) {
00225 Jnlst()->Printf(J_VECTOR, J_BOUNDTIGHTENING," := ");
00226 var -> Image () -> print (std::cout);
00227 }
00228
00229 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
00230
00231 if (knownOptimum &&
00232 (knownOptimum [i] <= upper_i) &&
00233 (knownOptimum [i] >= uu + COUENNE_EPS)) {
00234
00235 Jnlst()->Printf(J_STRONGWARNING, J_BOUNDTIGHTENING,
00236 "Couenne: propagating u_%d cuts optimum: [%g <-X- %g <-- %g] :: ",
00237 i, uu, knownOptimum [i], upper_i);
00238 var -> Lb () -> print (std::cout);
00239 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING," --- ");
00240 var -> Ub () -> print (std::cout);
00241 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"\n");
00242 }
00243 }
00244
00245 upper_i = uu;
00246
00247 if (uu < lower_i - COUENNE_BOUND_PREC) {
00248 Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
00249 "just-check: w_%d has infeasible bounds [%g,%g]. ", i, lower_i, upper_i);
00250 return -1;
00251 }
00252
00253 chg_bds [i].setUpper(t_chg_bounds::CHANGED);
00254 nchg++;
00255 }
00256
00257
00258
00259 }
00260
00261 if (nchg)
00262 Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING,
00263 " forward tightening %d changes\n", nchg);
00264
00265 return nchg;
00266 }