Cgl  trunk
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
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 // $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 &params,
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines