coin-Cgl
Classes | Public Member Functions | Friends | List of all members
CglKnapsackCover Class Reference

Knapsack Cover Cut Generator Class. More...

#include <CglKnapsackCover.hpp>

Inheritance diagram for CglKnapsackCover:
Inheritance graph
[legend]
Collaboration diagram for CglKnapsackCover:
Collaboration graph
[legend]

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 CglCutGeneratorclone () const
 Clone. More...
 
CglKnapsackCoveroperator= (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...
 
- Public Member Functions inherited from CglCutGenerator
 CglCutGenerator ()
 Default constructor. More...
 
 CglCutGenerator (const CglCutGenerator &)
 Copy constructor. More...
 
CglCutGeneratoroperator= (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...
 
cliqueTypecliqueType_
 epsilon More...
 
int * cliqueStart_
 Start of each clique. More...
 
cliqueEntrycliqueEntry_
 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

- Public Attributes inherited from CglCutGenerator
int aggressive_
 Aggressiveness - 0 = neutral, 100 is normal root node. More...
 

Detailed Description

Knapsack Cover Cut Generator Class.

Definition at line 12 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 59 of file CglKnapsackCover.hpp.

int CglKnapsackCover::getMaxInKnapsack ( ) const
inline

get limit on number in knapsack

Definition at line 62 of file CglKnapsackCover.hpp.

References maxInKnapsack_.

void CglKnapsackCover::switchOffExpensive ( )
inline

Switch off expensive cuts.

Definition at line 65 of file CglKnapsackCover.hpp.

References expensiveCuts_.

void CglKnapsackCover::switchOnExpensive ( )
inline

Switch on expensive cuts.

Definition at line 68 of file CglKnapsackCover.hpp.

References expensiveCuts_.

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

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::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 243 of file CglKnapsackCover.hpp.

double CglKnapsackCover::epsilon2_
private

Tolerance to use for violation - bigger than epsilon_.

Definition at line 245 of file CglKnapsackCover.hpp.

double CglKnapsackCover::onetol_
private

1-epsilon

Definition at line 247 of file CglKnapsackCover.hpp.

int CglKnapsackCover::maxInKnapsack_
private

Maximum in knapsack.

Definition at line 249 of file CglKnapsackCover.hpp.

Referenced by getMaxInKnapsack().

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 252 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::rowsToCheck_
private

epsilon

Definition at line 253 of file CglKnapsackCover.hpp.

bool CglKnapsackCover::expensiveCuts_
private

exactKnapsack can be expensive - this switches off some

Definition at line 255 of file CglKnapsackCover.hpp.

Referenced by switchOffExpensive(), and switchOnExpensive().

const OsiSolverInterface* CglKnapsackCover::solver_
mutableprivate

Cliques **** TEMP so can reference from listing.

Definition at line 258 of file CglKnapsackCover.hpp.

int CglKnapsackCover::whichRow_
mutableprivate

epsilon

Definition at line 259 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::complement_
mutableprivate

epsilon

Definition at line 260 of file CglKnapsackCover.hpp.

double* CglKnapsackCover::elements_
mutableprivate

epsilon

Definition at line 261 of file CglKnapsackCover.hpp.

int CglKnapsackCover::numberCliques_
private

Number of cliques.

Definition at line 263 of file CglKnapsackCover.hpp.

cliqueType* CglKnapsackCover::cliqueType_
private

epsilon

Definition at line 268 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::cliqueStart_
private

Start of each clique.

Definition at line 270 of file CglKnapsackCover.hpp.

cliqueEntry* CglKnapsackCover::cliqueEntry_
private

Entries for clique.

Definition at line 272 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 275 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 278 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::endFixStart_
private

End of fixes for a column.

Definition at line 280 of file CglKnapsackCover.hpp.

int* CglKnapsackCover::whichClique_
private

Clique numbers for one or zero fixes.

Definition at line 282 of file CglKnapsackCover.hpp.

int CglKnapsackCover::numberColumns_
private

Number of columns.

Definition at line 284 of file CglKnapsackCover.hpp.


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