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
00052
00055
00056 inline void setMaxInKnapsack(int value)
00057 { if (value>0) maxInKnapsack_ = value;}
00059 inline int getMaxInKnapsack() const
00060 {return maxInKnapsack_;}
00062 inline void switchOffExpensive()
00063 { expensiveCuts_=false;}
00065 inline void switchOnExpensive()
00066 { expensiveCuts_=true;}
00067 private:
00068
00069
00070
00071
00074
00082 int deriveAKnapsack(
00083 const OsiSolverInterface & si,
00084 OsiCuts & cs,
00085 CoinPackedVector & krow,
00086 bool treatAsLRow,
00087 double & b,
00088 int * complement,
00089 double * xstar,
00090 int rowIndex,
00091 int numberElements,
00092 const int * index,
00093 const double * element) const;
00094
00095 int deriveAKnapsack(
00096 const OsiSolverInterface & si,
00097 OsiCuts & cs,
00098 CoinPackedVector & krow,
00099 double & b,
00100 int * complement,
00101 double * xstar,
00102 int rowIndex,
00103 const CoinPackedVectorBase & matrixRow) const;
00104
00110 int findExactMostViolatedMinCover(
00111 int nCols,
00112 int row,
00113 CoinPackedVector & krow,
00114 double b,
00115 double * xstar,
00116 CoinPackedVector & cover,
00117 CoinPackedVector & remainder) const ;
00118
00122 int findLPMostViolatedMinCover(
00123 int nCols,
00124 int row,
00125 CoinPackedVector & krow,
00126 double & b,
00127 double * xstar,
00128 CoinPackedVector & cover,
00129 CoinPackedVector & remainder) const;
00130
00132 int findGreedyCover(
00133 int row,
00134 CoinPackedVector & krow,
00135 double & b,
00136 double * xstar,
00137 CoinPackedVector & cover,
00138 CoinPackedVector & remainder
00139 ) const;
00140
00142 int liftCoverCut(
00143 double & b,
00144 int nRowElem,
00145 CoinPackedVector & cover,
00146 CoinPackedVector & remainder,
00147 CoinPackedVector & cut ) const;
00148
00150 int liftAndUncomplementAndAdd(
00151 double rowub,
00152 CoinPackedVector & krow,
00153 double & b,
00154 int * complement,
00155 int row,
00156 CoinPackedVector & cover,
00157 CoinPackedVector & remainder,
00158 OsiCuts & cs ) const;
00159
00161 void seqLiftAndUncomplementAndAdd(
00162 int nCols,
00163 double * xstar,
00164 int * complement,
00165 int row,
00166 int nRowElem,
00167 double & b,
00168 CoinPackedVector & cover,
00169 CoinPackedVector & remainder,
00170 OsiCuts & cs ) const;
00171
00173 void liftUpDownAndUncomplementAndAdd(
00174 int nCols,
00175 double * xstar,
00176 int * complement,
00177 int row,
00178 int nRowElem,
00179 double & b,
00180
00181
00182 CoinPackedVector & fracCover,
00183
00184 CoinPackedVector & atOne,
00185
00186 CoinPackedVector & remainder,
00187 OsiCuts & cs ) const;
00188
00190 int findPseudoJohnAndEllisCover (
00191 int row,
00192 CoinPackedVector & krow,
00193 double & b,
00194 double * xstar,
00195 CoinPackedVector & cover,
00196 CoinPackedVector & remainder) const;
00197
00199 int findJohnAndEllisCover (
00200 int row,
00201 CoinPackedVector & krow,
00202 double & b,
00203 double * xstar,
00204 CoinPackedVector & fracCover,
00205 CoinPackedVector & atOnes,
00206 CoinPackedVector & remainder) const;
00207
00208
00216 int exactSolveKnapsack(
00217 int n,
00218 double c,
00219 double const *pp,
00220 double const *ww,
00221 double & z,
00222 int * x) const;
00223
00225
00226
00227
00230
00231 double epsilon_;
00233 double epsilon2_;
00235 double onetol_;
00237 int maxInKnapsack_;
00240 int numRowsToCheck_;
00241 int* rowsToCheck_;
00243 bool expensiveCuts_;
00245 };
00246
00247
00253 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
00254 const std::string mpdDir );
00255
00256 #endif