coin-Cgl
/build/buildd/coinor-cgl-0.55.0/Cgl/src/CglLandP/CglLandPSimplex.hpp
Go to the documentation of this file.
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 &params,
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