Cgl  trunk
Friends
CglOddHole Class Reference

Odd Hole Cut Generator Class. More...

#include <CglOddHole.hpp>

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

List of all members.

Public Member Functions

Generate Cuts
virtual void generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
 Generate odd hole cuts for the model of the solver interface, si.
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.
void createRowList (int numberRows, const int *whichRow)
 This version passes in a list - 1 marks possible.
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.
Number Possibilities
int numberPossible ()
 Returns how many rows might give odd hole cuts.
Gets and Sets
double getMinimumViolation () const
 Minimum violation.
void setMinimumViolation (double value)
double getMinimumViolationPer () const
 Minimum violation per entry.
void setMinimumViolationPer (double value)
int getMaximumEntries () const
 Maximum number of entries in a cut.
void setMaximumEntries (int value)
Constructors and destructors
 CglOddHole ()
 Default constructor.
 CglOddHole (const CglOddHole &)
 Copy constructor.
virtual CglCutGeneratorclone () const
 Clone.
CglOddHoleoperator= (const CglOddHole &rhs)
 Assignment operator.
virtual ~CglOddHole ()
 Destructor.
virtual void refreshSolver (OsiSolverInterface *solver)
 This can be used to refresh any inforamtion.

Friends

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

Detailed Description

Odd Hole Cut Generator Class.

Definition at line 14 of file CglOddHole.hpp.


Constructor & Destructor Documentation

Default constructor.

Copy constructor.

virtual CglOddHole::~CglOddHole ( ) [virtual]

Destructor.


Member Function Documentation

virtual void CglOddHole::generateCuts ( const OsiSolverInterface &  si,
OsiCuts &  cs,
const CglTreeInfo  info = CglTreeInfo() 
) const [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.

Returns how many rows might give odd hole cuts.

Minimum violation.

void CglOddHole::setMinimumViolation ( double  value)

Minimum violation per entry.

void CglOddHole::setMinimumViolationPer ( double  value)

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.


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.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines