- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/Cgl-0.52.0/Cgl/src/CglLandP/CglLandPSimplex.hpp

Go to the documentation of this file.

    00001 // Copyright (C) 2005, Pierre Bonami and others.  All Rights Reserved.
    00002 // Author:   Pierre Bonami
    00003 //           Tepper School of Business
    00004 //           Carnegie Mellon University, Pittsburgh, PA 15213
    00005 // Date:     21/07/05
    00006 //---------------------------------------------------------------------------
    00007 #ifndef CglLandPSimplex_H
    00008 #define CglLandPSimplex_H
    00009
    00010 #include <iostream>
    00011
    00012 #include "CglLandP.hpp"
    00013
    00014 #include "OsiSolverInterface.hpp"
    00015 #include "CoinMessage.hpp"
    00016 #include "CoinMessageHandler.hpp"
    00017 #include "CoinWarmStartBasis.hpp"
    00018 #include "CoinPackedMatrix.hpp"
    00019 namespace LAP {
    00021 enum LAPS_messages
    00022 {
    00023   Separating,
    00024   FoundImprovingRow,
    00025   FoundBestImprovingCol,
    00026   WarnFailedBestImprovingCol,
    00027   LogHead,
    00028   PivotLog,
    00029   FinishedOptimal,
    00030   HitLimit,
    00031   WarnBadSigmaComputation,
    00032   WarnBadRowComputation,
    00033   WarnGiveUpRow,
    00034   PivotFailedSigmaUnchanged,
    00035   PivotFailedSigmaIncreased,
    00036   FailedSigmaIncreased,
    00037   WarnBadRhsComputation,
    00038   WarnFailedPivotTol,
    00039   WarnFailedPivotIIf,
    00040   DUMMY_END
    00041 };
    00043 class LandPMessages : public CoinMessages
    00044 {
    00045 public:
    00046
    00048   LandPMessages();
    00049 };
    00050
    00051
    00052
    00053 class CglLandPSimplex
    00054 {
    00055 public:
    00056     struct TabRow
    00057   {
    00058     TabRow():num(-1), row(NULL), rhs(0), n_(0) {}
    00059     TabRow(const TabRow & source):num(source.num), row(NULL), rhs(source.rhs), n_(source.n_)
    00060     {
    00061       row = new double[n_];
    00062       CoinCopyN(source.row, n_, row);
    00063     }
    00064     void size(int n){if(row != NULL) delete [] row; row = new double[n]; n_=n;}
    00065     ~TabRow(){
    00066       if (row != NULL)
    00067         delete [] row;
    00068     }
    00069     void print(std::ostream & os, int width = 9, const int * nonBasics = NULL,
    00070  int m = 0)
    00071     {
    00072       os.width(3);
    00073       os.precision(4);
    00074       os.setf(std::ios_base::right, std::ios_base::adjustfield);
    00075       os<< num <<": ";
    00076       for(int j = 0 ; j < m ; j++)
    00077         {
    00078           os.width(width);
    00079           os.precision(3);
    00080           //      os.setf(std::ios_base::fixed, std::ios_base::floatfield);
    00081           os.setf(std::ios_base::right, std::ios_base::adjustfield);
    00082           os<<row[nonBasics[j]]<<" ";
    00083         }
    00084
    00085       os.width(width);
    00086       os.precision(4);
    00087       //    os.setf(std::ios_base::fixed, std::ios_base::floatfield);
    00088       os.setf(std::ios_base::right, std::ios_base::adjustfield);
    00089       os<<rhs;
    00090
    00091       os<<std::endl;
    00092
    00093     }
    00094     int num;
    00095     double *row;
    00096     double rhs;
    00097     int n_;
    00098   };
    00100   CglLandPSimplex(const OsiSolverInterface &si,
    00101                   const CglLandP::CachedData &cached,
    00102                   bool reducedSpace, int numPivots);
    00104   ~CglLandPSimplex();
    00106   void cacheUpdate(const CglLandP::CachedData &cached, bool reducedSpace = 0);
    00108   bool resetSolver(const CoinWarmStartBasis * basis);
    00110   bool findBestCut(int var, OsiRowCut & cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params);
    00112   bool generateMig(int row, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params) const;
    00113
    00115   CglLandPSimplex()
    00116 #ifdef LandP_DEBUG
    00117     :debug_(0,0)
    00118 #endif
    00119   {
    00120     std::cerr<<"Class CglLandPSimplex has no default constructor"<<std::endl;
    00121     throw CoinError("No default constructor","CglLandPSimplex","CglLandPSimplex()");
    00122   }
    00123     void setLogLevel(int level)
    00124   { handler_->setLogLevel(level);}
    00125
    00126
    00127   void setSi(OsiSolverInterface *si)
    00128   {si_ = si;}
    00129   void freeSi()
    00130   {delete si_;}
    00131
    00132   struct extraInfo {
    00133     extraInfo():
    00134 #if LandP_DEBUG > 1
    00135       Nnz(0), Nneg(0),
    00136 #endif
    00137       AngleToObj(0),
    00138       numPivots(0), depth(0.),
    00139       nNegativeRcRows(0), bestRow(0),
    00140       maxBestRow(0), bestRc(0.),
    00141       maxRc(-DBL_MAX)
    00142     {}
    00143 #if LandP_DEBUG > 1
    00144     int Nnz;
    00145     int Nneg;
    00146 #endif
    00147     double AngleToObj;
    00148     int numPivots;
    00149     double depth;
    00150     int nNegativeRcRows;
    00151     int bestRow;
    00152     int maxBestRow;
    00153     double bestRc;
    00154     double maxRc;
    00155   };
    00156   mutable extraInfo extra;
    00157
    00158 protected:
    00160   bool changeBasis(int incoming, int leaving, int direction);
    00163   int findCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance);
    00167   int fastFindCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance);
    00169   int rescanReducedCosts( int &direction, int &gammaSign, double tolerance);
    00171   int fastFindBestPivotColumn(int direction, int gammaSign,
    00172                           double pivotTol, double rhsTol,
    00173                           bool reducedSpace,
    00174                           bool allowNonImproving,
    00175                           double &bestSigma);
    00177   int findBestPivotColumn(int direction,
    00178                           double pivotTol, bool reducedSpace, bool allowDegeneratePivot,
    00179                           bool modularize);
    00180 #if 0
    00181 int plotCGLPobj(int direction, double gammaTolerance,
    00182                 double pivotTol, bool reducedSpace, bool allowDegenerate, bool modularize);
    00183 #endif
    00184
    00196   int findBestPivot(int &leaving, int & direction,
    00197                     const CglLandP::Parameters & params);
    00199   double computeCglpObjective(double gamma, bool strengthen);
    00202   double computeCglpObjective(TabRow & row) const;
    00204    inline double intersectionCutCoef(double alpha_i, double beta) const;
    00208   inline double strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const;
    00211   inline double newRowCoefficient(int j, double gamma) const;
    00214   inline double modularizedCoef(double alpha, double beta) const;
    00216   double computeCglpRedCost(int direction, int gammaSign);
    00218   void computeRedCostConstantsInRow();
    00220   void createIntersectionCut(const TabRow & row, OsiRowCut &cut) const;
    00222         //  void createIntersectionCut(double * row);
    00224   void createMIG( TabRow & row, OsiRowCut &cut) const;
    00227   double normCoef(TabRow &row);
    00229   void scale(OsiRowCut &cut, double norma);
    00231   void scale(OsiRowCut &cut);
    00233   void modularizeRow(TabRow & row);
    00235   void pullTableauRow(TabRow & row) const;
    00237   void adjustTableauRow(int var, TabRow & row, int direction);
    00239   void resetOriginalTableauRow(int var, TabRow & row, int direction);
    00241   inline double getLoBound(int index){return loBounds_[index];}
    00243   inline double getUpBound(int index){return upBounds_[index];}
    00245   void printTableau(std::ostream & os);
    00246 private:
    00247
    00248   enum lpSolver {clp, cplex, xpress};
    00249   lpSolver solver_;
    00250   void updateM1_M2_M3(TabRow & row, double tolerance, bool recucedSpace, bool alwaysComputeCheap);
    00251
    00254
    00255   mutable CglLandPSimplex::TabRow row_k_;
    00257   CglLandPSimplex::TabRow perturbed_row_k_;
    00259   CglLandPSimplex::TabRow row_i_;
    00261   CglLandPSimplex::TabRow newRow_;
    00263   CoinPackedVector gammas_;
    00265   double * rWk1_;
    00267   double * rWk2_;
    00269   double * rWk3_;
    00271   double * rWk4_;
    00273   int * rIntWork_;
    00275   bool * rowFlags_;
    00277   bool *colHasToComputeContrib_;
    00279   bool *colCandidateToLeave_;
    00281   int * basics_;
    00283   int * nonBasics_;
    00285   int * inM1_;
    00287   int * inM2_;
    00289   int * inM3_;
    00291   double tau_;
    00293   double sigma_;
    00295   CoinWarmStartBasis basis_;
    00297    double * colsolToCut_;
    00299    double * colsol_;
    00301   int numcols_;
    00303   int numrows_;
    00304   // for fast access to lower bounds (both cols and rows)
    00305   double * loBounds_;
    00306   // for fast access to upper bounds (both cols and rows)
    00307   double * upBounds_;
    00309   bool inDegenerateSequence_;
    00311   double chosenReducedCostVal_;
    00313   const bool * integers_;
    00317
    00318   OsiSolverInterface * si_;
    00321   bool own_;
    00322
    00323
    00325   int nNegativeRc_;
    00327   int nNegativeRcRows_;
    00328 #ifdef LandP_DEBUG
    00329
    00330 #if LandP_DEBUG > 1
    00331
    00332 void put_in_non_basic_init_space( OsiRowCut &cut);
    00333 #endif
    00334   friend class DebugData;
    00336   class DebugData
    00337   {
    00338   public:
    00339     DebugData(int n, int m):
    00340       bestNewRow_(NULL),
    00341       req(1e-05),
    00342       eq(1e-5)
    00343 #if LandP+DEBUG> 1
    00344       , initialTableau_(), initialBasics_(NULL), initialBasis_(NULL)
    00345 #endif
    00346
    00347     {
    00348       bestNewRow_ = new double[n + m];
    00349 #if LandP_DEBUG > 1
    00350       initialBasics_ = new int[m];
    00351       initialNonBasics_ = new int[n];
    00352       initialColsol_ = new double[n + m];
    00353       trueInitialSol_ = new double[n + m];
    00354 #endif
    00355     }
    00356     ~DebugData()
    00357     {
    00358       delete [] bestNewRow_;
    00359 #if LandP_DEBUG > 1
    00360       delete [] initialBasics_;
    00361       delete [] initialNonBasics_;
    00362       delete [] initialColsol_;
    00363       delete [] trueInitialSol_;
    00364       if(initialBasis_)
    00365         delete initialBasis_;
    00366 #endif
    00367     }
    00369     double * bestNewRow_;
    00371     double bestNewRhs_;
    00373     double newSigma_;
    00375     CoinRelFltEq req;
    00377     CoinAbsFltEq eq;
    00378
    00379 #if LandP_DEBUG > 1
    00380
    00381     void getCurrentTableau(OsiSolverInterface &si, CglLandPSimplex &lap);
    00383     CoinPackedMatrix initialTableau_;
    00385     int * initialBasics_;
    00387     int *initialNonBasics_;
    00389     CoinWarmStartBasis * initialBasis_;
    00391     double * initialColsol_;
    00393     double * trueInitialSol_;
    00394 #endif
    00395   };
    00396   DebugData debug_;
    00397 #endif
    00399
    00400   CoinMessageHandler * handler_;
    00401
    00402   CoinMessages messages_;
    00403 };
    00404
    00406 double
    00407 CglLandPSimplex::intersectionCutCoef(double alpha_i, double beta) const
    00408 {
    00409   if(alpha_i>0) return alpha_i* (1 - beta);
    00410   else return -alpha_i * beta;// (1 - beta);
    00411 }
    00412
    00414 double
    00415 CglLandPSimplex::strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const
    00416 {
    00417   //  double ratio = beta/(1-beta);
    00418   if( (!integers_[i]))
    00419     return intersectionCutCoef(alpha_i, beta);
    00420   else
    00421   {
    00422     double f_i = alpha_i - floor(alpha_i);
    00423     if(f_i < beta)
    00424       return f_i*(1- beta);
    00425     else
    00426       return (1 - f_i)*beta;//(1-beta);
    00427   }
    00428 }
    00429
    00432 double
    00433 CglLandPSimplex::newRowCoefficient(int j, double gamma) const
    00434 {
    00435   return row_k_.row[j] + gamma * row_i_.row[j];
    00436 }
    00437
    00439 double
    00440 CglLandPSimplex::modularizedCoef(double alpha, double beta) const
    00441 {
    00442   double f_i = alpha - floor(alpha);
    00443   if(f_i <= beta)
    00444     return f_i;
    00445   else
    00446     return f_i - 1;
    00447 }
    00448
    00449
    00450
    00451
    00452 }
    00453 #endif