coin-Cgl
CglKnapsackCover.hpp
Go to the documentation of this file.
1 // Copyright (C) 2000, International Business Machines
2 // Corporation and others. All Rights Reserved.
3 #ifndef CglKnapsackCover_H
4 #define CglKnapsackCover_H
5 
6 #include <string>
7 
8 #include "CglCutGenerator.hpp"
9 #include "CglTreeInfo.hpp"
10 
13  friend void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
14  const std::string mpdDir );
15 
16 public:
18  void setTestedRowIndices(int num, const int* ind);
19 
25  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
26  const CglTreeInfo info = CglTreeInfo()) const;
28 
33 
36  const CglKnapsackCover &);
37 
39  virtual CglCutGenerator * clone() const;
40 
43  operator=(
44  const CglKnapsackCover& rhs);
45 
47  virtual
50  virtual std::string generateCpp( FILE * fp);
52  virtual void refreshSolver(OsiSolverInterface * solver);
54 
55 
58  inline void setMaxInKnapsack(int value)
60  { if (value>0) maxInKnapsack_ = value;}
62  inline int getMaxInKnapsack() const
63  {return maxInKnapsack_;}
65  inline void switchOffExpensive()
66  { expensiveCuts_=false;}
68  inline void switchOnExpensive()
69  { expensiveCuts_=true;}
70 private:
71 
72  // Private member methods
73 
74 
77 
85  int deriveAKnapsack(
86  const OsiSolverInterface & si,
87  OsiCuts & cs,
88  CoinPackedVector & krow,
89  bool treatAsLRow,
90  double & b,
91  int * complement,
92  double * xstar,
93  int rowIndex,
94  int numberElements,
95  const int * index,
96  const double * element) const;
97 
98  int deriveAKnapsack(
99  const OsiSolverInterface & si,
100  OsiCuts & cs,
101  CoinPackedVector & krow,
102  double & b,
103  int * complement,
104  double * xstar,
105  int rowIndex,
106  const CoinPackedVectorBase & matrixRow) const;
107 
114  int nCols,
115  int row,
116  CoinPackedVector & krow,
117  double b,
118  double * xstar,
119  CoinPackedVector & cover,
120  CoinPackedVector & remainder) const ;
121 
126  int nCols,
127  int row,
128  CoinPackedVector & krow,
129  double & b,
130  double * xstar,
131  CoinPackedVector & cover,
132  CoinPackedVector & remainder) const;
133 
135  int findGreedyCover(
136  int row,
137  CoinPackedVector & krow,
138  double & b,
139  double * xstar,
140  CoinPackedVector & cover,
141  CoinPackedVector & remainder
142  ) const;
143 
145  int liftCoverCut(
146  double & b,
147  int nRowElem,
148  CoinPackedVector & cover,
149  CoinPackedVector & remainder,
150  CoinPackedVector & cut ) const;
151 
154  double rowub,
155  CoinPackedVector & krow,
156  double & b,
157  int * complement,
158  int row,
159  CoinPackedVector & cover,
160  CoinPackedVector & remainder,
161  OsiCuts & cs ) const;
162 
165  int nCols,
166  double * xstar,
167  int * complement,
168  int row,
169  int nRowElem,
170  double & b,
171  CoinPackedVector & cover, // need not be violated
172  CoinPackedVector & remainder,
173  OsiCuts & cs ) const;
174 
177  int nCols,
178  double * xstar,
179  int * complement,
180  int row,
181  int nRowElem,
182  double & b,
183 
184  // the following 3 packed vectors partition the krow:
185  CoinPackedVector & fracCover, // vars have frac soln values in lp relaxation
186  // and form cover with the vars atOne
187  CoinPackedVector & atOne, // vars have soln value of 1 in lp relaxation
188  // and together with fracCover form minimal (?) cover.
189  CoinPackedVector & remainder,
190  OsiCuts & cs ) const;
191 
194  int row,
195  CoinPackedVector & krow,
196  double & b,
197  double * xstar,
198  CoinPackedVector & cover,
199  CoinPackedVector & remainder) const;
200 
203  int row,
204  CoinPackedVector & krow,
205  double & b,
206  double * xstar,
207  CoinPackedVector & fracCover,
208  CoinPackedVector & atOnes,
209  CoinPackedVector & remainder) const;
210 
211 
219  int exactSolveKnapsack(
220  int n,
221  double c,
222  double const *pp,
223  double const *ww,
224  double & z,
225  int * x) const;
226 
232  int createCliques( OsiSolverInterface & si,
233  int minimumSize=2, int maximumSize=100, bool extendCliques=false);
235  void deleteCliques();
237 
238  // Private member data
239 
242  double epsilon_;
245  double epsilon2_;
247  double onetol_;
258  mutable const OsiSolverInterface * solver_;
259  mutable int whichRow_;
260  mutable int * complement_;
261  mutable double * elements_;
265  typedef struct {
266  unsigned int equality:1; // nonzero if clique is ==
267  } cliqueType;
289  //cliqueEntry * cliqueRow_;
291  //int * cliqueRowStart_;
293 };
294 
295 //#############################################################################
301 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
302  const std::string mpdDir );
303 
304 #endif