00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include <vector>
00012 #include "CoinTime.hpp"
00013
00014 #include "CouenneCutGenerator.hpp"
00015 #include "CouenneDisjCuts.hpp"
00016 #include "CouenneProblem.hpp"
00017 #include "CouenneInfeasCut.hpp"
00018
00019 using namespace Ipopt;
00020 using namespace Couenne;
00021
00023 void CouenneDisjCuts::generateCuts (const OsiSolverInterface &si,
00024 OsiCuts &cs,
00025 const CglTreeInfo info) const {
00026
00027
00028
00029
00030
00031
00032 if (isWiped (cs))
00033 return;
00034
00035 if (jnlst_ -> ProduceOutput (J_DETAILED, J_DISJCUTS))
00036 printf ("--- generateDisjCuts: level = %d, pass = %d, intree = %d [%d]\n",
00037 info.level, info.pass, info.inTree, depthStopSeparate_);
00038
00039 if ((depthStopSeparate_ >= 0) &&
00040 (info.level > depthStopSeparate_))
00041 return;
00042
00043 int nInitCuts = nrootcuts_;
00044
00045 if ((info.level <= 0) && !(info.inTree)) {
00046
00047 jnlst_ -> Printf (J_ERROR, J_COUENNE,
00048 "Disjunctive cuts (root node): ");
00049 fflush (stdout);
00050 }
00051
00052 double time = CoinCpuTime ();
00053
00054
00055 OsiSolverInterface *csi = si.clone ();
00056
00057 int
00058 initRowCuts = cs.sizeRowCuts (),
00059 initColCuts = cs.sizeColCuts ();
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111 int maxDisj = (initDisjNumber_ >= 0) ?
00112 CoinMin ((int) (csi -> numberObjects () * initDisjPercentage_), initDisjNumber_) :
00113 (int) (csi -> numberObjects () * initDisjPercentage_);
00114
00115
00116 numDisjunctions_ = (depthLevelling_ < 0 || info.level < depthLevelling_) ?
00117 (int) (maxDisj) :
00118 (int) (maxDisj / (2 + info.level - depthLevelling_));
00119
00120 if (numDisjunctions_ < 1) numDisjunctions_ = 1;
00121
00122 const int
00123 exc_infeasible = 1,
00124 exc_normal = 2,
00125 max_iterations = 1;
00126
00127 couenneCG_ -> Problem () -> domain () -> push (&si, &cs, false);
00128
00129 std::vector <std::pair <OsiCuts *, OsiCuts *> > disjunctions;
00130
00131 bool infeasNode = false;
00132
00133 try {
00134
00135
00136
00137 bool start_over;
00138 int iterations = 0;
00139
00140 do {
00141
00142
00143 ++iterations;
00144
00145 start_over = false;
00146
00147
00148 int result = getDisjunctions (disjunctions, *csi, cs, info);
00149
00150 if (result == COUENNE_INFEASIBLE) throw exc_infeasible;
00151 else if (result == COUENNE_TIGHTENED &&
00152 iterations < max_iterations) start_over = true;
00153
00154 if (disjunctions.empty ())
00155 throw exc_normal;
00156
00157
00158 for (std::vector <std::pair <OsiCuts *, OsiCuts *> >::iterator disjI = disjunctions.begin ();
00159 disjI != disjunctions.end (); ++disjI) {
00160
00161 if (CoinCpuTime () > couenneCG_ -> Problem () -> getMaxCpuTime ()) {
00162 start_over = false;
00163 break;
00164 }
00165
00166
00167
00168
00169 result = separateWithDisjunction (disjI -> first, *csi, cs, info);
00170 if (result == COUENNE_INFEASIBLE) throw exc_infeasible;
00171 else if (result == COUENNE_TIGHTENED && iterations < max_iterations) {
00172 start_over = true;
00173 break;
00174 }
00175
00176
00177 result = separateWithDisjunction (disjI -> second, *csi, cs, info);
00178 if (result == COUENNE_INFEASIBLE) throw exc_infeasible;
00179 else if (result == COUENNE_TIGHTENED && iterations < max_iterations) {
00180 start_over = true;
00181 break;
00182 }
00183 }
00184
00185 if (start_over) {
00186
00187 for (std::vector <std::pair <OsiCuts *, OsiCuts *> >::iterator disjI = disjunctions.begin ();
00188 disjI != disjunctions.end (); ++disjI) {
00189 delete disjI -> first;
00190 delete disjI -> second;
00191 }
00192
00193 disjunctions.erase (disjunctions.begin (), disjunctions.end ());
00194 }
00195
00196 if (!start_over && jnlst_ -> ProduceOutput (J_VECTOR, J_DISJCUTS))
00197
00198
00199 for (std::vector <std::pair <OsiCuts *, OsiCuts *> >::iterator disjI = disjunctions.begin ();
00200 disjI != disjunctions.end (); ++disjI) {
00201
00202 printf ("=========================== CUTS for the LEFT part\n");
00203 for (int i=0; i<disjI->first->sizeColCuts (); i++) disjI->first->colCutPtr(i)->print();
00204 for (int i=0; i<disjI->first->sizeRowCuts (); i++) disjI->first->rowCutPtr(i)->print();
00205 printf ("=========================== CUTS for the RIGHT part\n");
00206 for (int i=0; i<disjI->second->sizeColCuts (); i++) disjI->second->colCutPtr(i)->print();
00207 for (int i=0; i<disjI->second->sizeRowCuts (); i++) disjI->second->rowCutPtr(i)->print();
00208 printf ("===========================\n");
00209 }
00210
00211 } while (start_over && (iterations < max_iterations));
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223 if (generateDisjCuts (disjunctions, *csi, cs, info) == COUENNE_INFEASIBLE)
00224 throw exc_infeasible;
00225 }
00226
00227 catch (int exception) {
00228
00229 if (exception == exc_infeasible) {
00230
00231 jnlst_ -> Printf (J_DETAILED, J_DISJCUTS, "--- Disjunctive Cut separator: infeasible node\n");
00232 WipeMakeInfeas (cs);
00233 infeasNode = true;
00234 }
00235 }
00236
00237
00238 for (std::vector <std::pair <OsiCuts *, OsiCuts *> >::iterator disjI = disjunctions.begin ();
00239 disjI != disjunctions.end (); ++disjI) {
00240
00241 delete disjI -> first;
00242 delete disjI -> second;
00243 }
00244
00245 couenneCG_ -> Problem () -> domain () -> pop ();
00246
00247 if (!infeasNode) {
00248
00249
00250
00251 CoinPackedVector
00252 tighterLower,
00253 tighterUpper;
00254
00255 const double
00256 *oldLo = si. getColLower (), *newLo = csi -> getColLower (),
00257 *oldUp = si. getColUpper (), *newUp = csi -> getColUpper ();
00258
00259 int ncols = si.getNumCols ();
00260
00261 bool tightened = false;
00262
00263 for (int i=0; i<ncols; i++, newLo++, newUp++) {
00264
00265 if (*newLo > *oldLo++ + COUENNE_EPS) {tighterLower.insert (i, *newLo); tightened = true;}
00266 if (*newUp < *oldUp++ - COUENNE_EPS) {tighterUpper.insert (i, *newUp); tightened = true;}
00267 }
00268
00269 if (tightened) {
00270 OsiColCut tighter;
00271 tighter.setLbs (tighterLower);
00272 tighter.setUbs (tighterUpper);
00273 if (jnlst_ -> ProduceOutput (J_DETAILED, J_DISJCUTS)) {
00274 printf ("tightened bounds in disjunctive cuts:");
00275 tighter.print ();
00276 }
00277 cs.insert (tighter);
00278 }
00279
00280 int deltaNcuts =
00281 cs.sizeRowCuts () - initRowCuts +
00282 cs.sizeColCuts () - initColCuts;
00283
00284 if (info.level <= 0 && !(info.inTree))
00285 nrootcuts_ += deltaNcuts;
00286 ntotalcuts_ += deltaNcuts;
00287
00288 if (jnlst_ -> ProduceOutput (J_DETAILED, J_DISJCUTS)) {
00289
00290 if (cs.sizeRowCuts()>initRowCuts) printf ("added %d row cuts\n", cs.sizeRowCuts () - initRowCuts);
00291 if (cs.sizeColCuts()>initColCuts) printf ("added %d col cuts\n", cs.sizeColCuts () - initColCuts);
00292 }
00293
00294 if ((info.level <= 0) && !(info.inTree))
00295 jnlst_ -> Printf (J_ERROR, J_COUENNE,
00296 "%d cuts\n", CoinMax (0, nrootcuts_ - nInitCuts));
00297 else if (deltaNcuts)
00298 jnlst_ -> Printf (J_WARNING, J_COUENNE,
00299 "In-BB disjunctive cuts: %d row cuts, %d col cuts\n",
00300 cs.sizeRowCuts () - initRowCuts,
00301 cs.sizeColCuts () - initColCuts);
00302 }
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314 delete csi;
00315
00316 septime_ += (CoinCpuTime () - time);
00317 }