00001
00002
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
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,
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
00185 CoinPackedVector & fracCover,
00186
00187 CoinPackedVector & atOne,
00188
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
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;
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
00291
00293 };
00294
00295
00301 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
00302 const std::string mpdDir );
00303
00304 #endif