coin-Cgl
|
00001 // Copyright (C) 2005, 2007 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 #include <vector> 00012 00013 #include "CglLandP.hpp" 00014 00015 #include "OsiSolverInterface.hpp" 00016 #include "CoinMessage.hpp" 00017 #include "CoinMessageHandler.hpp" 00018 #include "CoinWarmStartBasis.hpp" 00019 #include "CoinPackedMatrix.hpp" 00020 00021 #include "OsiClpSolverInterface.hpp" 00022 #include "CglLandPTabRow.hpp" 00023 #include "CglLandPUtils.hpp" 00024 #include "CglLandPMessages.hpp" 00025 namespace LAP 00026 { 00028 class DebugData; 00029 00030 class CglLandPSimplex 00031 { 00032 public: 00034 CglLandPSimplex(const OsiSolverInterface &si, 00035 const CglLandP::CachedData &cached, 00036 const CglLandP::Parameters ¶ms, 00037 const Validator &validator); 00039 ~CglLandPSimplex(); 00041 void cacheUpdate(const CglLandP::CachedData &cached, bool reducedSpace = 0); 00043 bool resetSolver(const CoinWarmStartBasis * basis); 00045 bool optimize(int var, OsiRowCut & cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params); 00047 bool generateMig(int row, OsiRowCut &cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params) const; 00048 00050 int generateExtraCuts(const CglLandP::CachedData &cached, const CglLandP::Parameters & params); 00052 int generateExtraCut(int i, const CglLandP::CachedData & cached, 00053 const CglLandP::Parameters& params); 00054 00055 void genThisBasisMigs(const CglLandP::CachedData &cached, 00056 const CglLandP::Parameters & params) ; 00057 00059 int insertAllExtr(OsiCuts & cs, CoinRelFltEq eq); 00060 00061 void setLogLevel(int level) { 00062 handler_->setLogLevel(level); 00063 } 00064 00065 00066 void setSi(OsiSolverInterface *si) { 00067 si_ = si; 00068 OsiClpSolverInterface * clpSi = dynamic_cast<OsiClpSolverInterface *>(si_); 00069 if (clpSi) { 00070 solver_ = clp; 00071 clp_ = clpSi; 00072 } 00073 } 00074 void freeSi() { 00075 delete si_; 00076 clp_ = NULL; 00077 } 00078 00079 Cuts& extraCuts() { 00080 return cuts_; 00081 } 00082 void loadBasis(const OsiSolverInterface &si, 00083 std::vector<int> &M1, std::vector<int> &M2, 00084 int k); 00085 00086 00087 int getNumCols() const { 00088 return ncols_; 00089 } 00090 00091 int getNumRows() const { 00092 return nrows_; 00093 } 00094 00095 const CoinWarmStartBasis * getBasis() const{ 00096 return basis_; 00097 } 00098 const int * getNonBasics() const{ 00099 return nonBasics_; 00100 } 00101 00102 const int * getBasics() const{ 00103 return basics_; 00104 } 00105 00106 protected: 00108 bool changeBasis(int incoming, int leaving, int direction, bool recompute_source_row); 00112 int fastFindCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance, bool flagPositiveRows); 00114 int rescanReducedCosts( int &direction, int &gammaSign, double tolerance); 00116 int fastFindBestPivotColumn(int direction, int gammaSign, 00117 double pivotTol, double rhsTol, 00118 bool reducedSpace, 00119 bool allowNonImproving, 00120 double &bestSigma); 00121 00129 int findBestPivot(int &leaving, int & direction, 00130 const CglLandP::Parameters & params); 00131 00132 00135 double computeCglpObjective(const TabRow & row) const; 00139 inline double strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const; 00142 inline double newRowCoefficient(int j, double gamma) const; 00144 void createIntersectionCut(TabRow & row, OsiRowCut &cut) const; 00146 double normalizationFactor(const TabRow & row) const; 00148 void scaleCut(OsiRowCut & cut, double factor) const; 00150 // void createIntersectionCut(double * row); 00152 void createMIG( TabRow & row, OsiRowCut &cut) const; 00154 void pullTableauRow(TabRow & row) const; 00156 void adjustTableauRow(int var, TabRow & row, int direction); 00158 void resetOriginalTableauRow(int var, TabRow & row, int direction); 00160 inline double getLoBound(int index) const { 00161 return lo_bounds_[original_index_[index]]; 00162 } 00164 inline double getUpBound(int index) const { 00165 return up_bounds_[original_index_[index]]; 00166 } 00168 inline double getColsolToCut(int index) const { 00169 return colsolToCut_[original_index_[index]]; 00170 } 00171 bool isGtConst(int index) const { 00172 return (index >= ncols_ && lo_bounds_[original_index_[index]] < -1e-10 && up_bounds_[original_index_[index]] <= 1e-09); 00173 } 00175 inline void setColsolToCut(int index, double value) { 00176 colsolToCut_[original_index_[index]] = value; 00177 } 00179 inline CoinWarmStartBasis::Status getStatus(int index) const { 00180 if (index < ncols_) return basis_->getStructStatus(index); 00181 return basis_->getArtifStatus(index - ncols_); 00182 } 00184 inline bool isInteger(int index) { 00185 return integers_[original_index_[index]]; 00186 } 00188 void computeWeights(CglLandP::LHSnorm norm, CglLandP::Normalization type, 00189 CglLandP::RhsWeightType rhs); 00191 double normedCoef(double a, int ii) const{ 00192 if (norm_weights_.empty()){ 00193 return a; 00194 } 00195 else { 00196 return a*norm_weights_[ii]; 00197 } 00198 } 00200 void printTableau(std::ostream & os); 00201 00203 void printTableauLateX(std::ostream & os); 00204 void printRowLateX(std::ostream & os, int i); 00205 void printCutLateX(std::ostream & os, int i); 00206 00208 void printCglpBasis(std::ostream& os = std::cout); 00210 void get_M1_M2_M3(const TabRow & row, 00211 std::vector<int> &M1, 00212 std::vector<int> &M2, 00213 std::vector<int> &M3); 00214 private: 00216 CglLandPSimplex(); 00218 CglLandPSimplex(const CglLandPSimplex&); 00220 CglLandPSimplex& operator=(const CglLandPSimplex&); 00221 enum lpSolver {clp 00222 #ifdef COIN_HAS_CPX 00223 ,cplex 00224 #endif 00225 #ifdef COIN_HAX_XPR 00226 ,xpress 00227 #endif 00228 }; 00230 lpSolver solver_; 00232 OsiClpSolverInterface * clp_; 00233 00234 00236 void updateM1_M2_M3(TabRow & row, double tolerance, bool recucedSpace, bool alwaysComputeCheap); 00238 void removeRows(int nDelete, const int * rowsIdx); 00239 00240 00241 void compute_p_q_r_s(double gamma, int gammaSign, double &p, double & q, double & r , double &s); 00242 00243 00246 00247 mutable TabRow row_k_; 00249 TabRow row_i_; 00250 #ifndef NDBEUG 00251 TabRow new_row_; 00252 #endif 00253 00254 CoinPackedVector gammas_; 00256 std::vector<double> rWk1_; 00258 std::vector<double> rWk2_; 00260 std::vector<double> rWk3_; 00262 std::vector<double> rWk4_; 00264 std::vector<int> rIntWork_; 00266 bool * rowFlags_; 00268 std::vector<bool> col_in_subspace; 00270 bool *colCandidateToLeave_; 00272 int * basics_; 00274 int * nonBasics_; 00276 std::vector<int> M1_; 00278 std::vector<int> M2_; 00280 std::vector<int> M3_; 00282 double sigma_; 00284 CoinWarmStartBasis * basis_; 00286 double * colsolToCut_; 00288 double * colsol_; 00290 int ncols_orig_; 00292 int nrows_orig_; 00294 int ncols_; 00296 int nrows_; 00297 // for fast access to lower bounds (both cols and rows) 00298 std::vector<double> lo_bounds_; 00299 // for fast access to upper bounds (both cols and rows) 00300 std::vector<double> up_bounds_; 00302 bool inDegenerateSequence_; 00304 double chosenReducedCostVal_; 00306 const bool * integers_; 00308 std::vector<int> original_index_; 00310 Cuts cuts_; 00314 00315 OsiSolverInterface * si_; 00318 bool own_; 00320 const Validator & validator_; 00322 std::vector<double> norm_weights_; 00324 double rhs_weight_; 00325 00327 int nNegativeRcRows_; 00329 bool checkBasis(); 00330 00331 00333 CoinMessageHandler * handler_; 00335 CoinMessages messages_; 00336 #ifndef NDEBUG 00337 double bestSigma_; 00338 #endif 00339 #ifdef LandP_DEBUG 00340 DebugData debug_; 00341 #endif 00342 00343 protected: 00347 double computeCglpRedCost(int direction, int gammaSign, double tau); 00349 double computeRedCostConstantsInRow(); 00351 double computeCglpObjective(double gamma, bool strengthen, TabRow &row); 00353 double computeCglpObjective(double gamma, bool strengthen); 00356 int findCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance); 00358 int findBestPivotColumn(int direction, 00359 double pivotTol, bool reducedSpace, bool allowDegeneratePivot, 00360 bool modularize); 00361 #if 1 00362 int plotCGLPobj(int direction, double gammaTolerance, 00363 double pivotTol, bool reducedSpace, bool allowDegenerate, bool modularize); 00364 #endif 00365 00367 }; 00368 00369 00371 double CglLandPSimplex::strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const 00372 { 00373 // double ratio = beta/(1-beta); 00374 if ( (!integers_[i])) 00375 return intersectionCutCoef(alpha_i, beta); 00376 else { 00377 double f_i = alpha_i - floor(alpha_i); 00378 if (f_i < beta) 00379 return f_i*(1- beta); 00380 else 00381 return (1 - f_i)*beta;//(1-beta); 00382 } 00383 } 00384 00387 double 00388 CglLandPSimplex::newRowCoefficient(int j, double gamma) const 00389 { 00390 return row_k_[j] + gamma * row_i_[j]; 00391 } 00392 00393 00394 00395 00396 #ifdef LandP_DEBUG 00397 00398 #if LandP_DEBUG > 1 00399 00400 void put_in_non_basic_init_space( OsiRowCut &cut); 00401 00403 void outputCurrentCut(const CglLandP::Parameters & params); 00404 00405 #endif 00406 friend class DebugData; 00408 class DebugData 00409 { 00410 public: 00411 DebugData(int n, int m): 00412 bestNewRow_(NULL), 00413 req(1e-05), 00414 eq(1e-5) 00415 #if LandP+DEBUG> 1 00416 , initialTableau_(), initialBasics_(NULL), initialBasis_(NULL) 00417 #endif 00418 { 00419 bestNewRow_ = new double[n + m]; 00420 #if LandP_DEBUG > 1 00421 initialBasics_ = new int[m]; 00422 initialNonBasics_ = new int[n]; 00423 initialColsol_ = new double[n + m]; 00424 trueInitialSol_ = new double[n + m]; 00425 #endif 00426 } 00427 ~DebugData() { 00428 delete [] bestNewRow_; 00429 #if LandP_DEBUG > 1 00430 delete [] initialBasics_; 00431 delete [] initialNonBasics_; 00432 delete [] initialColsol_; 00433 delete [] trueInitialSol_; 00434 if (initialBasis_) 00435 delete initialBasis_; 00436 #endif 00437 } 00439 double * bestNewRow_; 00441 double bestNewRhs_; 00443 double newSigma_; 00445 CoinRelFltEq req; 00447 CoinAbsFltEq eq; 00449 double lastSigma_; 00451 int outStatus_; 00452 00454 bool checkSigma(); 00456 bool checkNewCut(); 00458 bool saveOutgoingStatus(); 00459 00460 #if LandP_DEBUG > 1 00461 00462 void getCurrentTableau(OsiSolverInterface &si, CglLandPSimplex &lap); 00464 CoinPackedMatrix initialTableau_; 00466 int * initialBasics_; 00468 int *initialNonBasics_; 00470 CoinWarmStartBasis * initialBasis_; 00472 double * initialColsol_; 00474 double * trueInitialSol_; 00475 #endif 00476 }; 00477 #endif 00478 00479 } 00480 #endif