00001
00002
00003 #ifndef CglKnapsackCover_H
00004 #define CglKnapsackCover_H
00005
00006 #include <string>
00007
00008 #include "CglCutGenerator.hpp"
00009
00011 class CglKnapsackCover : public CglCutGenerator {
00012 friend void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
00013 const std::string mpdDir );
00014
00015 public:
00017 void setTestedRowIndices(int num, const int* ind);
00018
00024 virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
00025 const CglTreeInfo info = CglTreeInfo()) const;
00027
00030
00031 CglKnapsackCover ();
00032
00034 CglKnapsackCover (
00035 const CglKnapsackCover &);
00036
00038 virtual CglCutGenerator * clone() const;
00039
00041 CglKnapsackCover &
00042 operator=(
00043 const CglKnapsackCover& rhs);
00044
00046 virtual
00047 ~CglKnapsackCover ();
00049 virtual std::string generateCpp( FILE * fp);
00051 virtual void refreshSolver(OsiSolverInterface * solver);
00053
00054
00057
00058 inline void setMaxInKnapsack(int value)
00059 { if (value>0) maxInKnapsack_ = value;}
00061 inline int getMaxInKnapsack() const
00062 {return maxInKnapsack_;}
00064 inline void switchOffExpensive()
00065 { expensiveCuts_=false;}
00067 inline void switchOnExpensive()
00068 { expensiveCuts_=true;}
00069 private:
00070
00071
00072
00073
00076
00084 int deriveAKnapsack(
00085 const OsiSolverInterface & si,
00086 OsiCuts & cs,
00087 CoinPackedVector & krow,
00088 bool treatAsLRow,
00089 double & b,
00090 int * complement,
00091 double * xstar,
00092 int rowIndex,
00093 int numberElements,
00094 const int * index,
00095 const double * element) const;
00096
00097 int deriveAKnapsack(
00098 const OsiSolverInterface & si,
00099 OsiCuts & cs,
00100 CoinPackedVector & krow,
00101 double & b,
00102 int * complement,
00103 double * xstar,
00104 int rowIndex,
00105 const CoinPackedVectorBase & matrixRow) const;
00106
00112 int findExactMostViolatedMinCover(
00113 int nCols,
00114 int row,
00115 CoinPackedVector & krow,
00116 double b,
00117 double * xstar,
00118 CoinPackedVector & cover,
00119 CoinPackedVector & remainder) const ;
00120
00124 int findLPMostViolatedMinCover(
00125 int nCols,
00126 int row,
00127 CoinPackedVector & krow,
00128 double & b,
00129 double * xstar,
00130 CoinPackedVector & cover,
00131 CoinPackedVector & remainder) const;
00132
00134 int findGreedyCover(
00135 int row,
00136 CoinPackedVector & krow,
00137 double & b,
00138 double * xstar,
00139 CoinPackedVector & cover,
00140 CoinPackedVector & remainder
00141 ) const;
00142
00144 int liftCoverCut(
00145 double & b,
00146 int nRowElem,
00147 CoinPackedVector & cover,
00148 CoinPackedVector & remainder,
00149 CoinPackedVector & cut ) const;
00150
00152 int liftAndUncomplementAndAdd(
00153 double rowub,
00154 CoinPackedVector & krow,
00155 double & b,
00156 int * complement,
00157 int row,
00158 CoinPackedVector & cover,
00159 CoinPackedVector & remainder,
00160 OsiCuts & cs ) const;
00161
00163 void seqLiftAndUncomplementAndAdd(
00164 int nCols,
00165 double * xstar,
00166 int * complement,
00167 int row,
00168 int nRowElem,
00169 double & b,
00170 CoinPackedVector & cover,
00171 CoinPackedVector & remainder,
00172 OsiCuts & cs ) const;
00173
00175 void liftUpDownAndUncomplementAndAdd(
00176 int nCols,
00177 double * xstar,
00178 int * complement,
00179 int row,
00180 int nRowElem,
00181 double & b,
00182
00183
00184 CoinPackedVector & fracCover,
00185
00186 CoinPackedVector & atOne,
00187
00188 CoinPackedVector & remainder,
00189 OsiCuts & cs ) const;
00190
00192 int findPseudoJohnAndEllisCover (
00193 int row,
00194 CoinPackedVector & krow,
00195 double & b,
00196 double * xstar,
00197 CoinPackedVector & cover,
00198 CoinPackedVector & remainder) const;
00199
00201 int findJohnAndEllisCover (
00202 int row,
00203 CoinPackedVector & krow,
00204 double & b,
00205 double * xstar,
00206 CoinPackedVector & fracCover,
00207 CoinPackedVector & atOnes,
00208 CoinPackedVector & remainder) const;
00209
00210
00218 int exactSolveKnapsack(
00219 int n,
00220 double c,
00221 double const *pp,
00222 double const *ww,
00223 double & z,
00224 int * x) const;
00225
00231 int createCliques( OsiSolverInterface & si,
00232 int minimumSize=2, int maximumSize=100, bool extendCliques=false);
00234 void deleteCliques();
00236
00237
00238
00241
00242 double epsilon_;
00244 double epsilon2_;
00246 double onetol_;
00248 int maxInKnapsack_;
00251 int numRowsToCheck_;
00252 int* rowsToCheck_;
00254 bool expensiveCuts_;
00257 mutable const OsiSolverInterface * solver_;
00258 mutable int whichRow_;
00259 mutable int * complement_;
00260 mutable double * elements_;
00262 int numberCliques_;
00264 typedef struct {
00265 unsigned int equality:1;
00266 } cliqueType;
00267 cliqueType * cliqueType_;
00269 int * cliqueStart_;
00271 typedef struct {
00272 unsigned int oneFixes:1;
00273 unsigned int sequence:31;
00274 } cliqueEntry;
00275 cliqueEntry * cliqueEntry_;
00278 int * oneFixStart_;
00281 int * zeroFixStart_;
00283 int * endFixStart_;
00285 int * whichClique_;
00287 int numberColumns_;
00292
00294
00296 };
00297
00298
00304 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
00305 const std::string mpdDir );
00306
00307 #endif