/home/coin/SVN-release/Alps-1.2.2/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

Generated on Fri Jan 7 03:09:09 2011 by  doxygen 1.4.7