Cbc  2.10.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Friends | List of all members
CglOddHole Class Reference

Odd Hole Cut Generator Class. More...

#include <CglOddHole.hpp>

+ Inheritance diagram for CglOddHole:
+ Collaboration diagram for CglOddHole:

Public Member Functions

Generate Cuts
virtual void generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
 Generate odd hole cuts for the model of the solver interface, si. More...
 
Create Row List
void createRowList (const OsiSolverInterface &si, const int *possible=NULL)
 Create a list of rows which might yield cuts this is to speed up process The possible parameter is a list to cut down search. More...
 
void createRowList (int numberRows, const int *whichRow)
 This version passes in a list - 1 marks possible. More...
 
Create Clique List
void createCliqueList (int numberCliques, const int *cliqueStart, const int *cliqueMember)
 Create a list of extra row cliques which may not be in matrix At present these are classical cliques. More...
 
Number Possibilities
int numberPossible ()
 Returns how many rows might give odd hole cuts. More...
 
Gets and Sets
double getMinimumViolation () const
 Minimum violation. More...
 
void setMinimumViolation (double value)
 
double getMinimumViolationPer () const
 Minimum violation per entry. More...
 
void setMinimumViolationPer (double value)
 
int getMaximumEntries () const
 Maximum number of entries in a cut. More...
 
void setMaximumEntries (int value)
 
Constructors and destructors
 CglOddHole ()
 Default constructor. More...
 
 CglOddHole (const CglOddHole &)
 Copy constructor. More...
 
virtual CglCutGeneratorclone () const
 Clone. More...
 
CglOddHoleoperator= (const CglOddHole &rhs)
 Assignment operator. More...
 
virtual ~CglOddHole ()
 Destructor. More...
 
virtual void refreshSolver (OsiSolverInterface *solver)
 This can be used to refresh any inforamtion. 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...
 
virtual std::string generateCpp (FILE *)
 Create C++ lines to set the generator in the current state. 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...
 
void setGlobalCuts (bool trueOrFalse)
 Set whether can do global cuts. More...
 
bool canDoGlobalCuts () const
 Say whether can do global cuts. 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
void generateCuts (const OsiRowCutDebugger *debugger, const CoinPackedMatrix &rowCopy, const double *solution, const double *dj, OsiCuts &cs, const int *suitableRow, const int *fixedColumn, const CglTreeInfo info, bool packed)
 Generate cuts from matrix copy and solution If packed true then <=1 rows, otherwise >=1 rows. More...
 

Private Attributes

Private member data
int * suitableRows_
 list of suitableRows More...
 
int * startClique_
 start of each clique More...
 
int * member_
 clique members More...
 
double epsilon_
 epsilon More...
 
double onetol_
 1-epsilon More...
 
double minimumViolation_
 Minimum violation. More...
 
double minimumViolationPer_
 Minimum violation per entry. More...
 
int maximumEntries_
 Maximum number of entries in a cut. More...
 
int numberRows_
 number of rows when suitability tested More...
 
int numberCliques_
 number of cliques More...
 

Friends

void CglOddHoleUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
 A function that tests the methods in the CglOddHole class. More...
 

Additional Inherited Members

- Public Attributes inherited from CglCutGenerator
int aggressive_
 Aggressiveness - 0 = neutral, 100 is normal root node. More...
 
bool canDoGlobalCuts_
 True if can do global cuts i.e. no general integers. More...
 

Detailed Description

Odd Hole Cut Generator Class.

Definition at line 14 of file CglOddHole.hpp.

Constructor & Destructor Documentation

CglOddHole::CglOddHole ( )

Default constructor.

CglOddHole::CglOddHole ( const CglOddHole )

Copy constructor.

virtual CglOddHole::~CglOddHole ( )
virtual

Destructor.

Member Function Documentation

virtual void CglOddHole::generateCuts ( const OsiSolverInterface si,
OsiCuts cs,
const CglTreeInfo  info = CglTreeInfo() 
)
virtual

Generate odd hole cuts for the model of the solver interface, si.

