Cgl 0.60.9
Loading...
Searching...
No Matches
CglKnapsackCover.hpp
Go to the documentation of this file.
1// $Id$
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
19public:
21 void setTestedRowIndices(int num, const int* ind);
22
25
28 virtual void generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
29 const CglTreeInfo info = CglTreeInfo());
31
34
36
39 const CglKnapsackCover &);
40
42 virtual CglCutGenerator * clone() const;
43
47 const CglKnapsackCover& rhs);
48
50 virtual
53 virtual std::string generateCpp( FILE * fp);
55 virtual void refreshSolver(OsiSolverInterface * solver);
57
58
61
62 inline void setMaxInKnapsack(int value)
63 { if (value>0) maxInKnapsack_ = value;}
64
65 inline int getMaxInKnapsack() const
66 {return maxInKnapsack_;}
67
68 inline void switchOffExpensive()
69 { expensiveCuts_=false;}
70
71 inline void switchOnExpensive()
72 { expensiveCuts_=true;}
73private:
74
75 // Private member methods
76
77
80
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
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
139 int row,
140 CoinPackedVector & krow,
141 double & b,
142 double * xstar,
143 CoinPackedVector & cover,
144 CoinPackedVector & remainder
145 );
146
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
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);
231public:
237 int createCliques( OsiSolverInterface & si,
238 int minimumSize=2, int maximumSize=100, bool extendCliques=false);
239private:
243
244 // Private member data
245
248
249 double epsilon_;
251 double epsilon2_;
253 double onetol_;
264 const OsiSolverInterface * solver_;
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//#############################################################################
307void CglKnapsackCoverUnitTest(const OsiSolverInterface * siP,
308 const std::string mpdDir );
309
310#endif
void CglKnapsackCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglKnapsackCover class.
CglCutGenerator()
Default constructor.
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)
void deleteCliques()
Delete all clique information.
void setMaxInKnapsack(int value)
Set limit on number in knapsack.
const OsiSolverInterface * solver_
Cliques **** TEMP so can reference from listing.
int maxInKnapsack_
Maximum in knapsack.
virtual ~CglKnapsackCover()
Destructor.
void setTestedRowIndices(int num, const int *ind)
A method to set which rows should be tested for knapsack covers.
int numRowsToCheck_
which rows to look at.
int * whichClique_
Clique numbers for one or zero fixes.
CglKnapsackCover & operator=(const CglKnapsackCover &rhs)
Assignment operator.
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...
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
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- violate...
bool expensiveCuts_
exactKnapsack can be expensive - this switches off some
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.
int * zeroFixStart_
Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.
int createCliques(OsiSolverInterface &si, int minimumSize=2, int maximumSize=100, bool extendCliques=false)
Creates cliques for use by probing.
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)
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any information.
int numberColumns_
Number of columns.
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...
CglKnapsackCover(const CglKnapsackCover &)
Copy constructor.
CglKnapsackCover()
Default constructor.
int * cliqueStart_
Start of each clique.
int deriveAKnapsack(const OsiSolverInterface &si, OsiCuts &cs, CoinPackedVector &krow, double &b, int *complement, double *xstar, int rowIndex, const CoinPackedVectorBase &matrixRow)
int numberCliques_
Number of cliques.
double onetol_
1-epsilon
int findGreedyCover(int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
find a minimum cover by a simple greedy approach
int getMaxInKnapsack() const
get limit on number in knapsack
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
CliqueEntry * cliqueEntry_
Entries for clique.
int liftCoverCut(double &b, int nRowElem, CoinPackedVector &cover, CoinPackedVector &remainder, CoinPackedVector &cut)
lift the cover inequality
void switchOnExpensive()
Switch on expensive cuts.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
double epsilon2_
Tolerance to use for violation - bigger than epsilon_.
int * endFixStart_
End of fixes for a column.
friend void CglKnapsackCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglKnapsackCover class.
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 switchOffExpensive()
Switch off expensive cuts.
int * oneFixStart_
Start of oneFixes cliques for a column in matrix or -1 if not in any clique.
virtual CglCutGenerator * clone() const
Clone.
int gubifyCut(CoinPackedVector &cut)
For testing gub stuff.
Information about where the cut generator is invoked from.
Derived class to pick up probing info.