/home/coin/SVN-release/OS-2.4.0/Couenne/src/disjunctive/generateDisjCuts.cpp

Go to the documentation of this file.
00001 /* $Id: generateDisjCuts.cpp 694 2011-06-18 20:13:17Z stefan $
00002  *
00003  * Name:    generateDisjCuts.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: separation method for disjunctive cuts
00006  *
00007  * (C) Carnegie-Mellon University, 2008-10.
00008  * This file is licensed under the Eclipse Public License (EPL)
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   // Check if cs contains only one cut and if it is of the form 1 <=
00028   // x0 <= -1. That means a previous cut generator has determined that
00029   // this node is infeasible and we shouldn't take the pain of running
00030   // this CGL.
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) &&        // if -1 no limit on depth
00040       (info.level > depthStopSeparate_))  // check if too deep for adding these cuts
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   // use clone of solver interface
00055   OsiSolverInterface *csi = si.clone ();
00056 
00057   int
00058     initRowCuts = cs.sizeRowCuts (),
00059     initColCuts = cs.sizeColCuts ();
00060 
00061   // get disjunctions /////////////////////////////
00062   //
00063   // start:
00064   //
00065   // consider problem Ax <= a_0, x in [l,u]
00066   //
00067   // // A and a_0 may be, depending on depth of BB tree and size of the
00068   // // problem, from the linearization at the root node (in this case
00069   // // a clone() is needed at the first iteration and branching rules
00070   // // should be applied explicitly) or the current LP as passed by
00071   // // si.
00072   //
00073   // Get set of disjunctions (in the form of OsiBranchingObjects) in
00074   // number limited by depth, problem size, and sorted according to
00075   // branching method (HotInfo if strong branching?)
00076   //
00077   // preprocessing /////////////////////////////////
00078   //
00079   // for each disjunction (x_i <= or >= x_i^d) {
00080   //
00081   //   1) apply left  disj., bound tightening returns x in [l_1,u_1]
00082   //   2) apply right disj., bound tightening returns x in [l_2,u_2]
00083   //
00084   //   3) if both infeasible, bail out
00085   //   4) if one infeasible only, save column cut, apply tightening to
00086   //      si and goto start
00087   // }
00088   //
00089   // CGLP //////////////////////////////////////////
00090   //
00091   // for each disjunction (x_i <= or >= x_i^d) {
00092   //
00093   //   5) get cuts Bx <= b_0 for left  disj.
00094   //   6) get cuts Cx <= c_0 for right disj.
00095   //
00096   //   7) if both infeasible, bail out
00097   //   8) if one infeasible only, save column cut, apply tightening to
00098   //      si and continue
00099   //
00100   //   9) generate CGLP:
00101   //         consider subset of Ax <= a_0: 
00102   //           a) active only, or
00103   //           b) {root linearization cuts} union {currently active}, or
00104   //           c) all cuts (!)
00105   //
00106   //   10) solve CGLP
00107   //
00108   //   11) add corresponding cut, possibly to CGLP as well?
00109   // }
00110 
00111   int maxDisj = (initDisjNumber_ >= 0) ? 
00112     CoinMin ((int) (csi -> numberObjects () * initDisjPercentage_), initDisjNumber_) :
00113     (int) (csi -> numberObjects () * initDisjPercentage_);
00114 
00115   // number of disjunctions to consider (branching objects)
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     // get disjunctions (rows and cols) ////////////////////////////////////////////////////
00136 
00137     bool start_over;
00138     int iterations = 0;
00139 
00140     do { // repeat as long as preprocessing or separation of convCuts
00141          // shrink the whole problem
00142 
00143       ++iterations;
00144 
00145       start_over = false;
00146 
00147       // preprocess, get column cuts (disjoint bounding boxes)
00148       int result = getDisjunctions (disjunctions, *csi, cs, info);
00149 
00150       if      (result == COUENNE_INFEASIBLE) throw exc_infeasible; // fathom node
00151       else if (result == COUENNE_TIGHTENED && 
00152                iterations < max_iterations) start_over = true;     // tightened node
00153 
00154       if (disjunctions.empty ())
00155         throw exc_normal;
00156 
00157       // generate convexification cuts for each disjunction
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         // separate on single disjunction
00167 
00168         // left
00169         result = separateWithDisjunction (disjI -> first, *csi, cs, info);
00170         if      (result == COUENNE_INFEASIBLE) throw exc_infeasible;           // fathom node
00171         else if (result == COUENNE_TIGHTENED && iterations < max_iterations) { // tightened node
00172           start_over = true;
00173           break;
00174         }
00175 
00176         // right
00177         result = separateWithDisjunction (disjI -> second, *csi, cs, info);
00178         if      (result == COUENNE_INFEASIBLE) throw exc_infeasible;           // fathom node
00179         else if (result == COUENNE_TIGHTENED && iterations < max_iterations) { // tightened node
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         // generate convexification cuts for each disjunction
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     // si contains the tightest bounding box. Use it to update
00214     // CouenneProblem's bounds AND add to cs
00215 
00216     // already done above
00217 
00218     // CGLP //////////////////////////////////////////////////////////////////////////
00219 
00220     // maybe one last FBBT before big CGLP?
00221 
00222     // generate all cuts
00223     if (generateDisjCuts (disjunctions, *csi, cs, info) == COUENNE_INFEASIBLE) // node can be fathomed
00224       throw exc_infeasible;
00225   }
00226 
00227   catch (int exception) {
00228 
00229     if (exception == exc_infeasible) { // add infeasible column cut 1 <= x_0 <= -1
00230 
00231       jnlst_ -> Printf (J_DETAILED, J_DISJCUTS, "--- Disjunctive Cut separator: infeasible node\n");
00232       WipeMakeInfeas (cs);
00233       infeasNode = true;
00234     }
00235   }
00236 
00237   // cleanup
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     // tighten bounds of si based on those tightened of csi
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   // else {
00305   //     jnlst_ -> Printf (J_STRONGWARNING, J_COUENNE, 
00306   //                    "In-BB disjunctive cuts: %d row cuts, %d col cuts\n",
00307   //                    cs.sizeRowCuts () - initRowCuts,
00308   //                    cs.sizeColCuts () - initColCuts);
00309   //   if ((info.level <= 0) && !(info.inTree))
00310   //     jnlst_ -> Printf (J_ERROR, J_COUENNE, 
00311   //                    "infeasible node\n");
00312   // }
00313 
00314   delete csi;
00315 
00316   septime_ += (CoinCpuTime () - time);
00317 }

Generated on Thu Sep 22 03:05:57 2011 by  doxygen 1.4.7