coin-Cgl
|
Knapsack Cover Cut Generator Class. More...
#include <CglKnapsackCover.hpp>
Classes | |
struct | cliqueType |
Clique type. More... | |
Public Member Functions | |
void | setTestedRowIndices (int num, const int *ind) |
A method to set which rows should be tested for knapsack covers. More... | |
Generate Cuts | |
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. More... | |
Constructors and destructors | |
CglKnapsackCover () | |
Default constructor. More... | |
CglKnapsackCover (const CglKnapsackCover &) | |
Copy constructor. More... | |
virtual CglCutGenerator * | clone () const |
Clone. More... | |
CglKnapsackCover & | operator= (const CglKnapsackCover &rhs) |
Assignment operator. More... | |
virtual | ~CglKnapsackCover () |
Destructor. More... | |
virtual std::string | generateCpp (FILE *fp) |
Create C++ lines to get to current state. More... | |
virtual void | refreshSolver (OsiSolverInterface *solver) |
This can be used to refresh any information. More... | |
Sets and gets | |
void | setMaxInKnapsack (int value) |
Set limit on number in knapsack. More... | |
int | getMaxInKnapsack () const |
get limit on number in knapsack More... | |
void | switchOffExpensive () |
Switch off expensive cuts. More... | |
void | switchOnExpensive () |
Switch on expensive cuts. More... | |
![]() | |
CglCutGenerator () | |
Default constructor. More... | |
CglCutGenerator (const CglCutGenerator &) | |
Copy constructor. More... | |
CglCutGenerator & | operator= (const CglCutGenerator &rhs) |
Assignment operator. More... | |
virtual | ~CglCutGenerator () |
Destructor. More... | |
int | getAggressiveness () const |
Get Aggressiveness - 0 = neutral, 100 is normal root node. More... | |
void | setAggressiveness (int value) |
Set Aggressiveness - 0 = neutral, 100 is normal root node. More... | |
virtual bool | mayGenerateRowCutsInTree () const |
Returns true if may generate Row cuts in tree (rather than root node). More... | |
virtual bool | needsOptimalBasis () const |
Return true if needs optimal basis to do cuts. More... | |
virtual int | maximumLengthOfCutInTree () const |
Return maximum length of cut in tree. More... | |
Private Member Functions | |
Private methods | |
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 variables of the form ax<=b from the rowIndex-th row in the model, returns 0 otherwise. More... | |
int | deriveAKnapsack (const OsiSolverInterface &si, OsiCuts &cs, CoinPackedVector &krow, double &b, int *complement, double *xstar, int rowIndex, const CoinPackedVectorBase &matrixRow) const |
deriveAKnapsack returns 1 if it is able to derive a (canonical) knapsack inequality in binary variables of the form ax<=b from the rowIndex-th row in the model, returns 0 otherwise. More... | |
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- violated cover problem and postprocess to ensure minimality More... | |
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 problem. More... | |
int | findGreedyCover (int row, CoinPackedVector &krow, double &b, double *xstar, CoinPackedVector &cover, CoinPackedVector &remainder) const |
find a minimum cover by a simple greedy approach More... | |
int | liftCoverCut (double &b, int nRowElem, CoinPackedVector &cover, CoinPackedVector &remainder, CoinPackedVector &cut) const |
lift the cover inequality More... | |
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 More... | |
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 More... | |
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 More... | |
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) More... | |
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) More... | |
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. More... | |
int | createCliques (OsiSolverInterface &si, int minimumSize=2, int maximumSize=100, bool extendCliques=false) |
Creates cliques for use by probing. More... | |
void | deleteCliques () |
Delete all clique information. More... | |
Private Attributes | |
Private member data | |
double | epsilon_ |
epsilon More... | |
double | epsilon2_ |
Tolerance to use for violation - bigger than epsilon_. More... | |
double | onetol_ |
1-epsilon More... | |
int | maxInKnapsack_ |
Maximum in knapsack. More... | |
int | numRowsToCheck_ |
which rows to look at. More... | |
int * | rowsToCheck_ |
epsilon More... | |
bool | expensiveCuts_ |
exactKnapsack can be expensive - this switches off some More... | |
const OsiSolverInterface * | solver_ |
Cliques **** TEMP so can reference from listing. More... | |
int | whichRow_ |
epsilon More... | |
int * | complement_ |
epsilon More... | |
double * | elements_ |
epsilon More... | |
int | numberCliques_ |
Number of cliques. More... | |
cliqueType * | cliqueType_ |
epsilon More... | |
int * | cliqueStart_ |
Start of each clique. More... | |
cliqueEntry * | cliqueEntry_ |
Entries for clique. More... | |
int * | oneFixStart_ |
Start of oneFixes cliques for a column in matrix or -1 if not in any clique. More... | |
int * | zeroFixStart_ |
Start of zeroFixes cliques for a column in matrix or -1 if not in any clique. More... | |
int * | endFixStart_ |
End of fixes for a column. More... | |
int * | whichClique_ |
Clique numbers for one or zero fixes. More... | |
int | numberColumns_ |
Number of columns. More... | |
Friends | |
void | CglKnapsackCoverUnitTest (const OsiSolverInterface *siP, const std::string mpdDir) |
A function that tests the methods in the CglKnapsackCover class. More... | |
Additional Inherited Members | |
![]() | |
int | aggressive_ |
Aggressiveness - 0 = neutral, 100 is normal root node. More... | |
Knapsack Cover Cut Generator Class.
Definition at line 12 of file CglKnapsackCover.hpp.
CglKnapsackCover::CglKnapsackCover | ( | ) |
Default constructor.
CglKnapsackCover::CglKnapsackCover | ( | const CglKnapsackCover & | ) |
Copy constructor.
|
virtual |
Destructor.
void CglKnapsackCover::setTestedRowIndices | ( | int | num, |
const int * | ind | ||
) |
A method to set which rows should be tested for knapsack covers.
|
virtual |
Generate knapsack cover cuts for the model of the solver interface, si.
Insert the generated cuts into OsiCut, cs.
Implements CglCutGenerator.
|
virtual |
Clone.
Implements CglCutGenerator.
CglKnapsackCover& CglKnapsackCover::operator= | ( | const CglKnapsackCover & | rhs) |
Assignment operator.
|
virtual |
Create C++ lines to get to current state.
Reimplemented from CglCutGenerator.
|
virtual |
This can be used to refresh any information.
Reimplemented from CglCutGenerator.
|
inline |
Set limit on number in knapsack.
Definition at line 59 of file CglKnapsackCover.hpp.
|
inline |
get limit on number in knapsack
Definition at line 62 of file CglKnapsackCover.hpp.
References maxInKnapsack_.
|
inline |
Switch off expensive cuts.
Definition at line 65 of file CglKnapsackCover.hpp.
References expensiveCuts_.
|
inline |
Switch on expensive cuts.
Definition at line 68 of file CglKnapsackCover.hpp.
References expensiveCuts_.
|
private |
deriveAKnapsack returns 1 if it is able to derive a (canonical) knapsack inequality in binary variables of the form ax<=b from the rowIndex-th row in the model, returns 0 otherwise.
|
private |
deriveAKnapsack returns 1 if it is able to derive a (canonical) knapsack inequality in binary variables of the form ax<=b from the rowIndex-th row in the model, returns 0 otherwise.
|
private |
Find a violated minimal cover from
a canonical form knapsack inequality by solving the -most- violated cover problem and postprocess to ensure minimality
|
private |
Find the most violate minimum cover by solving the lp-relaxation of the most-violate-min-cover problem.
|
private |
find a minimum cover by a simple greedy approach
|
private |
lift the cover inequality
|
private |
sequence-independent lift and uncomplement and add the resulting cut to the cut set
|
private |
sequence-dependent lift, uncomplement and add the resulting cut to the cut set
|
private |
sequence-dependent lift binary variables either up or down, uncomplement and add to the cut set
|
private |
find a cover using a variation of the logic found in OSL (w/o SOS)
|
private |
find a cover using the basic logic found in OSL (w/o SOS)
|
private |
A C-style implementation of the Horowitz-Sahni exact solution procedure for solving knapsack problem.
(ToDo: implement the more efficient dynamic programming approach)
(Reference: Martello and Toth, Knapsack Problems, Wiley, 1990, p30.)
|
private |
Creates cliques for use by probing.
Only cliques >= minimumSize and < maximumSize created Can also try and extend cliques as a result of probing (root node). Returns number of cliques found.
|
private |
Delete all clique information.
|
friend |
A function that tests the methods in the CglKnapsackCover class.
The only reason for it not to be a member method is that this way it doesn't have to be compiled into the library. And that's a gain, because the library should be compiled with optimization on, but this method should be compiled with debugging.
|
private |
epsilon
Definition at line 243 of file CglKnapsackCover.hpp.
|
private |
Tolerance to use for violation - bigger than epsilon_.
Definition at line 245 of file CglKnapsackCover.hpp.
|
private |
1-epsilon
Definition at line 247 of file CglKnapsackCover.hpp.
|
private |
Maximum in knapsack.
Definition at line 249 of file CglKnapsackCover.hpp.
Referenced by getMaxInKnapsack().
|
private |
which rows to look at.
If specified, only these rows will be considered for generating knapsack covers. Otherwise all rows will be tried
Definition at line 252 of file CglKnapsackCover.hpp.
|
private |
epsilon
Definition at line 253 of file CglKnapsackCover.hpp.
|
private |
exactKnapsack can be expensive - this switches off some
Definition at line 255 of file CglKnapsackCover.hpp.
Referenced by switchOffExpensive(), and switchOnExpensive().
|
mutableprivate |
Cliques **** TEMP so can reference from listing.
Definition at line 258 of file CglKnapsackCover.hpp.
|
mutableprivate |
epsilon
Definition at line 259 of file CglKnapsackCover.hpp.
|
mutableprivate |
epsilon
Definition at line 260 of file CglKnapsackCover.hpp.
|
mutableprivate |
epsilon
Definition at line 261 of file CglKnapsackCover.hpp.
|
private |
Number of cliques.
Definition at line 263 of file CglKnapsackCover.hpp.
|
private |
epsilon
Definition at line 268 of file CglKnapsackCover.hpp.
|
private |
Start of each clique.
Definition at line 270 of file CglKnapsackCover.hpp.
|
private |
Entries for clique.
Definition at line 272 of file CglKnapsackCover.hpp.
|
private |
Start of oneFixes cliques for a column in matrix or -1 if not in any clique.
Definition at line 275 of file CglKnapsackCover.hpp.
|
private |
Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.
Definition at line 278 of file CglKnapsackCover.hpp.
|
private |
End of fixes for a column.
Definition at line 280 of file CglKnapsackCover.hpp.
|
private |
Clique numbers for one or zero fixes.
Definition at line 282 of file CglKnapsackCover.hpp.
|
private |
Number of columns.
Definition at line 284 of file CglKnapsackCover.hpp.