Cgl  0.58.9
CglKnapsackCover.hpp
Go to the documentation of this file.
1 // $Id: CglKnapsackCover.hpp 1123 2013-04-06 20:47:24Z stefan $
2 // Copyright (C) 2000, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5 
6 #ifndef CglKnapsackCover_H
7 #define CglKnapsackCover_H
8 
9 #include <string>
10 
11 #include "CglCutGenerator.hpp"
12 #include "CglTreeInfo.hpp"
13 
16  friend void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
17  const std::string mpdDir );
18 
19 public:
21  void setTestedRowIndices(int num, const int* ind);
22 
28  virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
29  const CglTreeInfo info = CglTreeInfo());
31 
36 
39  const CglKnapsackCover &);
40 
42  virtual CglCutGenerator * clone() const;
43 
46  operator=(
47  const CglKnapsackCover& rhs);
48 
50  virtual
53  virtual std::string generateCpp( FILE * fp);
55  virtual void refreshSolver(OsiSolverInterface * solver);
57 
58 
61  inline void setMaxInKnapsack(int value)
63  { if (value>0) maxInKnapsack_ = value;}
65  inline int getMaxInKnapsack() const
66  {return maxInKnapsack_;}
68  inline void switchOffExpensive()
69  { expensiveCuts_=false;}
71  inline void switchOnExpensive()
72  { expensiveCuts_=true;}
73 private:
74 
75  // Private member methods
76 
77 
80 
88  int deriveAKnapsack(
89  const OsiSolverInterface & si,
90  OsiCuts & cs,
91  CoinPackedVector & krow,
92  bool treatAsLRow,
93  double & b,
94  int * complement,
95  double * xstar,
96  int rowIndex,
97  int numberElements,
98  const int * index,
99  const double * element);
100 
101  int deriveAKnapsack(
102  const OsiSolverInterface & si,
103  OsiCuts & cs,
104  CoinPackedVector & krow,
105  double & b,
106  int * complement,
107  double * xstar,
108  int rowIndex,
109  const CoinPackedVectorBase & matrixRow);
110 
116  int findExactMostViolatedMinCover(
117  int nCols,
118  int row,
119  CoinPackedVector & krow,
120  double b,
121  double * xstar,
122  CoinPackedVector & cover,
123  CoinPackedVector & remainder);
124 
128  int findLPMostViolatedMinCover(
129  int nCols,
130  int row,
131  CoinPackedVector & krow,
132  double & b,
133  double * xstar,
134  CoinPackedVector & cover,
135  CoinPackedVector & remainder);
136 
138  int findGreedyCover(
139  int row,
140  CoinPackedVector & krow,
141  double & b,
142  double * xstar,
143  CoinPackedVector & cover,
144  CoinPackedVector & remainder
145  );
146 
148  int liftCoverCut(
149  double & b,
150  int nRowElem,
151  CoinPackedVector & cover,
152  CoinPackedVector & remainder,
153  CoinPackedVector & cut );
154 
156  int liftAndUncomplementAndAdd(
157  double rowub,
158  CoinPackedVector & krow,
159  double & b,
160  int * complement,
161  int row,
162  CoinPackedVector & cover,
163  CoinPackedVector & remainder,
164  OsiCuts & cs );
165 
167 void seqLiftAndUncomplementAndAdd(
168  int nCols,
169  double * xstar,
170  int * complement,
171  int row,
172  int nRowElem,
173  double & b,
174  CoinPackedVector & cover, // need not be violated
175  CoinPackedVector & remainder,
176  OsiCuts & cs );
177 
179 void liftUpDownAndUncomplementAndAdd(
180  int nCols,
181  double * xstar,
182  int * complement,
183  int row,
184  int nRowElem,
185  double & b,
186 
187  // the following 3 packed vectors partition the krow:
188  CoinPackedVector & fracCover, // vars have frac soln values in lp relaxation
189  // and form cover with the vars atOne
190  CoinPackedVector & atOne, // vars have soln value of 1 in lp relaxation
191  // and together with fracCover form minimal (?) cover.
192  CoinPackedVector & remainder,
193  OsiCuts & cs );
194 
196  int findPseudoJohnAndEllisCover (
197  int row,
198  CoinPackedVector & krow,
199  double & b,
200  double * xstar,
201  CoinPackedVector & cover,
202  CoinPackedVector & remainder);
203 
205  int findJohnAndEllisCover (
206  int row,
207  CoinPackedVector & krow,
208  double & b,
209  double * xstar,
210  CoinPackedVector & fracCover,
211  CoinPackedVector & atOnes,
212  CoinPackedVector & remainder);
213 
214 
222  int exactSolveKnapsack(
223  int n,
224  double c,
225  double const *pp,
226  double const *ww,
227  double & z,
228  int * x);
229 
235  int createCliques( OsiSolverInterface & si,
236  int minimumSize=2, int maximumSize=100, bool extendCliques=false);
238  void deleteCliques();
240 
241  // Private member data
242 
245  double epsilon_;
248  double epsilon2_;
250  double onetol_;
252  int maxInKnapsack_;
255  int numRowsToCheck_;
256  int* rowsToCheck_;
258  bool expensiveCuts_;
261  const OsiSolverInterface * solver_;
262  int whichRow_;
263  int * complement_;
264  double * elements_;
266  int numberCliques_;
268  typedef struct {
269  unsigned int equality:1; // nonzero if clique is ==
270  } cliqueType;
271  cliqueType * cliqueType_;
273  int * cliqueStart_;
275  cliqueEntry * cliqueEntry_;
278  int * oneFixStart_;
281  int * zeroFixStart_;
283  int * endFixStart_;
285  int * whichClique_;
287  int numberColumns_;
292  //cliqueEntry * cliqueRow_;
294  //int * cliqueRowStart_;
296 };
297 
298 //#############################################################################
304 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
305  const std::string mpdDir );
306 
307 #endif
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any information.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
void setTestedRowIndices(int num, const int *ind)
A method to set which rows should be tested for knapsack covers.
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
CglKnapsackCover()
Default constructor.
virtual ~CglKnapsackCover()
Destructor.
Derived class to pick up probing info.
Definition: CglTreeInfo.hpp:79
CglKnapsackCover & operator=(const CglKnapsackCover &rhs)
Assignment operator.
friend void CglKnapsackCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglKnapsackCover class.
void switchOffExpensive()
Switch off expensive cuts.
Cut Generator Base Class.
int getMaxInKnapsack() const
get limit on number in knapsack
void switchOnExpensive()
Switch on expensive cuts.
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate knapsack cover cuts for the model of the solver interface, si.
Knapsack Cover Cut Generator Class.
void setMaxInKnapsack(int value)
Set limit on number in knapsack.
virtual CglCutGenerator * clone() const
Clone.