Cgl 0.60.2

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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
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::refreshSolver
virtual void refreshSolver(OsiSolverInterface *solver)
This can be used to refresh any information.
CglKnapsackCover::zeroFixStart_
int * zeroFixStart_
Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.
Definition: CglKnapsackCover.hpp:284
CglKnapsackCover::generateCpp
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
CglKnapsackCover::oneFixStart_
int * oneFixStart_
Start of oneFixes cliques for a column in matrix or -1 if not in any clique.
Definition: CglKnapsackCover.hpp:281
CglKnapsackCover::whichClique_
int * whichClique_
Clique numbers for one or zero fixes.
Definition: CglKnapsackCover.hpp:288
CglKnapsackCover::elements_
double * elements_
Definition: CglKnapsackCover.hpp:267
CglKnapsackCover::deleteCliques
void deleteCliques()
Delete all clique information.
CglKnapsackCover::liftUpDownAndUncomplementAndAdd
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 ...
CglKnapsackCover::setTestedRowIndices
void setTestedRowIndices(int num, const int *ind)
A method to set which rows should be tested for knapsack covers.
CglKnapsackCover::solver_
const OsiSolverInterface * solver_
Cliques **** TEMP so can reference from listing.
Definition: CglKnapsackCover.hpp:264
CglKnapsackCover::rowsToCheck_
int * rowsToCheck_
Definition: CglKnapsackCover.hpp:259
CglCutGenerator.hpp
CglTreeInfo
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
OsiCuts
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
CglKnapsackCover::liftAndUncomplementAndAdd
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 ...
CglKnapsackCover::cliqueType_
CliqueType * cliqueType_
Definition: CglKnapsackCover.hpp:274
CglKnapsackCover::CglKnapsackCover
CglKnapsackCover()
Default constructor.
CglKnapsackCover::expensiveCuts_
bool expensiveCuts_
exactKnapsack can be expensive - this switches off some
Definition: CglKnapsackCover.hpp:261
CglKnapsackCover::findGreedyCover
int findGreedyCover(int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder)
find a minimum cover by a simple greedy approach
CglKnapsackCover::~CglKnapsackCover
virtual ~CglKnapsackCover()
Destructor.
CglKnapsackCover::maxInKnapsack_
int maxInKnapsack_
Maximum in knapsack.
Definition: CglKnapsackCover.hpp:255
OsiSolverInterface
Abstract Base Class for describing an interface to a solver.
Definition: OsiSolverInterface.hpp:61
CglKnapsackCover::gubifyCut
int gubifyCut(CoinPackedVector &cut)
For testing gub stuff.
CglKnapsackCover::findExactMostViolatedMinCover
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...
CoinPackedVectorBase
Abstract base class for various sparse vectors.
Definition: CoinPackedVectorBase.hpp:23
CglKnapsackCover::cliqueEntry_
CliqueEntry * cliqueEntry_
Entries for clique.
Definition: CglKnapsackCover.hpp:278
CglKnapsackCover::operator=
CglKnapsackCover & operator=(const CglKnapsackCover &rhs)
Assignment operator.
CglKnapsackCover::CglKnapsackCoverUnitTest
friend void CglKnapsackCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglKnapsackCover class.
CglKnapsackCover::complement_
int * complement_
Definition: CglKnapsackCover.hpp:266
CliqueEntry
Derived class to pick up probing info.
Definition: CglTreeInfo.hpp:86
CglKnapsackCover::switchOffExpensive
void switchOffExpensive()
Switch off expensive cuts.
Definition: CglKnapsackCover.hpp:68
CglTreeInfo.hpp
atOne
bool atOne(int i, unsigned int *array)
Definition: opbdp_solve.hpp:37
CglKnapsackCover::findPseudoJohnAndEllisCover
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)
CglKnapsackCover::endFixStart_
int * endFixStart_
End of fixes for a column.
Definition: CglKnapsackCover.hpp:286
CglCutGenerator
Cut Generator Base Class.
Definition: CglCutGenerator.hpp:23
CglKnapsackCover::whichRow_
int whichRow_
Definition: CglKnapsackCover.hpp:265
CglKnapsackCover::getMaxInKnapsack
int getMaxInKnapsack() const
get limit on number in knapsack
Definition: CglKnapsackCover.hpp:65
CglKnapsackCover::liftCoverCut
int liftCoverCut(double &b, int nRowElem, CoinPackedVector &cover, CoinPackedVector &remainder, CoinPackedVector &cut)
lift the cover inequality
CglKnapsackCover::findJohnAndEllisCover
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)
cut
Definition: Cgl012cut.hpp:153
CglKnapsackCover::CliqueType
Clique type.
Definition: CglKnapsackCover.hpp:271
CglKnapsackCover::createCliques
int createCliques(OsiSolverInterface &si, int minimumSize=2, int maximumSize=100, bool extendCliques=false)
Creates cliques for use by probing.
CglKnapsackCover::switchOnExpensive
void switchOnExpensive()
Switch on expensive cuts.
Definition: CglKnapsackCover.hpp:71
CglKnapsackCover::numberColumns_
int numberColumns_
Number of columns.
Definition: CglKnapsackCover.hpp:290
CglKnapsackCover::epsilon_
double epsilon_
epsilon
Definition: CglKnapsackCover.hpp:249
CglKnapsackCoverUnitTest
void CglKnapsackCoverUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglKnapsackCover class.
CglKnapsackCover::onetol_
double onetol_
1-epsilon
Definition: CglKnapsackCover.hpp:253
CglKnapsackCover::numberCliques_
int numberCliques_
Number of cliques.
Definition: CglKnapsackCover.hpp:269
CglKnapsackCover::epsilon2_
double epsilon2_
Tolerance to use for violation - bigger than epsilon_.
Definition: CglKnapsackCover.hpp:251
CglKnapsackCover::deriveAKnapsack
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...
CglKnapsackCover::cliqueStart_
int * cliqueStart_
Start of each clique.
Definition: CglKnapsackCover.hpp:276
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::exactSolveKnapsack
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...
CoinPackedVector
Sparse Vector.
Definition: CoinPackedVector.hpp:123
CglKnapsackCover
Knapsack Cover Cut Generator Class.
Definition: CglKnapsackCover.hpp:15
CglKnapsackCover::setMaxInKnapsack
void setMaxInKnapsack(int value)
Set limit on number in knapsack.
Definition: CglKnapsackCover.hpp:62
CglKnapsackCover::numRowsToCheck_
int numRowsToCheck_
which rows to look at.
Definition: CglKnapsackCover.hpp:258
CglKnapsackCover::findLPMostViolatedMinCover
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::clone
virtual CglCutGenerator * clone() const
Clone.
CglKnapsackCover::seqLiftAndUncomplementAndAdd
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