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) const;
00026
00029
00030 CglKnapsackCover ();
00031
00033 CglKnapsackCover (
00034 const CglKnapsackCover &);
00035
00037 CglKnapsackCover &
00038 operator=(
00039 const CglKnapsackCover& rhs);
00040
00042 virtual
00043 ~CglKnapsackCover ();
00045
00046
00049
00050 inline void setMaxInKnapsack(int value)
00051 { if (value>0) maxInKnapsack_ = value;};
00053 inline int getMaxInKnapsack() const
00054 {return maxInKnapsack_;};
00055 private:
00056
00057
00058
00059
00062
00070 int deriveAKnapsack(
00071 const OsiSolverInterface & si,
00072 OsiCuts & cs,
00073 CoinPackedVector & krow,
00074 bool treatAsLRow,
00075 double & b,
00076 int * complement,
00077 double * xstar,
00078 int rowIndex,
00079 int numberElements,
00080 const int * index,
00081 const double * element) const;
00082
00083 int deriveAKnapsack(
00084 const OsiSolverInterface & si,
00085 OsiCuts & cs,
00086 CoinPackedVector & krow,
00087 double & b,
00088 int * complement,
00089 double * xstar,
00090 int rowIndex,
00091 const CoinPackedVectorBase & matrixRow) const;
00092
00098 int findExactMostViolatedMinCover(
00099 int nCols,
00100 int row,
00101 CoinPackedVector & krow,
00102 double b,
00103 double * xstar,
00104 CoinPackedVector & cover,
00105 CoinPackedVector & remainder) const ;
00106
00110 int findLPMostViolatedMinCover(
00111 int nCols,
00112 int row,
00113 CoinPackedVector & krow,
00114 double & b,
00115 double * xstar,
00116 CoinPackedVector & cover,
00117 CoinPackedVector & remainder) const;
00118
00120 int findGreedyCover(
00121 int row,
00122 CoinPackedVector & krow,
00123 double & b,
00124 double * xstar,
00125 CoinPackedVector & cover,
00126 CoinPackedVector & remainder
00127 ) const;
00128
00130 int liftCoverCut(
00131 double & b,
00132 int nRowElem,
00133 CoinPackedVector & cover,
00134 CoinPackedVector & remainder,
00135 CoinPackedVector & cut ) const;
00136
00138 int liftAndUncomplementAndAdd(
00139 double rowub,
00140 CoinPackedVector & krow,
00141 double & b,
00142 int * complement,
00143 int row,
00144 CoinPackedVector & cover,
00145 CoinPackedVector & remainder,
00146 OsiCuts & cs) const;
00147
00149 void seqLiftAndUncomplementAndAdd(
00150 int nCols,
00151 double * xstar,
00152 int * complement,
00153 int row,
00154 int nRowElem,
00155 double & b,
00156 CoinPackedVector & cover,
00157 CoinPackedVector & remainder,
00158 OsiCuts & cs) const;
00159
00161 void liftUpDownAndUncomplementAndAdd(
00162 int nCols,
00163 double * xstar,
00164 int * complement,
00165 int row,
00166 int nRowElem,
00167 double & b,
00168
00169
00170 CoinPackedVector & fracCover,
00171
00172 CoinPackedVector & atOne,
00173
00174 CoinPackedVector & remainder,
00175 OsiCuts & cs ) const;
00176
00178 int findPseudoJohnAndEllisCover (
00179 int row,
00180 CoinPackedVector & krow,
00181 double & b,
00182 double * xstar,
00183 CoinPackedVector & cover,
00184 CoinPackedVector & remainder) const;
00185
00187 int findJohnAndEllisCover (
00188 int row,
00189 CoinPackedVector & krow,
00190 double & b,
00191 double * xstar,
00192 CoinPackedVector & fracCover,
00193 CoinPackedVector & atOnes,
00194 CoinPackedVector & remainder) const;
00195
00196
00204 int exactSolveKnapsack(
00205 int n,
00206 double c,
00207 double const *pp,
00208 double const *ww,
00209 double & z,
00210 int * x) const;
00211
00213
00214
00215
00218
00219 double epsilon_;
00221 double epsilon2_;
00223 double onetol_;
00225 int maxInKnapsack_;
00228 int numRowsToCheck_;
00229 int* rowsToCheck_;
00231 };
00232
00233
00239 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
00240 const std::string mpdDir );
00241
00242 #endif