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