- Main Page
- Namespaces
- Classes
- Files
- Directories

- Search for |

- Alphabetical List
- Class List
- Class Hierarchy
- Class Members

# CglKnapsackCover Class Reference

Knapsack Cover Cut Generator Class. More...

`#include <CglKnapsackCover.hpp>`

Inheritance diagram for CglKnapsackCover:

[legend]
Collaboration diagram for CglKnapsackCover:

[legend]
List of all members.

## Public Member Functions
void | setTestedRowIndices (int num, const int *ind)
| A method to set which rows should be tested for knapsack covers.
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.
Constructors and destructors
| CglKnapsackCover ()
| Default constructor.
| CglKnapsackCover (const CglKnapsackCover &)
| Copy constructor.
virtual CglCutGenerator * | clone () const
| Clone.
CglKnapsackCover & | operator= (const CglKnapsackCover &rhs)
| Assignment operator.
virtual | ~CglKnapsackCover ()
| Destructor.
virtual std::string | generateCpp (FILE *fp)
| Create C++ lines to get to current state.
virtual void | refreshSolver (OsiSolverInterface *solver)
| This can be used to refresh any information.
Sets and gets
void | setMaxInKnapsack (int value)
| Set limit on number in knapsack.
int | getMaxInKnapsack () const
| get limit on number in knapsack
void | switchOffExpensive ()
| Switch off expensive cuts.
void | switchOnExpensive ()
| Switch on expensive cuts.
## 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.
int | deriveAKnapsack (const OsiSolverInterface &si, OsiCuts &cs, CoinPackedVector &krow, double &b, int *complement, double *xstar, int rowIndex, const CoinPackedVectorBase &matrixRow) const
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.
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.
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 | liftCoverCut (double &b, int nRowElem, CoinPackedVector &cover, CoinPackedVector &remainder, CoinPackedVector &cut) const
| lift the cover inequality
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
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
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
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)
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)
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 | createCliques (OsiSolverInterface &si, int minimumSize=2, int maximumSize=100, bool extendCliques=false)
| Creates cliques for use by probing.
void | deleteCliques ()
| Delete all clique information.
## Private Attributes
Private member data
double | epsilon_
| epsilon
double | epsilon2_
| Tolerance to use for violation - bigger than epsilon_.
double | onetol_
| 1-epsilon
int | maxInKnapsack_
| Maximum in knapsack.
int | numRowsToCheck_
| which rows to look at.
int * | rowsToCheck_
bool | expensiveCuts_
| exactKnapsack can be expensive - this switches off some
const OsiSolverInterface * | solver_
| Cliques TEMP so can reference from listing.
int | whichRow_
int * | complement_
double * | elements_
int | numberCliques_
| Number of cliques.
cliqueType * | cliqueType_
int * | cliqueStart_
| Start of each clique.
cliqueEntry * | cliqueEntry_
| Entries for clique.
int * | oneFixStart_
| Start of oneFixes cliques for a column in matrix or -1 if not in any clique.
int * | zeroFixStart_
| Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.
int * | endFixStart_
| End of fixes for a column.
int * | whichClique_
| Clique numbers for one or zero fixes.
int | numberColumns_
| Number of columns.
## Friends
void | CglKnapsackCoverUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
| A function that tests the methods in the CglKnapsackCover class.
## Classes
struct | cliqueType
| Clique type. More...

## Detailed Description

Knapsack Cover Cut Generator Class.

Definition at line 15 of file CglKnapsackCover.hpp.

## Constructor & Destructor Documentation

CglKnapsackCover::CglKnapsackCover | ( |  | ) |

Default constructor.

CglKnapsackCover::CglKnapsackCover | ( | const CglKnapsackCover & |  | ) |

Copy constructor.

virtual CglKnapsackCover::~CglKnapsackCover | ( |  | ) | `[virtual]`

Destructor.

## Member Function Documentation

void CglKnapsackCover::setTestedRowIndices | ( | int | num,
|  | const int * | ind |
| ) |  |  |

A method to set which rows should be tested for knapsack covers.

virtual void CglKnapsackCover::generateCuts | ( | const OsiSolverInterface & | si,
|  | OsiCuts & | cs,
|  | const CglTreeInfo | info = `CglTreeInfo()` |
| ) |  |  | const`[virtual]`

Generate knapsack cover cuts for the model of the solver interface, si.

Insert the generated cuts into OsiCut, cs.

Implements CglCutGenerator.

virtual CglCutGenerator* CglKnapsackCover::clone | ( |  | ) | const`[virtual]`

