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

Go to the documentation of this file.
00001 /* $Id: generateDisjCuts.cpp 215 2009-07-08 15:43:38Z pbelotti $
00002  *
00003  * Name:    generateDisjCuts.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: separation method for disjunctive cuts
00006  *
00007  * (C) Carnegie-Mellon University, 2008-09.
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include <vector>
00012 #include "CoinTime.hpp"
00013 
00014 #include "CouenneDisjCuts.hpp"
00015 #include "CouenneProblem.hpp"
00016 #include "CouenneCutGenerator.hpp"
00017 
00019 void CouenneDisjCuts::generateCuts (const OsiSolverInterface &si, 
00020                                     OsiCuts &cs, 
00021                                     const CglTreeInfo info) const {
00022 
00023   if (jnlst_ -> ProduceOutput (J_DETAILED, J_DISJCUTS)) 
00024     printf ("--- generateDisjCuts: level = %d, pass = %d, intree = %d [%d]\n",
00025             info.level, info.pass, info.inTree, depthStopSeparate_);
00026 
00027   if ((depthStopSeparate_ >= 0) &&        // if -1 no limit on depth
00028       (info.level > depthStopSeparate_))  // check if too deep for adding these cuts
00029     return;
00030 
00031   double time = CoinCpuTime ();
00032 
00033   // use clone solver interface
00034   OsiSolverInterface *csi = si.clone ();
00035 
00036   int
00037     initRowCuts = cs.sizeRowCuts (),
00038     initColCuts = cs.sizeColCuts ();
00039 
00040   // get disjunctions /////////////////////////////
00041   //
00042   // start:
00043   //
00044   // consider problem Ax <= a_0, x in [l,u]
00045   //
00046   // // A and a_0 may be, depending on depth of BB tree and size of the
00047   // // problem, from the linearization at the root node (in this case
00048   // // a clone() is needed at the first iteration and branching rules
00049   // // should be applied explicitly) or the current LP as passed by
00050   // // si.
00051   //
00052   // Get set of disjunctions (in the form of OsiBranchingObjects) in
00053   // number limited by depth, problem size, and sorted according to
00054   // branching method (HotInfo if strong branching?)
00055   //
00056   // preprocessing /////////////////////////////////
00057   //
00058   // for each disjunction (x_i <= or >= x_i^d) {
00059   //
00060   //   1) apply left  disj., bound tightening returns x in [l_1,u_1]
00061   //   2) apply right disj., bound tightening returns x in [l_2,u_2]
00062   //
00063   //   3) if both infeasible, bail out
00064   //   4) if one infeasible only, save column cut, apply tightening to
00065   //      si and goto start
00066   // }
00067   //
00068   // CGLP //////////////////////////////////////////
00069   //
00070   // for each disjunction (x_i <= or >= x_i^d) {
00071   //
00072   //   5) get cuts Bx <= b_0 for left  disj.
00073   //   6) get cuts Cx <= c_0 for right disj.
00074   //
00075   //   7) if both infeasible, bail out
00076   //   8) if one infeasible only, save column cut, apply tightening to
00077   //      si and continue
00078   //
00079   //   9) generate CGLP:
00080   //         consider subset of Ax <= a_0: 
00081   //           a) active only, or
00082   //           b) {root linearization cuts} union {currently active}, or
00083   //           c) all cuts (!)
00084   //
00085   //   10) solve CGLP
00086   //
00087   //   11) add corresponding cut, possibly to CGLP as well?
00088   // }
00089 
00090   int maxDisj = (initDisjNumber_ >= 0) ? 
00091     CoinMin ((int) (csi -> numberObjects () * initDisjPercentage_), initDisjNumber_) :
00092     (int) (csi -> numberObjects () * initDisjPercentage_);
00093 
00094   // number of disjunctions to consider (branching objects)
00095   numDisjunctions_ = (depthLevelling_ < 0 || info.level < depthLevelling_) ? 
00096     (int) (maxDisj) :
00097     (int) (maxDisj / (2 + info.level - depthLevelling_));
00098 
00099   if (numDisjunctions_ < 1) numDisjunctions_ = 1;
00100 
00101   const int 
00102     exc_infeasible = 1, 
00103     exc_normal     = 2, 
00104     max_iterations = 1;
00105 
00106   couenneCG_ -> Problem () -> domain () -> push (couenneCG_ -> Problem () -> nVars  (),
00107                                                  si. getColSolution (),
00108                                                  si. getColLower    (),
00109                                                  si. getColUpper    ());
00110 
00111   std::vector <std::pair <OsiCuts *, OsiCuts *> > disjunctions;
00112 
00113   try {
00114 
00115     // get disjunctions (rows and cols) ////////////////////////////////////////////////////
00116 
00117     bool start_over;
00118     int iterations = 0;
00119 
00120     do { // repeat as long as preprocessing or separation of convCuts
00121          // shrink the whole problem
00122 
00123       ++iterations;
00124 
00125       start_over = false;
00126 
00127       // preprocess, get column cuts (disjoint bounding boxes)
00128       int result = getDisjunctions (disjunctions, *csi, cs, info);
00129 
00130       if      (result == COUENNE_INFEASIBLE) throw exc_infeasible; // fathom node
00131       else if (result == COUENNE_TIGHTENED && 
00132                iterations < max_iterations) start_over = true;     // tightened node
00133 
00134       if (disjunctions.empty ())
00135         throw exc_normal;
00136 
00137       // generate convexification cuts for each disjunction
00138       for (std::vector <std::pair <OsiCuts *, OsiCuts *> >::iterator disjI = disjunctions.begin ();
00139            disjI != disjunctions.end (); ++disjI) {
00140 
00141         // separate on single disjunction
00142 
00143         // left
00144         result = separateWithDisjunction (disjI -> first, *csi, cs, info);
00145         if      (result == COUENNE_INFEASIBLE) throw exc_infeasible;           // fathom node
00146         else if (result == COUENNE_TIGHTENED && iterations < max_iterations) { // tightened node
00147           start_over = true;
00148           break;
00149         }
00150 
00151         // right
00152         result = separateWithDisjunction (disjI -> second, *csi, cs, info);
00153         if      (result == COUENNE_INFEASIBLE) throw exc_infeasible;           // fathom node
00154         else if (result == COUENNE_TIGHTENED && iterations < max_iterations) { // tightened node
00155           start_over = true;
00156           break;
00157         }
00158       }
00159 
00160       if (start_over) {
00161 
00162         for (std::vector <std::pair <OsiCuts *, OsiCuts *> >::iterator disjI = disjunctions.begin ();
00163              disjI != disjunctions.end (); ++disjI) {
00164           delete disjI -> first;
00165           delete disjI -> second;
00166         }
00167 
00168         disjunctions.erase (disjunctions.begin (), disjunctions.end ());
00169       }
00170 
00171       if (!start_over && jnlst_ -> ProduceOutput (J_VECTOR, J_DISJCUTS))
00172 
00173         // generate convexification cuts for each disjunction
00174         for (std::vector <std::pair <OsiCuts *, OsiCuts *> >::iterator disjI = disjunctions.begin ();
00175              disjI != disjunctions.end (); ++disjI) {
00176 
00177           printf ("=========================== CUTS for the LEFT part\n");
00178           for (int i=0; i<disjI->first->sizeColCuts (); i++) disjI->first->colCutPtr(i)->print();
00179           for (int i=0; i<disjI->first->sizeRowCuts (); i++) disjI->first->rowCutPtr(i)->print();
00180           printf ("=========================== CUTS for the RIGHT part\n");
00181           for (int i=0; i<disjI->second->sizeColCuts (); i++) disjI->second->colCutPtr(i)->print();
00182           for (int i=0; i<disjI->second->sizeRowCuts (); i++) disjI->second->rowCutPtr(i)->print();
00183           printf ("===========================\n");
00184         }
00185 
00186     } while (start_over && (iterations < max_iterations));
00187 
00188     // si contains the tightest bounding box. Use it to update
00189     // CouenneProblem's bounds AND add to cs
00190 
00191     // already done above
00192 
00193     // CGLP //////////////////////////////////////////////////////////////////////////
00194 
00195     // maybe one last FBBT before big CGLP?
00196 
00197     // generate all cuts
00198     if (generateDisjCuts (disjunctions, *csi, cs, info) == COUENNE_INFEASIBLE) // node can be fathomed
00199       throw exc_infeasible;
00200   }
00201 
00202   catch (int exception) {
00203 
00204     if (exception == exc_infeasible) { // add infeasible column cut 1 <= x_0 <= -1
00205 
00206       if (jnlst_ -> ProduceOutput (J_DETAILED, J_DISJCUTS))
00207         printf ("---   infeasible node!\n");
00208 
00209       OsiColCut infeascut;
00210       int ind = 0;
00211       double upper = -1., lower = +1.;
00212 
00213       infeascut. setLbs (1, &ind, &lower);
00214       infeascut. setUbs (1, &ind, &upper);
00215 
00216       cs.insert (infeascut);
00217     }
00218   }
00219 
00220   // cleanup
00221   for (std::vector <std::pair <OsiCuts *, OsiCuts *> >::iterator disjI = disjunctions.begin ();
00222        disjI != disjunctions.end (); ++disjI) {
00223 
00224     delete disjI -> first;
00225     delete disjI -> second;
00226   }
00227 
00228   couenneCG_ -> Problem () -> domain () -> pop ();
00229 
00230   // tighten bounds of si based on those tightened of csi
00231 
00232   CoinPackedVector 
00233     tighterLower, 
00234     tighterUpper;
00235 
00236   const double 
00237     *oldLo = si. getColLower (),   *newLo = csi -> getColLower (), 
00238     *oldUp = si. getColUpper (),   *newUp = csi -> getColUpper ();
00239 
00240   int ncols = si.getNumCols ();
00241 
00242   bool tightened = false;
00243 
00244   for (int i=0; i<ncols; i++, newLo++, newUp++) {
00245 
00246     if (*newLo > *oldLo++ + COUENNE_EPS) {tighterLower.insert (i, *newLo); tightened = true;}
00247     if (*newUp < *oldUp++ - COUENNE_EPS) {tighterUpper.insert (i, *newUp); tightened = true;}
00248   }
00249 
00250   if (tightened) {
00251     OsiColCut tighter;
00252     tighter.setLbs (tighterLower);
00253     tighter.setUbs (tighterUpper);
00254     if (jnlst_ -> ProduceOutput (J_DETAILED, J_DISJCUTS)) {
00255       printf ("tightened bounds in disjunctive cuts:");
00256       tighter.print ();
00257     }
00258     cs.insert (tighter);
00259   }
00260 
00261   delete csi;
00262 
00263   int deltaNcuts = 
00264     cs.sizeRowCuts () - initRowCuts + 
00265     cs.sizeColCuts () - initColCuts;
00266 
00267   if (info.level <= 0) 
00268     nrootcuts_ = deltaNcuts;
00269   ntotalcuts_ += deltaNcuts;
00270 
00271   if (jnlst_ -> ProduceOutput (J_DETAILED, J_DISJCUTS)) {
00272 
00273     if (cs.sizeRowCuts()>initRowCuts) printf ("added %d row cuts\n", cs.sizeRowCuts () - initRowCuts);
00274     if (cs.sizeColCuts()>initColCuts) printf ("added %d col cuts\n", cs.sizeColCuts () - initColCuts);
00275   }
00276 
00277   septime_ += (CoinCpuTime () - time);
00278 }

Generated on Mon May 3 03:05:19 2010 by  doxygen 1.4.7