00001
00002
00003
00004
00005
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
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
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
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
00305 double * loBounds_;
00306
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;
00411 }
00412
00414 double
00415 CglLandPSimplex::strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const
00416 {
00417
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;
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