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
int numberColumns_
Number of columns.
int numRowsToCheck_
which rows to look at.
void setMaxInKnapsack(int value)
Set limit on number in knapsack.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
int * rowsToCheck_
epsilon
int findExactMostViolatedMinCover(int nCols, int row, CoinPackedVector &krow, double b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
Find a violated minimal cover from a canonical form knapsack inequality by solving the -most- violate...
void liftUpDownAndUncomplementAndAdd(int nCols, double *xstar, int *complement, int row, int nRowElem, double &b, CoinPackedVector &fracCover, CoinPackedVector &atOne, CoinPackedVector &remainder, OsiCuts &cs) const
sequence-dependent lift binary variables either up or down, uncomplement and add to the cut set ...
double epsilon_
epsilon
int * zeroFixStart_
Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.
int findLPMostViolatedMinCover(int nCols, int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
Find the most violate minimum cover by solving the lp-relaxation of the most-violate-min-cover proble...
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
Generate knapsack cover cuts for the model of the solver interface, si.
void seqLiftAndUncomplementAndAdd(int nCols, double *xstar, int *complement, int row, int nRowElem, double &b, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs) const
sequence-dependent lift, uncomplement and add the resulting cut to the cut set
CglKnapsackCover()
Default constructor.
int * whichClique_
Clique numbers for one or zero fixes.
int * complement_
epsilon
int maxInKnapsack_
Maximum in knapsack.
void setTestedRowIndices(int num, const int *ind)
A method to set which rows should be tested for knapsack covers.
int numberCliques_
Number of cliques.
int liftCoverCut(double &b, int nRowElem, CoinPackedVector &cover, CoinPackedVector &remainder, CoinPackedVector &cut) const
lift the cover inequality
friend void CglKnapsackCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglKnapsackCover class.
void switchOnExpensive()
Switch on expensive cuts.
int liftAndUncomplementAndAdd(double rowub, CoinPackedVector &krow, double &b, int *complement, int row, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs) const
sequence-independent lift and uncomplement and add the resulting cut to the cut set ...
double epsilon2_
Tolerance to use for violation - bigger than epsilon_.
int getMaxInKnapsack() const
get limit on number in knapsack
int * cliqueStart_
Start of each clique.
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.
int findGreedyCover(int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
find a minimum cover by a simple greedy approach
int * endFixStart_
End of fixes for a column.
int * oneFixStart_
Start of oneFixes cliques for a column in matrix or -1 if not in any clique.
Derived class to pick up probing info.
Definition: CglTreeInfo.hpp:74
int findJohnAndEllisCover(int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &fracCover, CoinPackedVector &atOnes, CoinPackedVector &remainder) const
find a cover using the basic logic found in OSL (w/o SOS)
Cut Generator Base Class.
Knapsack Cover Cut Generator Class.
cliqueType * cliqueType_
epsilon
cliqueEntry * cliqueEntry_
Entries for clique.
virtual CglCutGenerator * clone() const
Clone.
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any information.
int deriveAKnapsack(const OsiSolverInterface &si, OsiCuts &cs, CoinPackedVector &krow, bool treatAsLRow, double &b, int *complement, double *xstar, int rowIndex, int numberElements, const int *index, const double *element) const
deriveAKnapsack returns 1 if it is able to derive a (canonical) knapsack inequality in binary variabl...
CglKnapsackCover & operator=(const CglKnapsackCover &rhs)
Assignment operator.
double onetol_
1-epsilon
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:13
bool expensiveCuts_
exactKnapsack can be expensive - this switches off some
double * elements_
epsilon
const OsiSolverInterface * solver_
Cliques **** TEMP so can reference from listing.
int exactSolveKnapsack(int n, double c, double const *pp, double const *ww, double &z, int *x) const
A C-style implementation of the Horowitz-Sahni exact solution procedure for solving knapsack problem...
int findPseudoJohnAndEllisCover(int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const
find a cover using a variation of the logic found in OSL (w/o SOS)
void deleteCliques()
Delete all clique information.
int createCliques(OsiSolverInterface &si, int minimumSize=2, int maximumSize=100, bool extendCliques=false)
Creates cliques for use by probing.
virtual ~CglKnapsackCover()
Destructor.