Cgl
trunk
|
00001 // $Id$ 00002 // Copyright (C) 2000, International Business Machines 00003 // Corporation and others. All Rights Reserved. 00004 // This code is licensed under the terms of the Eclipse Public License (EPL). 00005 00006 #ifndef CglKnapsackCover_H 00007 #define CglKnapsackCover_H 00008 00009 #include <string> 00010 00011 #include "CglCutGenerator.hpp" 00012 #include "CglTreeInfo.hpp" 00013 00015 class CglKnapsackCover : public CglCutGenerator { 00016 friend void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP, 00017 const std::string mpdDir ); 00018 00019 public: 00021 void setTestedRowIndices(int num, const int* ind); 00022 00028 virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs, 00029 const CglTreeInfo info = CglTreeInfo()) const; 00031 00034 00035 CglKnapsackCover (); 00036 00038 CglKnapsackCover ( 00039 const CglKnapsackCover &); 00040 00042 virtual CglCutGenerator * clone() const; 00043 00045 CglKnapsackCover & 00046 operator=( 00047 const CglKnapsackCover& rhs); 00048 00050 virtual 00051 ~CglKnapsackCover (); 00053 virtual std::string generateCpp( FILE * fp); 00055 virtual void refreshSolver(OsiSolverInterface * solver); 00057 00058 00061 00062 inline void setMaxInKnapsack(int value) 00063 { if (value>0) maxInKnapsack_ = value;} 00065 inline int getMaxInKnapsack() const 00066 {return maxInKnapsack_;} 00068 inline void switchOffExpensive() 00069 { expensiveCuts_=false;} 00071 inline void switchOnExpensive() 00072 { expensiveCuts_=true;} 00073 private: 00074 00075 // Private member methods 00076 00077 00080 00088 int deriveAKnapsack( 00089 const OsiSolverInterface & si, 00090 OsiCuts & cs, 00091 CoinPackedVector & krow, 00092 bool treatAsLRow, 00093 double & b, 00094 int * complement, 00095 double * xstar, 00096 int rowIndex, 00097 int numberElements, 00098 const int * index, 00099 const double * element) const; 00100 00101 int deriveAKnapsack( 00102 const OsiSolverInterface & si, 00103 OsiCuts & cs, 00104 CoinPackedVector & krow, 00105 double & b, 00106 int * complement, 00107 double * xstar, 00108 int rowIndex, 00109 const CoinPackedVectorBase & matrixRow) const; 00110 00116 int findExactMostViolatedMinCover( 00117 int nCols, 00118 int row, 00119 CoinPackedVector & krow, 00120 double b, 00121 double * xstar, 00122 CoinPackedVector & cover, 00123 CoinPackedVector & remainder) const ; 00124 00128 int findLPMostViolatedMinCover( 00129 int nCols, 00130 int row, 00131 CoinPackedVector & krow, 00132 double & b, 00133 double * xstar, 00134 CoinPackedVector & cover, 00135 CoinPackedVector & remainder) const; 00136 00138 int findGreedyCover( 00139 int row, 00140 CoinPackedVector & krow, 00141 double & b, 00142 double * xstar, 00143 CoinPackedVector & cover, 00144 CoinPackedVector & remainder 00145 ) const; 00146 00148 int liftCoverCut( 00149 double & b, 00150 int nRowElem, 00151 CoinPackedVector & cover, 00152 CoinPackedVector & remainder, 00153 CoinPackedVector & cut ) const; 00154 00156 int liftAndUncomplementAndAdd( 00157 double rowub, 00158 CoinPackedVector & krow, 00159 double & b, 00160 int * complement, 00161 int row, 00162 CoinPackedVector & cover, 00163 CoinPackedVector & remainder, 00164 OsiCuts & cs ) const; 00165 00167 void seqLiftAndUncomplementAndAdd( 00168 int nCols, 00169 double * xstar, 00170 int * complement, 00171 int row, 00172 int nRowElem, 00173 double & b, 00174 CoinPackedVector & cover, // need not be violated 00175 CoinPackedVector & remainder, 00176 OsiCuts & cs ) const; 00177 00179 void liftUpDownAndUncomplementAndAdd( 00180 int nCols, 00181 double * xstar, 00182 int * complement, 00183 int row, 00184 int nRowElem, 00185 double & b, 00186 00187 // the following 3 packed vectors partition the krow: 00188 CoinPackedVector & fracCover, // vars have frac soln values in lp relaxation 00189 // and form cover with the vars atOne 00190 CoinPackedVector & atOne, // vars have soln value of 1 in lp relaxation 00191 // and together with fracCover form minimal (?) cover. 00192 CoinPackedVector & remainder, 00193 OsiCuts & cs ) const; 00194 00196 int findPseudoJohnAndEllisCover ( 00197 int row, 00198 CoinPackedVector & krow, 00199 double & b, 00200 double * xstar, 00201 CoinPackedVector & cover, 00202 CoinPackedVector & remainder) const; 00203 00205 int findJohnAndEllisCover ( 00206 int row, 00207 CoinPackedVector & krow, 00208 double & b, 00209 double * xstar, 00210 CoinPackedVector & fracCover, 00211 CoinPackedVector & atOnes, 00212 CoinPackedVector & remainder) const; 00213 00214 00222 int exactSolveKnapsack( 00223 int n, 00224 double c, 00225 double const *pp, 00226 double const *ww, 00227 double & z, 00228 int * x) const; 00229 00235 int createCliques( OsiSolverInterface & si, 00236 int minimumSize=2, int maximumSize=100, bool extendCliques=false); 00238 void deleteCliques(); 00240 00241 // Private member data 00242 00245 00246 double epsilon_; 00248 double epsilon2_; 00250 double onetol_; 00252 int maxInKnapsack_; 00255 int numRowsToCheck_; 00256 int* rowsToCheck_; 00258 bool expensiveCuts_; 00261 mutable const OsiSolverInterface * solver_; 00262 mutable int whichRow_; 00263 mutable int * complement_; 00264 mutable double * elements_; 00266 int numberCliques_; 00268 typedef struct { 00269 unsigned int equality:1; // nonzero if clique is == 00270 } cliqueType; 00271 cliqueType * cliqueType_; 00273 int * cliqueStart_; 00275 cliqueEntry * cliqueEntry_; 00278 int * oneFixStart_; 00281 int * zeroFixStart_; 00283 int * endFixStart_; 00285 int * whichClique_; 00287 int numberColumns_; 00292 //cliqueEntry * cliqueRow_; 00294 //int * cliqueRowStart_; 00296 }; 00297 00298 //############################################################################# 00304 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP, 00305 const std::string mpdDir ); 00306 00307 #endif