Clone.

Implements CglCutGenerator.

CglKnapsackCover& CglKnapsackCover::operator= | ( | const CglKnapsackCover & | rhs | ) |

Assignment operator.

virtual std::string CglKnapsackCover::generateCpp | ( | FILE * | fp | ) | `[virtual]`

Create C++ lines to get to current state.

Reimplemented from CglCutGenerator.

virtual void CglKnapsackCover::refreshSolver | ( | OsiSolverInterface * | solver | ) | `[virtual]`

This can be used to refresh any information.

Reimplemented from CglCutGenerator.

void CglKnapsackCover::setMaxInKnapsack | ( | int | value | ) | `[inline]`

Set limit on number in knapsack.

Definition at line 62 of file CglKnapsackCover.hpp.

int CglKnapsackCover::getMaxInKnapsack | ( |  | ) | const`[inline]`

get limit on number in knapsack

Definition at line 65 of file CglKnapsackCover.hpp.

void CglKnapsackCover::switchOffExpensive | ( |  | ) | `[inline]`

Switch off expensive cuts.

Definition at line 68 of file CglKnapsackCover.hpp.

void CglKnapsackCover::switchOnExpensive | ( |  | ) | `[inline]`

Switch on expensive cuts.

Definition at line 71 of file CglKnapsackCover.hpp.

int CglKnapsackCover::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`[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.

int CglKnapsackCover::deriveAKnapsack | ( | const OsiSolverInterface & | si,
|  | OsiCuts & | cs,
|  | CoinPackedVector & | krow,
|  | double & | b,
|  | int * | complement,
|  | double * | xstar,
|  | int | rowIndex,
|  | const CoinPackedVectorBase & | matrixRow |
| ) |  |  | const`[private]`

int CglKnapsackCover::findExactMostViolatedMinCover | ( | int | nCols,
|  | int | row,
|  | CoinPackedVector & | krow,
|  | double | b,
|  | double * | xstar,
|  | CoinPackedVector & | cover,
|  | CoinPackedVector & | remainder |
| ) |  |  | const`[private]`

Find a violated minimal cover from a canonical form knapsack inequality by solving the -most- violated cover problem and postprocess to ensure minimality.

int CglKnapsackCover::findLPMostViolatedMinCover | ( | int | nCols,
|  | int | row,
|  | CoinPackedVector & | krow,
|  | double & | b,
|  | double * | xstar,
|  | CoinPackedVector & | cover,
|  | CoinPackedVector & | remainder |
| ) |  |  | const`[private]`

Find the most violate minimum cover by solving the lp-relaxation of the most-violate-min-cover problem.

int CglKnapsackCover::findGreedyCover | ( | int | row,
|  | CoinPackedVector & | krow,
|  | double & | b,
|  | double * | xstar,
|  | CoinPackedVector & | cover,
|  | CoinPackedVector & | remainder |
| ) |  |  | const`[private]`

find a minimum cover by a simple greedy approach

int CglKnapsackCover::liftCoverCut | ( | double & | b,
|  | int | nRowElem,
|  | CoinPackedVector & | cover,
|  | CoinPackedVector & | remainder,
|  | CoinPackedVector & | cut |
| ) |  |  | const`[private]`

lift the cover inequality

int CglKnapsackCover::liftAndUncomplementAndAdd | ( | double | rowub,
|  | CoinPackedVector & | krow,
|  | double & | b,
|  | int * | complement,
|  | int | row,
|  | CoinPackedVector & | cover,
|  | CoinPackedVector & | remainder,
|  | OsiCuts & | cs |
| ) |  |  | const`[private]`

sequence-independent lift and uncomplement and add the resulting cut to the cut set

void CglKnapsackCover::seqLiftAndUncomplementAndAdd | ( | int | nCols,
|  | double * | xstar,
|  | int * | complement,
|  | int | row,
|  | int | nRowElem,
|  | double & | b,
|  | CoinPackedVector & | cover,
|  | CoinPackedVector & | remainder,
|  | OsiCuts & | cs |
| ) |  |  | const`[private]`

sequence-dependent lift, uncomplement and add the resulting cut to the cut set

void CglKnapsackCover::liftUpDownAndUncomplementAndAdd | ( | int | nCols,
|  | double * | xstar,
|  | int * | complement,
|  | int | row,
|  | int | nRowElem,
|  | double & | b,
|  | CoinPackedVector & | fracCover,
|  | CoinPackedVector & | atOne,
|  | CoinPackedVector & | remainder,
|  | OsiCuts & | cs |
| ) |  |  | const`[private]`

sequence-dependent lift binary variables either up or down, uncomplement and add to the cut set

int CglKnapsackCover::findPseudoJohnAndEllisCover | ( | int | row,
|  | CoinPackedVector & | krow,
|  | double & | b,
|  | double * | xstar,
|  | CoinPackedVector & | cover,
|  | CoinPackedVector & | remainder |
| ) |  |  | const`[private]`

find a cover using a variation of the logic found in OSL (w/o SOS)

int CglKnapsackCover::findJohnAndEllisCover | ( | int | row,
|  | CoinPackedVector & | krow,
|  | double & | b,
|  | double * | xstar,
|  | CoinPackedVector & | fracCover,
|  | CoinPackedVector & | atOnes,
|  | CoinPackedVector & | remainder |
| ) |  |  | const`[private]`

find a cover using the basic logic found in OSL (w/o SOS)

int CglKnapsackCover::exactSolveKnapsack | ( | int | n,
|  | double | c,
|  | double const * | pp,
|  | double const * | ww,
|  | double & | z,
|  | int * | x |
| ) |  |  | const`[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.)

