00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include "CglCutGenerator.hpp"
00012 #include "CouenneCutGenerator.hpp"
00013 #include "CouenneProblem.hpp"
00014 #include "CouenneSolverInterface.hpp"
00015
00016 #define OBBT_EPS 1e-3
00017
00018
00019
00020
00021
00023 static bool obbt_updateBound (CouenneSolverInterface *csi,
00024 int sense,
00025 CouNumber &bound,
00026 bool isint) {
00027
00028
00029 csi -> setDblParam (OsiDualObjectiveLimit, COIN_DBL_MAX);
00030 csi -> setDblParam (OsiPrimalObjectiveLimit, (sense==1) ? bound : -bound);
00031 csi -> setObjSense (1);
00032
00034
00035
00036 csi -> resolve ();
00037
00039
00040 if (csi -> isProvenOptimal ()) {
00041
00042 double opt = csi -> getObjValue ();
00043
00044 if (sense > 0)
00045 {if (opt >bound+OBBT_EPS) {bound=(isint ? ceil (opt-COUENNE_EPS) : opt); return true;}}
00046 else {if ((opt=-opt)<bound-OBBT_EPS) {bound=(isint ? floor(opt+COUENNE_EPS) : opt); return true;}}
00047 }
00048
00049 return false;
00050 }
00051
00052
00054
00055 int CouenneProblem::
00056 obbt_iter (CouenneSolverInterface *csi,
00057 t_chg_bounds *chg_bds,
00058 const CoinWarmStart *warmstart,
00059 Bonmin::BabInfo *babInfo,
00060 double *objcoe,
00061 int sense,
00062 int index) const {
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073 std::set <int> deplist;
00074 int deplistsize;
00075
00076 bool issimple = false;
00077
00078 exprVar *var = Var (index);
00079
00080 int
00081 objind = Obj (0) -> Body () -> Index (),
00082 ncols = csi -> getNumCols (),
00083 nImprov = 0;
00084
00085 if ((var -> Type () == AUX) &&
00086 ((deplistsize = var -> Image () -> DepList (deplist, STOP_AT_AUX)) <= 1)) {
00087
00088 if (!deplistsize) {
00089
00090 CouNumber value = (*(var -> Image ())) ();
00091
00092 if (csi -> getColLower () [index] < value - COUENNE_EPS) {
00093 csi -> setColLower (index, value);
00094 chg_bds [index].setLowerBits(t_chg_bounds::CHANGED | t_chg_bounds::EXACT);
00095 }
00096 else chg_bds [index].setLowerBits(t_chg_bounds::EXACT);
00097
00098 if (csi -> getColUpper () [index] > value + COUENNE_EPS) {
00099 csi -> setColUpper (index, value);
00100 chg_bds [index].setUpperBits(t_chg_bounds::CHANGED | t_chg_bounds::EXACT);
00101 }
00102 else chg_bds [index].setUpperBits(t_chg_bounds::EXACT);
00103
00104 issimple = true;
00105
00106 } else {
00107
00108
00109 int indInd = *(deplist.begin ());
00110
00111
00112
00113
00114 if
00115 ((chg_bds [indInd].lower() & t_chg_bounds::EXACT) &&
00116 (chg_bds [indInd].upper() & t_chg_bounds::EXACT) ||
00117
00118
00119 (var -> Image () -> Linearity () <= LINEAR)) {
00120
00121 issimple = true;
00122
00123 CouNumber lb, ub;
00124 var -> Image () -> getBounds (lb, ub);
00125
00126 if (csi -> getColLower () [index] < lb - COUENNE_EPS) {
00127 csi -> setColLower (index, lb);
00128 chg_bds [index].setLowerBits(t_chg_bounds::CHANGED | t_chg_bounds::EXACT);
00129 } else chg_bds [index].setLowerBits(t_chg_bounds::EXACT);
00130
00131 if (csi -> getColUpper () [index] > ub + COUENNE_EPS) {
00132 csi -> setColUpper (index, ub);
00133 chg_bds [index].setUpperBits(t_chg_bounds::CHANGED | t_chg_bounds::EXACT);
00134 } else chg_bds [index].setUpperBits(t_chg_bounds::EXACT);
00135 }
00136 }
00137 }
00138
00139
00140 if (!issimple &&
00141 ((Var (index) -> Type () == VAR) ||
00142 (Var (index) -> Multiplicity () > 0)) &&
00143 (Lb (index) < Ub (index) - COUENNE_EPS) &&
00144
00145 ((index != objind)
00146
00147 || ((sense == 1) && !(chg_bds [index].lower() & t_chg_bounds::EXACT))
00148 )) {
00149
00150
00151 bool isInt = (Var (index) -> isInteger ());
00152
00153 objcoe [index] = sense;
00154
00155 csi -> setObjective (objcoe);
00156 csi -> setObjSense (1);
00157
00158
00159 #if 0
00160 for (int iv=0; iv<csi->getNumCols (); iv++) {
00161 if (fabs (csi -> getColLower () [iv]) > 1e7) csi -> setColLower (iv, -1e14);
00162 if (fabs (csi -> getColUpper () [iv]) > 1e7) csi -> setColUpper (iv, 1e14);
00163 }
00164 #endif
00165
00166 CouNumber &bound =
00167 (sense == 1) ?
00168 (Lb (index)) :
00169 (Ub (index));
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188 csi -> setWarmStart (warmstart);
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214 if (obbt_updateBound (csi, sense, bound, isInt)) {
00215
00216 if (bestSol ()) {
00217 if (sense == 1) {
00218 if ((Lb (index) < bestSol () [index]) &&
00219 (bound > COUENNE_EPS + bestSol () [index]))
00220 Jnlst()->Printf(J_STRONGWARNING, J_BOUNDTIGHTENING,
00221 "#### OBBT error on x%d: lb = %g, opt = %g, new lb = %g\n",
00222 index, Lb (index), bestSol () [index], bound);
00223 } else {
00224 if ((Ub (index) > bestSol () [index]) &&
00225 (bound < -COUENNE_EPS + bestSol () [index]))
00226 Jnlst()->Printf(J_STRONGWARNING, J_BOUNDTIGHTENING,
00227 "#### OBBT error on x%d: ub = %g, opt = %g, new ub = %g\n",
00228 index, Ub (index), bestSol () [index], bound);
00229 }
00230 }
00231
00232
00233
00234 if (sense==1)
00235 if (csi -> getColLower () [index] < bound - COUENNE_EPS) {
00236 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"l_%d: %g --> %g\n",
00237 index, csi -> getColLower () [index], bound);
00238 csi -> setColLower (index, bound);
00239 chg_bds [index].setLowerBits(t_chg_bounds::CHANGED | t_chg_bounds::EXACT);
00240 } else chg_bds [index].setLowerBits(t_chg_bounds::EXACT);
00241 else
00242 if (csi -> getColUpper () [index] > bound + COUENNE_EPS) {
00243 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,"u_%d: %g --> %g\n",
00244 index, csi -> getColUpper () [index], bound);
00245 csi -> setColUpper (index, bound);
00246 chg_bds [index].setUpperBits(t_chg_bounds::CHANGED | t_chg_bounds::EXACT);
00247 } else chg_bds [index].setUpperBits(t_chg_bounds::EXACT);
00248
00249
00250
00251
00252
00253
00254
00255
00256 const double *sol = csi -> getColSolution ();
00257
00258 for (int j=0; j<ncols; j++)
00259 if ((j!=index) && (j!=objind)) {
00260
00261 if (sol [j] <= Lb (j) + COUENNE_EPS) chg_bds [j].setLowerBits(t_chg_bounds::EXACT);
00262 if (sol [j] >= Ub (j) - COUENNE_EPS) chg_bds [j].setUpperBits(t_chg_bounds::EXACT);
00263 }
00264
00265 #if 0
00266
00267
00268 CouNumber *redcost = NULL;
00269
00270
00271
00272
00273
00274 for (int j=0; j<ncols; j++)
00275 if ((j!=index) && (j!=objind)) {
00276
00277
00278
00279
00280
00281
00282
00283 if (!(chg_bds [j].lower & EXACT)) {
00284 }
00285
00286 if (!(chg_bds [j].upper & EXACT)) {
00287 }
00288 }
00289 #endif
00290
00291
00292
00293
00294
00295 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
00296 " OBBT: x_%d: [%g, %g]\n", index,
00297 csi -> getColLower () [index],
00298 csi -> getColUpper () [index]);
00299
00300 if (doFBBT_ && !(boundTightening (chg_bds, babInfo))) {
00301 Jnlst()->Printf(J_DETAILED, J_BOUNDTIGHTENING,
00302 "node is infeasible after post-OBBT tightening\n");
00303 return -1;
00304 }
00305
00306 nImprov++;
00307 }
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320 objcoe [index] = 0;
00321 }
00322
00323 if (nImprov && jnlst_ -> ProduceOutput (J_ITERSUMMARY, J_BOUNDTIGHTENING)) {
00324 Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING, "OBBT: tightened ", nImprov);
00325 if (jnlst_ -> ProduceOutput (J_ITERSUMMARY, J_BOUNDTIGHTENING)) Var (index) -> print ();
00326 Jnlst () -> Printf (J_ITERSUMMARY, J_BOUNDTIGHTENING, "\n");
00327 }
00328
00329 return nImprov;
00330 }