00001
00002
00003
00004
00005
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
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
00298 std::vector<double> lo_bounds_;
00299
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
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;
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