/home/coin/SVN-release/OS-2.4.2/Couenne/src/disjunctive/singleDisjunctions.cpp

Go to the documentation of this file.
00001 /* $Id: singleDisjunctions.cpp 490 2011-01-14 16:07:12Z pbelotti $ */
00002 /*
00003  * Name:    singleDisjunctions.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: simpler methods on single disjunctions
00006  *
00007  * (C) Carnegie-Mellon University, 2008. 
00008  * This file is licensed under the Eclipse Public License (EPL)
00009  */
00010 
00011 #include "CouenneCutGenerator.hpp"
00012 #include "CouenneProblem.hpp"
00013 #include "CouenneDisjCuts.hpp"
00014 
00015 using namespace Couenne;
00016 
00018 OsiCuts *CouenneDisjCuts::getSingleDisjunction (OsiSolverInterface &si) const { 
00019 
00020   int 
00021     ncols = si.getNumCols (), nNL = 0, nNU = 0,
00022     *indNL = new int [ncols],      
00023     *indNU = new int [ncols];
00024 
00025   double 
00026     *oldL  = couenneCG_ -> Problem () -> Lb (),   *valNL = new double [ncols],
00027     *oldU  = couenneCG_ -> Problem () -> Ub (),   *valNU = new double [ncols];
00028 
00029   const double
00030     *newL = si.getColLower (),   
00031     *newU = si.getColUpper ();
00032 
00033   for (int i=0; i<ncols; i++) {
00034     if (newL [i] > oldL [i] + COUENNE_EPS) {indNL [nNL] = i; valNL [nNL++] = newL [i];}
00035     if (newU [i] < oldU [i] - COUENNE_EPS) {indNU [nNU] = i; valNU [nNU++] = newU [i];}
00036   }           
00037 
00038   OsiColCut cut;
00039 
00040   cut. setLbs (nNL, indNL, valNL);
00041   cut. setUbs (nNU, indNU, valNU);
00042 
00043   OsiCuts *cuts = new OsiCuts;
00044 
00045   cuts -> insert (cut);
00046 
00047   delete [] indNL;   delete [] valNL;
00048   delete [] indNU;   delete [] valNU;
00049 
00050   return cuts;
00051 }
00052 
00053 
00055 int CouenneDisjCuts::checkDisjSide (OsiSolverInterface &si, OsiCuts *cuts) const {
00056 
00057   int retval = COUENNE_FEASIBLE;
00058 
00059   const double 
00060     *lower = si.getColLower (),
00061     *upper = si.getColUpper ();
00062 
00063   // check each colcut in cuts (there should be just one)
00064 
00065   for (int i = cuts -> sizeColCuts (); i--;) {
00066 
00067     // lower bounds
00068 
00069     const CoinPackedVector &lbs = cuts -> colCutPtr (i) -> lbs ();
00070     const int    *lindices = lbs.getIndices ();
00071     const double *lvalues  = lbs.getElements ();
00072 
00073     for (int j = lbs.getNumElements (); j--;) {
00074       register double lb  = *lvalues++;
00075       register int    ind = *lindices++;
00076 
00077       if (lb > upper [ind] + COUENNE_EPS) // fathom node
00078         return COUENNE_INFEASIBLE;
00079 
00080       if (lb > lower [ind] + COUENNE_EPS) 
00081         retval = COUENNE_TIGHTENED;
00082     }
00083 
00084     // upper bounds
00085 
00086     const CoinPackedVector &ubs = cuts -> colCutPtr (i) -> ubs ();
00087     const int    *uindices = ubs.getIndices ();
00088     const double *uvalues  = ubs.getElements ();
00089 
00090     for (int j = ubs.getNumElements (); j--;) {
00091       register double ub  = *uvalues++;
00092       register int    ind = *uindices++;
00093 
00094       if (ub < lower [ind] - COUENNE_EPS) // fathom node
00095         return COUENNE_INFEASIBLE;
00096 
00097       if (ub < upper [ind] - COUENNE_EPS) 
00098         retval = COUENNE_TIGHTENED;
00099     }
00100   }
00101 
00102   return retval;
00103 }
00104 
00105 
00107 int CouenneDisjCuts::getBoxUnion (OsiSolverInterface &si,
00108                                   OsiCuts *left, OsiCuts *right, 
00109                                   CoinPackedVector &lower, CoinPackedVector &upper) const {
00110 
00111   int retval = COUENNE_FEASIBLE;
00112 
00113   CoinPackedVector 
00114     lowerLeft,  upperLeft,
00115     lowerRight, upperRight;
00116 
00117   // merge all left lowers and uppers
00118   for (int i = left -> sizeColCuts (); i--;) {
00119     lowerLeft. append (left -> colCutPtr (i) -> lbs ());
00120     upperLeft. append (left -> colCutPtr (i) -> ubs ());
00121   }
00122 
00123   // merge all right lowers and uppers
00124   for (int i = right -> sizeColCuts (); i--;) {
00125     lowerRight. append (right -> colCutPtr (i) -> lbs ());
00126     upperRight. append (right -> colCutPtr (i) -> ubs ());
00127   }
00128 
00129   // sort all indexed vectors
00130   lowerLeft.  sortIncrIndex ();  upperLeft.  sortIncrIndex ();
00131   lowerRight. sortIncrIndex ();  upperRight. sortIncrIndex ();
00132 
00133   // now compare bounds one by one -- complexity linear in size of vectors
00134 
00135   mergeBoxes (-1, lowerLeft, lowerRight, lower);
00136   mergeBoxes (+1, upperLeft, upperRight, upper);
00137 
00138   return retval;
00139 }
00140 
00141 
00143 void CouenneDisjCuts::mergeBoxes (int dir, // direction (negative for "<", positive for ">")
00144                                   CoinPackedVector &left, 
00145                                   CoinPackedVector &right, 
00146                                   CoinPackedVector merged) const { 
00147   int
00148     Ln = left.  getNumElements (),
00149     Rn = right. getNumElements ();
00150 
00151   if (!Ln || !Rn) 
00152     return;
00153 
00154   const int 
00155     *Li = left.  getIndices (),
00156     *Ri = right. getIndices ();
00157 
00158   const double
00159     *Le = left.  getElements (),
00160     *Re = right. getElements ();
00161 
00162   for (;;) {
00163 
00164     for (;;) {
00165 
00166       register int diff = *Li - *Ri;
00167 
00168       if      (diff < 0) {if (!--Ln) break; Li++; Le++;}
00169       else if (diff > 0) {if (!--Rn) break; Ri++; Re++;}
00170       else break;
00171     }
00172 
00173     if (!Ln || !Rn) break;                                  // !Ln, !Rn (==> exit), or Li==*Ri: 
00174     if (dir < 0) merged. insert (*Li, *Le<*Re ? *Le : *Re); // add min(*Le, *Re)) 
00175     else         merged. insert (*Li, *Le>*Re ? *Le : *Re); // add max(*Le, *Re)) 
00176 
00177     Li++; Ri++;
00178     Le++; Re++;
00179 
00180     if (!--Ln || !--Rn) break;
00181   }
00182 }

Generated on Wed Nov 30 03:04:01 2011 by  doxygen 1.4.7