Cgl  0.60.2
CglKnapsackCover.hpp
Go to the documentation of this file.
1 // $Id: CglKnapsackCover.hpp 1201 2014-03-07 17:24:04Z forrest $
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 
15 class CglKnapsackCover : public CglCutGenerator {
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 
34  CglKnapsackCover ();
36 
38  CglKnapsackCover (
39  const CglKnapsackCover &);
40 
42  virtual CglCutGenerator * clone() const;
43 
45  CglKnapsackCover &
46  operator=(
47  const CglKnapsackCover& rhs);
48 
50  virtual
51  ~CglKnapsackCover ();
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);
230  int gubifyCut(CoinPackedVector & cut);
231 public:
237  int createCliques( OsiSolverInterface & si,
238  int minimumSize=2, int maximumSize=100, bool extendCliques=false);
239 private:
241  void deleteCliques();
243 
244  // Private member data
245 
248  double epsilon_;
251  double epsilon2_;
253  double onetol_;
255  int maxInKnapsack_;
258  int numRowsToCheck_;
259  int* rowsToCheck_;
261  bool expensiveCuts_;
264  const OsiSolverInterface * solver_;
265  int whichRow_;
266  int * complement_;
267  double * elements_;
269  int numberCliques_;
271  typedef struct {
272  unsigned int equality:1; // nonzero if clique is ==
273  } CliqueType;
274  CliqueType * cliqueType_;
276  int * cliqueStart_;
278  CliqueEntry * cliqueEntry_;
281  int * oneFixStart_;
284  int * zeroFixStart_;
286  int * endFixStart_;
288  int * whichClique_;
290  int numberColumns_;
295  //CliqueEntry * cliqueRow_;
297  //int * cliqueRowStart_;
299 };
300 
301 //#############################################################################
307 void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
308  const std::string mpdDir );
309 
310 #endif
CglKnapsackCover::switchOnExpensive
void switchOnExpensive()
Switch on expensive cuts.
Definition: CglKnapsackCover.hpp:71
CglKnapsackCover::CglKnapsackCoverUnitTest
friend void CglKnapsackCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglKnapsackCover class.
CglKnapsackCover::createCliques
int createCliques(OsiSolverInterface &si, int minimumSize=2, int maximumSize=100, bool extendCliques=false)
Creates cliques for use by probing.
CglTreeInfo
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
CoinPackedVector
CglTreeInfo.hpp
CglKnapsackCover::getMaxInKnapsack
int getMaxInKnapsack() const
get limit on number in knapsack
Definition: CglKnapsackCover.hpp:65
CglKnapsackCoverUnitTest
void CglKnapsackCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglKnapsackCover class.
CglCutGenerator.hpp
CglKnapsackCover::setMaxInKnapsack
void setMaxInKnapsack(int value)
Set limit on number in knapsack.
Definition: CglKnapsackCover.hpp:62
CglKnapsackCover::generateCuts
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate knapsack cover cuts for the model of the solver interface, si.
CglKnapsackCover
Knapsack Cover Cut Generator Class.
Definition: CglKnapsackCover.hpp:15
CglKnapsackCover::generateCpp
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
CglCutGenerator
Cut Generator Base Class.
Definition: CglCutGenerator.hpp:23
CglKnapsackCover::refreshSolver
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any information.
CoinPackedVectorBase
CglKnapsackCover::clone
virtual CglCutGenerator * clone() const
Clone.
CglKnapsackCover::CglKnapsackCover
CglKnapsackCover()
Default constructor.
cut
Definition: Cgl012cut.hpp:153
CglKnapsackCover::switchOffExpensive
void switchOffExpensive()
Switch off expensive cuts.
Definition: CglKnapsackCover.hpp:68
CglKnapsackCover::setTestedRowIndices
void setTestedRowIndices(int num, const int *ind)
A method to set which rows should be tested for knapsack covers.
CliqueEntry
Derived class to pick up probing info.
Definition: CglTreeInfo.hpp:86
CglKnapsackCover::~CglKnapsackCover
virtual ~CglKnapsackCover()
Destructor.
CglKnapsackCover::operator=
CglKnapsackCover & operator=(const CglKnapsackCover &rhs)
Assignment operator.
Generated by   doxygen 1.8.17