This looks at all rows of type sum x(i) <= 1 (or == 1) (x 0-1) and sees if there is an odd cycle cut. See Grotschel, Lovasz and Schrijver (1988) for method. This is then lifted by using the corresponding Chvatal cut i.e. Take all rows in cycle and add them together. RHS will be odd so weaken all odd coefficients so 1.0 goes to 0.0 etc - then constraint is sum even(j)*x(j) <= odd which can be replaced by sum (even(j)/2)*x(j) <= (odd-1.0)/2. A similar cut can be generated for sum x(i) >= 1.

Insert the generated cuts into OsiCut, cs.

This is only done for rows with unsatisfied 0-1 variables. If there are many of these it will be slow. Improvements would do a randomized subset and also speed up shortest path algorithm used.

Implements CglCutGenerator.

void CglOddHole::createRowList ( const OsiSolverInterface si,
const int *  possible = NULL 
)

Create a list of rows which might yield cuts this is to speed up process The possible parameter is a list to cut down search.

void CglOddHole::createRowList ( int  numberRows,
const int *  whichRow 
)

This version passes in a list - 1 marks possible.

void CglOddHole::createCliqueList ( int  numberCliques,
const int *  cliqueStart,
const int *  cliqueMember 
)

Create a list of extra row cliques which may not be in matrix At present these are classical cliques.

int CglOddHole::numberPossible ( )

Returns how many rows might give odd hole cuts.

double CglOddHole::getMinimumViolation ( ) const

Minimum violation.

void CglOddHole::setMinimumViolation ( double  value)
double CglOddHole::getMinimumViolationPer ( ) const

Minimum violation per entry.

void CglOddHole::setMinimumViolationPer ( double  value)
int CglOddHole::getMaximumEntries ( ) const

Maximum number of entries in a cut.

void CglOddHole::setMaximumEntries ( int  value)
virtual CglCutGenerator* CglOddHole::clone ( ) const
virtual

Clone.

Implements CglCutGenerator.

CglOddHole& CglOddHole::operator= ( const CglOddHole rhs)

Assignment operator.

virtual void CglOddHole::refreshSolver ( OsiSolverInterface solver)
virtual

This can be used to refresh any inforamtion.

Reimplemented from CglCutGenerator.

void CglOddHole::generateCuts ( const OsiRowCutDebugger debugger,
const CoinPackedMatrix rowCopy,
const double *  solution,
const double *  dj,
OsiCuts cs,
const int *  suitableRow,
const int *  fixedColumn,
const CglTreeInfo  info,
bool  packed 
)
private

Generate cuts from matrix copy and solution If packed true then <=1 rows, otherwise >=1 rows.

Friends And Related Function Documentation

void CglOddHoleUnitTest ( const OsiSolverInterface siP,
const std::string  mpdDir 
)
friend

A function that tests the methods in the CglOddHole 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

int* CglOddHole::suitableRows_
private

list of suitableRows

Definition at line 129 of file CglOddHole.hpp.

int* CglOddHole::startClique_
private

start of each clique

Definition at line 131 of file CglOddHole.hpp.

int* CglOddHole::member_
private

clique members

Definition at line 133 of file CglOddHole.hpp.

double CglOddHole::epsilon_
private

epsilon

Definition at line 135 of file CglOddHole.hpp.

double CglOddHole::onetol_
private

1-epsilon

Definition at line 137 of file CglOddHole.hpp.

double CglOddHole::minimumViolation_
private

Minimum violation.

Definition at line 139 of file CglOddHole.hpp.

double CglOddHole::minimumViolationPer_
private

Minimum violation per entry.

Definition at line 141 of file CglOddHole.hpp.

int CglOddHole::maximumEntries_
private

Maximum number of entries in a cut.

Definition at line 143 of file CglOddHole.hpp.

int CglOddHole::numberRows_
private

number of rows when suitability tested

Definition at line 145 of file CglOddHole.hpp.

int CglOddHole::numberCliques_
private

number of cliques

Definition at line 147 of file CglOddHole.hpp.


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