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

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

Generated on Mon Aug 3 03:02:20 2009 by  doxygen 1.4.7