- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/Alps-1.2.1/Cgl/src/CglLandP/CglLandPSimplex.hpp

Go to the documentation of this file.

    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 #ifndef CglLandPSimplex_H
    00008 #define CglLandPSimplex_H
    00009
    00010 #include <iostream>
    00011 #include <vector>
    00012
    00013 #include "CglConfig.h"
    00014 #include "CglLandP.hpp"
    00015
    00016 #include "OsiSolverInterface.hpp"
    00017 #include "CoinMessage.hpp"
    00018 #include "CoinMessageHandler.hpp"
    00019 #include "CoinWarmStartBasis.hpp"
    00020 #include "CoinPackedMatrix.hpp"
    00021
    00022 #ifdef COIN_HAS_OSICLP
    00023 #include "OsiClpSolverInterface.hpp"
    00024 #endif
    00025
    00026 #include "CglLandPTabRow.hpp"
    00027 #include "CglLandPUtils.hpp"
    00028 #include "CglLandPMessages.hpp"
    00029
    00030 //#define APPEND_ROW
    00031 #define OLD_COMPUTATION
    00032
    00033 namespace LAP
    00034 {
    00036 class DebugData;
    00037
    00038 class CglLandPSimplex
    00039 {
    00040 public:
    00042     CglLandPSimplex(const OsiSolverInterface &si,
    00043                     const CglLandP::CachedData &cached,
    00044                     const CglLandP::Parameters &params,
    00045                     const Validator &validator);
    00047     ~CglLandPSimplex();
    00049     void cacheUpdate(const CglLandP::CachedData &cached, bool reducedSpace = 0);
    00051     bool resetSolver(const CoinWarmStartBasis * basis);
    00053     bool optimize(int var, OsiRowCut & cut, const CglLandP::CachedData &cached, const CglLandP::Parameters & params);
    00055     bool generateMig(int row, OsiRowCut &cut, const CglLandP::Parameters & params) const;
    00056
    00058     int generateExtraCuts(const CglLandP::CachedData &cached, const CglLandP::Parameters & params);
    00060     int generateExtraCut(int i, const CglLandP::CachedData & cached,
    00061                          const CglLandP::Parameters& params);
    00062
    00063     void genThisBasisMigs(const CglLandP::CachedData &cached,
    00064                           const CglLandP::Parameters & params) ;
    00065
    00067     int insertAllExtr(OsiCuts & cs, CoinRelFltEq eq);
    00068
    00069     void setLogLevel(int level)
    00070     {
    00071         handler_->setLogLevel(level);
    00072     }
    00073
    00074
    00075     void setSi(OsiSolverInterface *si)
    00076     {
    00077         si_ = si;
    00078 #ifdef COIN_HAS_OSICLP
    00079         OsiClpSolverInterface * clpSi = dynamic_cast<OsiClpSolverInterface *>(si_);
    00080         if (clpSi)
    00081         {
    00082             clp_ = clpSi;
    00083         }
    00084 #endif
    00085     }
    00086     void freeSi()
    00087     {
    00088         assert(si_ != NULL);
    00089         delete si_;
    00090         si_ = NULL;
    00091 #ifdef COIN_HAS_OSICLP
    00092         clp_ = NULL;
    00093 #endif
    00094     }
    00095
    00096     Cuts& extraCuts()
    00097     {
    00098         return cuts_;
    00099     }
    00100     void loadBasis(const OsiSolverInterface &si,
    00101                    std::vector<int> &M1, std::vector<int> &M2,
    00102                    int k);
    00103
    00104
    00105     int getNumCols() const
    00106     {
    00107         return ncols_;
    00108     }
    00109
    00110     int getNumRows() const
    00111     {
    00112         return nrows_;
    00113     }
    00114
    00115     const CoinWarmStartBasis  * getBasis() const
    00116     {
    00117         return basis_;
    00118     }
    00119     const int * getNonBasics() const
    00120     {
    00121         return nonBasics_;
    00122     }
    00123
    00124     const int * getBasics() const
    00125     {
    00126         return basics_;
    00127     }
    00128
    00129     void outPivInfo(int ncuts)
    00130     {
    00131         handler_->message(RoundStats, messages_)<<ncuts<<numPivots_
    00132         <<numSourceRowEntered_
    00133         <<numIncreased_<<CoinMessageEol;
    00134     }
    00135 #ifdef APPEND_ROW
    00136
    00137     void append_row(int row_num, bool modularize) ;
    00139     void update_row(TabRow &row);
    00140
    00141     void check_mod_row(TabRow &row);
    00142 #endif
    00143 protected:
    00145     bool changeBasis(int incoming, int leaving, int direction,
    00146 #ifndef OLD_COMPUTATION
    00147                      bool recompute_source_row,
    00148 #endif
    00149                      bool modularize);
    00153     int fastFindCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance, bool flagPositiveRows);
    00155     int rescanReducedCosts( int &direction, int &gammaSign, double tolerance);
    00157     int fastFindBestPivotColumn(int direction, int gammaSign,
    00158                                 double pivotTol, double rhsTol,
    00159                                 bool reducedSpace,
    00160                                 bool allowNonImproving,
    00161                                 double &bestSigma, bool modularize);
    00162
    00170     int findBestPivot(int &leaving, int & direction,
    00171                       const CglLandP::Parameters & params);
    00172
    00173
    00176     double computeCglpObjective(const TabRow & row, bool modularize = false) const;
    00180     inline double strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const;
    00183     inline double newRowCoefficient(int j, double gamma) const;
    00185     void createIntersectionCut(TabRow & row, OsiRowCut &cut) const;
    00187     double normalizationFactor(const TabRow & row) const;
    00189     void scaleCut(OsiRowCut & cut, double factor) const;
    00191     //  void createIntersectionCut(double * row);
    00193     void createMIG( TabRow & row, OsiRowCut &cut) const;
    00195     void pullTableauRow(TabRow & row) const;
    00197     void adjustTableauRow(int var, TabRow & row, int direction);
    00199     void resetOriginalTableauRow(int var, TabRow & row, int direction);
    00201     inline double getLoBound(int index) const
    00202     {
    00203         return lo_bounds_[original_index_[index]];
    00204     }
    00206     inline double getUpBound(int index) const
    00207     {
    00208         return up_bounds_[original_index_[index]];
    00209     }
    00211     inline double getColsolToCut(int index) const
    00212     {
    00213         return colsolToCut_[original_index_[index]];
    00214     }
    00215     bool isGtConst(int index) const
    00216     {
    00217         return (index >= ncols_ && lo_bounds_[original_index_[index]] < -1e-10 && up_bounds_[original_index_[index]] <= 1e-09);
    00218     }
    00220     inline void setColsolToCut(int index, double value)
    00221     {
    00222         colsolToCut_[original_index_[index]] = value;
    00223     }
    00225     inline CoinWarmStartBasis::Status getStatus(int index) const
    00226     {
    00227         if (index < ncols_) return basis_->getStructStatus(index);
    00228         return basis_->getArtifStatus(index - ncols_);
    00229     }
    00231     inline bool isInteger(int index) const
    00232     {
    00233         return integers_[original_index_[index]];
    00234     }
    00236     void computeWeights(CglLandP::LHSnorm norm, CglLandP::Normalization type,
    00237                         CglLandP::RhsWeightType rhs);
    00239     double normedCoef(double a, int ii) const
    00240     {
    00241         if (norm_weights_.empty())
    00242         {
    00243             return a;
    00244         }
    00245         else
    00246         {
    00247             return a*norm_weights_[ii];
    00248         }
    00249     }
    00251     void printTableau(std::ostream & os);
    00252
    00254   void printEverything();
    00256     void printTableauLateX(std::ostream & os);
    00257     void printRowLateX(std::ostream & os, int i);
    00258     void printCutLateX(std::ostream & os, int i);
    00259
    00261     void printCglpBasis(std::ostream& os = std::cout);
    00263     void get_M1_M2_M3(const TabRow & row,
    00264                       std::vector<int> &M1,
    00265                       std::vector<int> &M2,
    00266                       std::vector<int> &M3);
    00268     void eliminate_slacks(double * vec) const;
    00269 private:
    00271     CglLandPSimplex();
    00273     CglLandPSimplex(const CglLandPSimplex&);
    00275     CglLandPSimplex& operator=(const CglLandPSimplex&);
    00276 #ifdef COIN_HAS_OSICLP
    00277
    00278     OsiClpSolverInterface * clp_;
    00279 #endif
    00280
    00282     void updateM1_M2_M3(TabRow & row, double tolerance, bool alwaysComputeCheap);
    00284     void removeRows(int nDelete, const int * rowsIdx);
    00285
    00286
    00287     void compute_p_q_r_s(double gamma, int gammaSign, double &p, double & q, double & r , double &s);
    00288
    00289
    00292
    00293     mutable TabRow row_k_;
    00295     mutable TabRow original_row_k_;
    00297     TabRow row_i_;
    00298 #ifndef NDBEUG
    00299     TabRow new_row_;
    00300 #endif
    00301
    00302     CoinPackedVector gammas_;
    00304     std::vector<double> rWk1_;
    00306     std::vector<double> rWk2_;
    00308     std::vector<double> rWk3_;
    00310     std::vector<double> rWk4_;
    00312     std::vector<int> rIntWork_;
    00314     bool * rowFlags_;
    00316     std::vector<bool> col_in_subspace;
    00318     bool *colCandidateToLeave_;
    00320     int * basics_;
    00322     int * nonBasics_;
    00324     std::vector<int> M1_;
    00326     std::vector<int> M2_;
    00328     std::vector<int> M3_;
    00330     double sigma_;
    00332     CoinWarmStartBasis * basis_;
    00334     double * colsolToCut_;
    00336     double * colsol_;
    00338     int ncols_orig_;
    00340     int nrows_orig_;
    00342     int ncols_;
    00344     int nrows_;
    00345     // for fast access to lower bounds (both cols and rows)
    00346     std::vector<double> lo_bounds_;
    00347     // for fast access to upper bounds (both cols and rows)
    00348     std::vector<double> up_bounds_;
    00350     bool inDegenerateSequence_;
    00352     double chosenReducedCostVal_;
    00354     const bool * integers_;
    00356     std::vector<int> original_index_;
    00358     Cuts cuts_;
    00362
    00363     OsiSolverInterface * si_;
    00366     bool own_;
    00368     const Validator & validator_;
    00370     std::vector<double> norm_weights_;
    00372     double rhs_weight_;
    00373
    00375     int nNegativeRcRows_;
    00377     bool checkBasis();
    00378
    00380     int numPivots_;
    00382     int numSourceRowEntered_;
    00384     int numIncreased_;
    00385
    00387     CoinMessageHandler * handler_;
    00389     CoinMessages messages_;
    00390 #ifndef NDEBUG
    00391     double bestSigma_;
    00392 #endif
    00393
    00394 protected:
    00398     double computeCglpRedCost(int direction, int gammaSign, double tau);
    00400     double computeRedCostConstantsInRow();
    00402     double computeCglpObjective(double gamma, bool strengthen, TabRow &row);
    00404     double computeCglpObjective(double gamma, bool strengthen);
    00407     int findCutImprovingPivotRow( int &direction, int &gammaSign, double tolerance);
    00409     int findBestPivotColumn(int direction,
    00410                             double pivotTol, bool reducedSpace, bool allowDegeneratePivot,
    00411                             bool modularize);
    00412 #if 1
    00413     int plotCGLPobj(int direction, double gammaTolerance,
    00414                     double pivotTol, bool reducedSpace, bool allowDegenerate, bool modularize);
    00415 #endif
    00416
    00418 };
    00419
    00420
    00422 double CglLandPSimplex::strengthenedIntersectionCutCoef(int i, double alpha_i, double beta) const
    00423 {
    00424     //  double ratio = beta/(1-beta);
    00425     if ( (!integers_[i]))
    00426         return intersectionCutCoef(alpha_i, beta);
    00427     else
    00428     {
    00429         double f_i = alpha_i - floor(alpha_i);
    00430         if (f_i < beta)
    00431             return f_i*(1- beta);
    00432         else
    00433             return (1 - f_i)*beta;//(1-beta);
    00434     }
    00435 }
    00436
    00439 double
    00440 CglLandPSimplex::newRowCoefficient(int j, double gamma) const
    00441 {
    00442     return row_k_[j] + gamma * row_i_[j];
    00443 }
    00444
    00445 }
    00446 #endif