Cbc  2.10.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
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 
117  int nCols,
118  int row,
119  CoinPackedVector & krow,
120  double b,
121  double * xstar,
122  CoinPackedVector & cover,
123  CoinPackedVector & remainder);
124 
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 
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 
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 
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 
197  int row,
198  CoinPackedVector & krow,
199  double & b,
200  double * xstar,
201  CoinPackedVector & cover,
202  CoinPackedVector & remainder);
203 
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);
231 public:
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_;
266  int * complement_;
267  double * elements_;
271  typedef struct {
272  unsigned int equality:1; // nonzero if clique is ==
273  } CliqueType;
295  //CliqueEntry * cliqueRow_;
297  //int * cliqueRowStart_;
299 };
300 
301 //#############################################################################
308  const std::string mpdDir );
309 
310 #endif
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any information.
int * zeroFixStart_
Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
int * oneFixStart_
Start of oneFixes cliques for a column in matrix or -1 if not in any clique.
int * whichClique_
Clique numbers for one or zero fixes.
void deleteCliques()
Delete all clique information.
void liftUpDownAndUncomplementAndAdd(int nCols, double *xstar, int *complement, int row, int nRowElem, double &b, CoinPackedVector &fracCover, CoinPackedVector &atOne, CoinPackedVector &remainder, OsiCuts &cs)
sequence-dependent lift binary variables either up or down, uncomplement and add to the cut set ...
void setTestedRowIndices(int num, const int *ind)
A method to set which rows should be tested for knapsack covers.
const OsiSolverInterface * solver_
Cliques **** TEMP so can reference from listing.
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
int liftAndUncomplementAndAdd(double rowub, CoinPackedVector &krow, double &b, int *complement, int row, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs)
sequence-independent lift and uncomplement and add the resulting cut to the cut set ...
CliqueType * cliqueType_
CglKnapsackCover()
Default constructor.
bool expensiveCuts_
exactKnapsack can be expensive - this switches off some
int findGreedyCover(int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
find a minimum cover by a simple greedy approach
virtual ~CglKnapsackCover()
Destructor.
int maxInKnapsack_
Maximum in knapsack.
Abstract Base Class for describing an interface to a solver.
int gubifyCut(CoinPackedVector &cut)
For testing gub stuff.
int findExactMostViolatedMinCover(int nCols, int row, CoinPackedVector &krow, double b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
Find a violated minimal cover from a canonical form knapsack inequality by solving the -most- viol...
Abstract base class for various sparse vectors.
CliqueEntry * cliqueEntry_
Entries for clique.
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.
Derived class to pick up probing info.
Definition: CglTreeInfo.hpp:86
void switchOffExpensive()
Switch off expensive cuts.
bool atOne(int i, unsigned int *array)
Definition: opbdp_solve.hpp:37
int findPseudoJohnAndEllisCover(int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
find a cover using a variation of the logic found in OSL (w/o SOS)
int * endFixStart_
End of fixes for a column.
Cut Generator Base Class.
int getMaxInKnapsack() const
get limit on number in knapsack
int liftCoverCut(double &b, int nRowElem, CoinPackedVector &cover, CoinPackedVector &remainder, CoinPackedVector &cut)
lift the cover inequality
int findJohnAndEllisCover(int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &fracCover, CoinPackedVector &atOnes, CoinPackedVector &remainder)
find a cover using the basic logic found in OSL (w/o SOS)
int createCliques(OsiSolverInterface &si, int minimumSize=2, int maximumSize=100, bool extendCliques=false)
Creates cliques for use by probing.
void switchOnExpensive()
Switch on expensive cuts.
int numberColumns_
Number of columns.
double epsilon_
epsilon
void CglKnapsackCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglKnapsackCover class.
double onetol_
1-epsilon
int numberCliques_
Number of cliques.
double epsilon2_
Tolerance to use for violation - bigger than epsilon_.
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)
deriveAKnapsack returns 1 if it is able to derive a (canonical) knapsack inequality in binary variabl...
int * cliqueStart_
Start of each clique.
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate knapsack cover cuts for the model of the solver interface, si.
int exactSolveKnapsack(int n, double c, double const *pp, double const *ww, double &z, int *x)
A C-style implementation of the Horowitz-Sahni exact solution procedure for solving knapsack problem...
Sparse Vector.
Knapsack Cover Cut Generator Class.
void setMaxInKnapsack(int value)
Set limit on number in knapsack.
int numRowsToCheck_
which rows to look at.
int findLPMostViolatedMinCover(int nCols, int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
Find the most violate minimum cover by solving the lp-relaxation of the most-violate-min-cover proble...
virtual CglCutGenerator * clone() const
Clone.
void seqLiftAndUncomplementAndAdd(int nCols, double *xstar, int *complement, int row, int nRowElem, double &b, CoinPackedVector &cover, CoinPackedVector &remainder, OsiCuts &cs)
sequence-dependent lift, uncomplement and add the resulting cut to the cut set