Cgl
trunk
|
00001 // Copyright (C) 2005-2009 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 // $Id$ 00008 // 00009 // This code is licensed under the terms of the Eclipse Public License (EPL). 00010 //--------------------------------------------------------------------------- 00011 #ifndef CglLandPSimplex_H 00012 #define CglLandPSimplex_H 00013 00014 #include <iostream> 00015 #include <vector> 00016 00017 #include "CglConfig.h" 00018 #include "CglLandP.hpp" 00019 00020 #include "OsiSolverInterface.hpp" 00021 #include "CoinMessage.hpp" 00022 #include "CoinMessageHandler.hpp" 00023 #include "CoinWarmStartBasis.hpp" 00024 #include "CoinPackedMatrix.hpp" 00025 00026 #ifdef COIN_HAS_OSICLP 00027 #include "OsiClpSolverInterface.hpp" 00028 #endif 00029 00030 #include "CglLandPTabRow.hpp" 00031 #include "CglLandPUtils.hpp" 00032 #include "CglLandPMessages.hpp" 00033 00034 //#define APPEND_ROW 00035 #define OLD_COMPUTATION 00036 00037 namespace LAP 00038 { 00040 class DebugData; 00041 00042 class CglLandPSimplex 00043 { 00044 public: 00046 CglLandPSimplex(const OsiSolverInterface &si, 00047 const CglLandP::CachedData &cached, 00048 const CglLandP::Parameters ¶ms, 00049 const Validator &validator); 00051 ~CglLandPSimplex(); 00053 void cacheUpdate(const CglLandP::CachedData &cached, bool reducedSpace = 0); 00055 bool resetSolver(const CoinWarmStartBasis * basis); 00057 bool optimize(int var, OsiRowCut & cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params); 00059 bool generateMig(int row, OsiRowCut &cut, const CglLandP::Parameters & params) const; 00060 00062 int generateExtraCuts(const CglLandP::CachedData &cached, const CglLandP::Parameters & params); 00064 int generateExtraCut(int i, const CglLandP::CachedData & cached, 00065 const CglLandP::Parameters& params); 00066 00067 void genThisBasisMigs(const CglLandP::CachedData &cached, 00068 const CglLandP::Parameters & params) ; 00069 00071 int insertAllExtr(OsiCuts & cs, CoinRelFltEq eq); 00072 00073 void setLogLevel(int level) 00074 { 00075 handler_->setLogLevel(level); 00076 } 00077 00078 00079 void setSi(OsiSolverInterface *si) 00080 { 00081 si_ = si; 00082 #ifdef COIN_HAS_OSICLP 00083 OsiClpSolverInterface * clpSi = dynamic_cast<OsiClpSolverInterface *>(si_); 00084 if (clpSi) 00085 { 00086 clp_ = clpSi; 00087 } 00088 #endif 00089 } 00090 void freeSi() 00091 { 00092 assert(si_ != NULL); 00093 delete si_; 00094 si_ = NULL; 00095 #ifdef COIN_HAS_OSICLP 00096 clp_ = NULL; 00097 #endif 00098 } 00099 00100 Cuts& extraCuts() 00101 { 00102 return cuts_; 00103 } 00104 void loadBasis(const OsiSolverInterface &si, 00105 std::vector<int> &M1, std::vector<int> &M2, 00106 int k); 00107 00108 00109 int getNumCols() const 00110 { 00111 return ncols_; 00112 } 00113 00114 int getNumRows() const 00115 { 00116 return nrows_; 00117 } 00118 00119 const CoinWarmStartBasis * getBasis() const 00120 { 00121 return basis_; 00122 } 00123 const int * getNonBasics() const 00124 { 00125 return nonBasics_; 00126 } 00127 00128 const int * getBasics() const 00129 { 00130 return basics_; 00131 } 00132 00133 void outPivInfo(int ncuts) 00134 { 00135 handler_->message(RoundStats, messages_)<<ncuts<<numPivots_ 00136 <<numSourceRowEntered_ 00137 <<numIncreased_<<CoinMessageEol; 00138 } 00139 #ifdef APPEND_ROW 00140 00141 void append_row(int row_num, bool modularize) ; 00143 void update_row(TabRow &row); 00144 00145 void check_mod_row(TabRow &row); 00146 #endif 00147 protected: 00149 bool changeBasis(int incoming, int leaving, int direction, 00150 #ifndef OLD_COMPUTATION 00151 bool recompute_source_row, 00152 #endif 00153 bool modularize); 00157 int fastFindCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance, bool flagPositiveRows); 00159 int rescanReducedCosts( int &direction, int &gammaSign, double tolerance); 00161 int fastFindBestPivotColumn(int direction, int gammaSign, 00162 double pivotTol, double rhsTol, 00163 bool reducedSpace, 00164 bool allowNonImproving, 00165 double &bestSigma, bool modularize); 00166 00174 int findBestPivot(int &leaving, int & direction, 00175 const CglLandP::Parameters & params); 00176 00177 00180 double computeCglpObjective(const TabRow & row, bool modularize = false) const; 00184 inline double strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const; 00187 inline double newRowCoefficient(int j, double gamma) const; 00189 void createIntersectionCut(TabRow & row, OsiRowCut &cut) const; 00191 double normalizationFactor(const TabRow & row) const; 00193 void scaleCut(OsiRowCut & cut, double factor) const; 00195 // void createIntersectionCut(double * row); 00197 void createMIG( TabRow & row, OsiRowCut &cut) const; 00199 void pullTableauRow(TabRow & row) const; 00201 void adjustTableauRow(int var, TabRow & row, int direction); 00203 void resetOriginalTableauRow(int var, TabRow & row, int direction); 00205 inline double getLoBound(int index) const 00206 { 00207 return lo_bounds_[original_index_[index]]; 00208 } 00210 inline double getUpBound(int index) const 00211 { 00212 return up_bounds_[original_index_[index]]; 00213 } 00215 inline double getColsolToCut(int index) const 00216 { 00217 return colsolToCut_[original_index_[index]]; 00218 } 00219 bool isGtConst(int index) const 00220 { 00221 return (index >= ncols_ && lo_bounds_[original_index_[index]] < -1e-10 && up_bounds_[original_index_[index]] <= 1e-09); 00222 } 00224 inline void setColsolToCut(int index, double value) 00225 { 00226 colsolToCut_[original_index_[index]] = value; 00227 } 00229 inline CoinWarmStartBasis::Status getStatus(int index) const 00230 { 00231 if (index < ncols_) return basis_->getStructStatus(index); 00232 return basis_->getArtifStatus(index - ncols_); 00233 } 00235 inline bool isInteger(int index) const 00236 { 00237 return integers_[original_index_[index]]; 00238 } 00240 void computeWeights(CglLandP::LHSnorm norm, CglLandP::Normalization type, 00241 CglLandP::RhsWeightType rhs); 00243 double normedCoef(double a, int ii) const 00244 { 00245 if (norm_weights_.empty()) 00246 { 00247 return a; 00248 } 00249 else 00250 { 00251 return a*norm_weights_[ii]; 00252 } 00253 } 00255 void printTableau(std::ostream & os); 00256 00258 void printEverything(); 00260 void printTableauLateX(std::ostream & os); 00261 void printRowLateX(std::ostream & os, int i); 00262 void printCutLateX(std::ostream & os, int i); 00263 00265 void printCglpBasis(std::ostream& os = std::cout); 00267 void get_M1_M2_M3(const TabRow & row, 00268 std::vector<int> &M1, 00269 std::vector<int> &M2, 00270 std::vector<int> &M3); 00272 void eliminate_slacks(double * vec) const; 00273 private: 00275 CglLandPSimplex(); 00277 CglLandPSimplex(const CglLandPSimplex&); 00279 CglLandPSimplex& operator=(const CglLandPSimplex&); 00280 #ifdef COIN_HAS_OSICLP 00281 00282 OsiClpSolverInterface * clp_; 00283 #endif 00284 00286 void updateM1_M2_M3(TabRow & row, double tolerance, bool alwaysComputeCheap); 00288 void removeRows(int nDelete, const int * rowsIdx); 00289 00290 00291 void compute_p_q_r_s(double gamma, int gammaSign, double &p, double & q, double & r , double &s); 00292 00293 00296 00297 mutable TabRow row_k_; 00299 mutable TabRow original_row_k_; 00301 TabRow row_i_; 00302 #ifndef NDBEUG 00303 TabRow new_row_; 00304 #endif 00305 00306 CoinPackedVector gammas_; 00308 std::vector<double> rWk1_; 00310 std::vector<double> rWk2_; 00312 std::vector<double> rWk3_; 00314 std::vector<double> rWk4_; 00316 std::vector<int> rIntWork_; 00318 bool * rowFlags_; 00320 std::vector<bool> col_in_subspace; 00322 bool *colCandidateToLeave_; 00324 int * basics_; 00326 int * nonBasics_; 00328 std::vector<int> M1_; 00330 std::vector<int> M2_; 00332 std::vector<int> M3_; 00334 double sigma_; 00336 CoinWarmStartBasis * basis_; 00338 double * colsolToCut_; 00340 double * colsol_; 00342 int ncols_orig_; 00344 int nrows_orig_; 00346 int ncols_; 00348 int nrows_; 00349 // for fast access to lower bounds (both cols and rows) 00350 std::vector<double> lo_bounds_; 00351 // for fast access to upper bounds (both cols and rows) 00352 std::vector<double> up_bounds_; 00354 bool inDegenerateSequence_; 00356 double chosenReducedCostVal_; 00358 const bool * integers_; 00360 std::vector<int> original_index_; 00362 Cuts cuts_; 00366 00367 OsiSolverInterface * si_; 00370 bool own_; 00372 const Validator & validator_; 00374 std::vector<double> norm_weights_; 00376 double rhs_weight_; 00377 00379 int nNegativeRcRows_; 00381 bool checkBasis(); 00382 00384 int numPivots_; 00386 int numSourceRowEntered_; 00388 int numIncreased_; 00389 00391 CoinMessageHandler * handler_; 00393 CoinMessages messages_; 00394 #ifndef NDEBUG 00395 double bestSigma_; 00396 #endif 00397 00398 protected: 00402 double computeCglpRedCost(int direction, int gammaSign, double tau); 00404 double computeRedCostConstantsInRow(); 00406 double computeCglpObjective(double gamma, bool strengthen, TabRow &row); 00408 double computeCglpObjective(double gamma, bool strengthen); 00411 int findCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance); 00413 int findBestPivotColumn(int direction, 00414 double pivotTol, bool reducedSpace, bool allowDegeneratePivot, 00415 bool modularize); 00416 #if 1 00417 int plotCGLPobj(int direction, double gammaTolerance, 00418 double pivotTol, bool reducedSpace, bool allowDegenerate, bool modularize); 00419 #endif 00420 00422 }; 00423 00424 00426 double CglLandPSimplex::strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const 00427 { 00428 // double ratio = beta/(1-beta); 00429 if ( (!integers_[i])) 00430 return intersectionCutCoef(alpha_i, beta); 00431 else 00432 { 00433 double f_i = alpha_i - floor(alpha_i); 00434 if (f_i < beta) 00435 return f_i*(1- beta); 00436 else 00437 return (1 - f_i)*beta;//(1-beta); 00438 } 00439 } 00440 00443 double 00444 CglLandPSimplex::newRowCoefficient(int j, double gamma) const 00445 { 00446 return row_k_[j] + gamma * row_i_[j]; 00447 } 00448 00449 } 00450 #endif