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

- File List
- File Members

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