int CglKnapsackCover::createCliques | ( | OsiSolverInterface & | si,
|  | int | minimumSize = `2`,
|  | int | maximumSize = `100`,
|  | bool | extendCliques = `false` |
| ) |  |  | `[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.

void CglKnapsackCover::deleteCliques | ( |  | ) | `[private]`

Delete all clique information.

## Friends And Related Function Documentation

void CglKnapsackCoverUnitTest | ( | const OsiSolverInterface * | siP,
|  | const std::string | mpdDir |
| ) |  |  | `[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.

## Member Data Documentation

double CglKnapsackCover::epsilon_`[private]`

epsilon

Definition at line 246 of file CglKnapsackCover.hpp.

double CglKnapsackCover::epsilon2_`[private]`

Tolerance to use for violation - bigger than epsilon_.

Definition at line 248 of file CglKnapsackCover.hpp.

double CglKnapsackCover::onetol_`[private]`

1-epsilon

Definition at line 250 of file CglKnapsackCover.hpp.

int CglKnapsackCover::maxInKnapsack_`[private]`

Maximum in knapsack.

Definition at line 252 of file CglKnapsackCover.hpp.

int CglKnapsackCover::numRowsToCheck_`[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 255 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::rowsToCheck_`[private]`

Definition at line 256 of file CglKnapsackCover.hpp.

bool CglKnapsackCover::expensiveCuts_`[private]`

exactKnapsack can be expensive - this switches off some

Definition at line 258 of file CglKnapsackCover.hpp.

const OsiSolverInterface* CglKnapsackCover::solver_`[mutable, private]`

Cliques TEMP so can reference from listing.

Definition at line 261 of file CglKnapsackCover.hpp.

int CglKnapsackCover::whichRow_`[mutable, private]`

Definition at line 262 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::complement_`[mutable, private]`

Definition at line 263 of file CglKnapsackCover.hpp.

double* CglKnapsackCover::elements_`[mutable, private]`

Definition at line 264 of file CglKnapsackCover.hpp.

int CglKnapsackCover::numberCliques_`[private]`

Number of cliques.

Definition at line 266 of file CglKnapsackCover.hpp.

cliqueType* CglKnapsackCover::cliqueType_`[private]`

Definition at line 271 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::cliqueStart_`[private]`

Start of each clique.

Definition at line 273 of file CglKnapsackCover.hpp.

cliqueEntry* CglKnapsackCover::cliqueEntry_`[private]`

Entries for clique.

Definition at line 275 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::oneFixStart_`[private]`

Start of oneFixes cliques for a column in matrix or -1 if not in any clique.

Definition at line 278 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::zeroFixStart_`[private]`

Start of zeroFixes cliques for a column in matrix or -1 if not in any clique.

Definition at line 281 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::endFixStart_`[private]`

End of fixes for a column.

Definition at line 283 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::whichClique_`[private]`

Clique numbers for one or zero fixes.

Definition at line 285 of file CglKnapsackCover.hpp.

int CglKnapsackCover::numberColumns_`[private]`

Number of columns.

Definition at line 287 of file CglKnapsackCover.hpp.

The documentation for this class was generated from the following file:

- /home/coin/SVN-release/Cgl-0.57.1/Cgl/src/CglKnapsackCover/CglKnapsackCover.hpp