coin-Cgl
|
00001 // Copyright (C) 2000, International Business Machines 00002 // Corporation and others. All Rights Reserved. 00003 #ifndef CglKnapsackCover_H 00004 #define CglKnapsackCover_H 00005 00006 #include <string> 00007 00008 #include "CglCutGenerator.hpp" 00009 #include "CglTreeInfo.hpp" 00010 00012 class CglKnapsackCover : public CglCutGenerator { 00013 friend void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP, 00014 const std::string mpdDir ); 00015 00016 public: 00018 void setTestedRowIndices(int num, const int* ind); 00019 00025 virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs, 00026 const CglTreeInfo info = CglTreeInfo()) const; 00028 00031 00032 CglKnapsackCover (); 00033 00035 CglKnapsackCover ( 00036 const CglKnapsackCover &); 00037 00039 virtual CglCutGenerator * clone() const; 00040 00042 CglKnapsackCover & 00043 operator=( 00044 const CglKnapsackCover& rhs); 00045 00047 virtual 00048 ~CglKnapsackCover (); 00050 virtual std::string generateCpp( FILE * fp); 00052 virtual void refreshSolver(OsiSolverInterface * solver); 00054 00055 00058 00059 inline void setMaxInKnapsack(int value) 00060 { if (value>0) maxInKnapsack_ = value;} 00062 inline int getMaxInKnapsack() const 00063 {return maxInKnapsack_;} 00065 inline void switchOffExpensive() 00066 { expensiveCuts_=false;} 00068 inline void switchOnExpensive() 00069 { expensiveCuts_=true;} 00070 private: 00071 00072 // Private member methods 00073 00074 00077 00085 int deriveAKnapsack( 00086 const OsiSolverInterface & si, 00087 OsiCuts & cs, 00088 CoinPackedVector & krow, 00089 bool treatAsLRow, 00090 double & b, 00091 int * complement, 00092 double * xstar, 00093 int rowIndex, 00094 int numberElements, 00095 const int * index, 00096 const double * element) const; 00097 00098 int deriveAKnapsack( 00099 const OsiSolverInterface & si, 00100 OsiCuts & cs, 00101 CoinPackedVector & krow, 00102 double & b, 00103 int * complement, 00104 double * xstar, 00105 int rowIndex, 00106 const CoinPackedVectorBase & matrixRow) const; 00107 00113 int findExactMostViolatedMinCover( 00114 int nCols, 00115 int row, 00116 CoinPackedVector & krow, 00117 double b, 00118 double * xstar, 00119 CoinPackedVector & cover, 00120 CoinPackedVector & remainder) const ; 00121 00125 int findLPMostViolatedMinCover( 00126 int nCols, 00127 int row, 00128 CoinPackedVector & krow, 00129 double & b, 00130 double * xstar, 00131 CoinPackedVector & cover, 00132 CoinPackedVector & remainder) const; 00133 00135 int findGreedyCover( 00136 int row, 00137 CoinPackedVector & krow, 00138 double & b, 00139 double * xstar, 00140 CoinPackedVector & cover, 00141 CoinPackedVector & remainder 00142 ) const; 00143 00145 int liftCoverCut( 00146 double & b, 00147 int nRowElem, 00148 CoinPackedVector & cover, 00149 CoinPackedVector & remainder, 00150 CoinPackedVector & cut ) const; 00151 00153 int liftAndUncomplementAndAdd( 00154 double rowub, 00155 CoinPackedVector & krow, 00156 double & b, 00157 int * complement, 00158 int row, 00159 CoinPackedVector & cover, 00160 CoinPackedVector & remainder, 00161 OsiCuts & cs ) const; 00162 00164 void seqLiftAndUncomplementAndAdd( 00165 int nCols, 00166 double * xstar, 00167 int * complement, 00168 int row, 00169 int nRowElem, 00170 double & b, 00171 CoinPackedVector & cover, // need not be violated 00172 CoinPackedVector & remainder, 00173 OsiCuts & cs ) const; 00174 00176 void liftUpDownAndUncomplementAndAdd( 00177 int nCols, 00178 double * xstar, 00179 int * complement, 00180 int row, 00181 int nRowElem, 00182 double & b, 00183 00184 // the following 3 packed vectors partition the krow: 00185 CoinPackedVector & fracCover, // vars have frac soln values in lp relaxation 00186 // and form cover with the vars atOne 00187 CoinPackedVector & atOne, // vars have soln value of 1 in lp relaxation 00188 // and together with fracCover form minimal (?) cover. 00189 CoinPackedVector & remainder, 00190 OsiCuts & cs ) const; 00191 00193 int findPseudoJohnAndEllisCover ( 00194 int row, 00195 CoinPackedVector & krow, 00196 double & b, 00197 double * xstar, 00198 CoinPackedVector & cover, 00199 CoinPackedVector & remainder) const; 00200 00202 int findJohnAndEllisCover ( 00203 int row, 00204 CoinPackedVector & krow, 00205 double & b, 00206 double * xstar, 00207 CoinPackedVector & fracCover, 00208 CoinPackedVector & atOnes, 00209 CoinPackedVector & remainder) const; 00210 00211 00219 int exactSolveKnapsack( 00220 int n, 00221 double c, 00222 double const *pp, 00223 double const *ww, 00224 double & z, 00225 int * x) const; 00226 00232 int createCliques( OsiSolverInterface & si, 00233 int minimumSize=2, int maximumSize=100, bool extendCliques=false); 00235 void deleteCliques(); 00237 00238 // Private member data 00239 00242 00243 double epsilon_; 00245 double epsilon2_; 00247 double onetol_; 00249 int maxInKnapsack_; 00252 int numRowsToCheck_; 00253 int* rowsToCheck_; 00255 bool expensiveCuts_; 00258 mutable const OsiSolverInterface * solver_; 00259 mutable int whichRow_; 00260 mutable int * complement_; 00261 mutable double * elements_; 00263 int numberCliques_; 00265 typedef struct { 00266 unsigned int equality:1; // nonzero if clique is == 00267 } cliqueType; 00268 cliqueType * cliqueType_; 00270 int * cliqueStart_; 00272 cliqueEntry * cliqueEntry_; 00275 int * oneFixStart_; 00278 int * zeroFixStart_; 00280 int * endFixStart_; 00282 int * whichClique_; 00284 int numberColumns_; 00289 //cliqueEntry * cliqueRow_; 00291 //int * cliqueRowStart_; 00293 }; 00294 00295 //############################################################################# 00301 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP, 00302 const std::string mpdDir ); 00303 00304 #endif