- Main Page
- Namespaces
- Classes
- Files
- Directories

- Search for |

- File List
- File Members

# 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