Cgl  0.59.10
Friends | List of all members
CglRedSplit2 Class Reference

Reduce-and-Split Cut Generator Class; See method generateCuts(). More...

#include <CglRedSplit2.hpp>

+ Inheritance diagram for CglRedSplit2:
+ Collaboration diagram for CglRedSplit2:

Public Member Functions

generateCuts
virtual void generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
 Generate Reduce-and-Split Mixed Integer Gomory cuts for the model of the solver interface si. More...
 
virtual bool needsOptimalBasis () const
 Return true if needs optimal basis to do cuts (will return true) More...
 
int generateMultipliers (const OsiSolverInterface &si, int *lambda, int maxNumMultipliers, int *basicVariables=NULL, OsiCuts *cs=NULL)
 
int tiltLandPcut (const OsiSolverInterface *si, double *row, double rowRhs, int rownumber, const double *xbar, const int *newnonbasics, OsiRowCut *cs, int *lambda=NULL)
 
Public Methods
void setParam (const CglRedSplit2Param &source)
 
CglRedSplit2ParamgetParam ()
 
void print () const
 Print some of the data members; used for debugging. More...
 
void printOptTab (OsiSolverInterface *solver) const
 Print the current simplex tableau. More...
 
Constructors and destructors
 CglRedSplit2 ()
 Default constructor. More...
 
 CglRedSplit2 (const CglRedSplit2Param &RS_param)
 Constructor with specified parameters. More...
 
 CglRedSplit2 (const CglRedSplit2 &)
 Copy constructor. More...
 
virtual CglCutGeneratorclone () const
 Clone. More...
 
CglRedSplit2operator= (const CglRedSplit2 &rhs)
 Assignment operator. More...
 
virtual ~CglRedSplit2 ()
 Destructor. 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...
 
virtual void refreshSolver (OsiSolverInterface *)
 This can be used to refresh any information. 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 int maximumLengthOfCutInTree () const
 Return maximum length of cut in tree. More...
 

Friends

void CglRedSplit2UnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
 A function that tests some of the methods in the CglRedSplit2 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

Reduce-and-Split Cut Generator Class; See method generateCuts().

Based on the papers "Practical strategies for generating rank-1 split cuts in mixed-integer linear programming" by G. Cornuejols and G. Nannicini, published on Mathematical Programming Computation, and "Combining Lift-and-Project and Reduce-and-Split" by E. Balas, G. Cornuejols, T. Kis and G. Nannicini, published on INFORMS Journal on Computing. Part of this code is based on CglRedSplit by F. Margot.

Definition at line 31 of file CglRedSplit2.hpp.

Constructor & Destructor Documentation

◆ CglRedSplit2() [1/3]

CglRedSplit2::CglRedSplit2 ( )

Default constructor.

◆ CglRedSplit2() [2/3]

CglRedSplit2::CglRedSplit2 ( const CglRedSplit2Param RS_param)

Constructor with specified parameters.

◆ CglRedSplit2() [3/3]

CglRedSplit2::CglRedSplit2 ( const CglRedSplit2 )

Copy constructor.

◆ ~CglRedSplit2()

virtual CglRedSplit2::~CglRedSplit2 ( )
virtual

Destructor.

Member Function Documentation

◆ generateCuts()

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

Generate Reduce-and-Split Mixed Integer Gomory cuts for the model of the solver interface si.

Insert the generated cuts into OsiCuts cs.

This generator currently works only with the Lp solvers Clp or Cplex9.0 or higher. It requires access to the optimal tableau and optimal basis inverse and makes assumptions on the way slack variables are added by the solver. The Osi implementations for Clp and Cplex verify these assumptions.

When calling the generator, the solver interface si must contain an optimized problem and information related to the optimal basis must be available through the OsiSolverInterface methods (si->optimalBasisIsAvailable() must return 'true'). It is also essential that the integrality of structural variable i can be obtained using si->isInteger(i).

Reduce-and-Split cuts are a class of split cuts. We compute linear combinations of the rows of the simplex tableau, trying to reduce some of the coefficients on the nonbasic continuous columns. We have a large number of heuristics to choose which coefficients should be reduced, and by using which rows. The paper explains everything in detail.

Note that this generator can potentially generate a huge number of cuts, depending on how it is parametered. Default parameters should be good for most situations; if you want to go heavy on split cuts, use more row selection strategies or a different number of rows in the linear combinations. Again, look at the paper for details. If you want to generate a small number of cuts, default parameters are not the best choice.

A combination of Reduce-and-Split with Lift & Project is described in the paper "Combining Lift-and-Project and Reduce-and-Split". The Reduce-and-Split code for the implementation used in that paper is included here.

This generator does not generate the same cuts as CglRedSplit, therefore both generators can be used in conjunction.

Implements CglCutGenerator.

◆ needsOptimalBasis()

virtual bool CglRedSplit2::needsOptimalBasis ( ) const
virtual

Return true if needs optimal basis to do cuts (will return true)

Reimplemented from CglCutGenerator.

◆ generateMultipliers()

int CglRedSplit2::generateMultipliers ( const OsiSolverInterface &  si,
int *  lambda,
int  maxNumMultipliers,
int *  basicVariables = NULL,
OsiCuts *  cs = NULL 
)

◆ tiltLandPcut()

int CglRedSplit2::tiltLandPcut ( const OsiSolverInterface *  si,
double *  row,
double  rowRhs,
int  rownumber,
const double *  xbar,
const int *  newnonbasics,
OsiRowCut *  cs,
int *  lambda = NULL 
)

◆ setParam()

void CglRedSplit2::setParam ( const CglRedSplit2Param source)

◆ getParam()

CglRedSplit2Param& CglRedSplit2::getParam ( )
inline

Definition at line 132 of file CglRedSplit2.hpp.

◆ print()

void CglRedSplit2::print ( ) const

Print some of the data members; used for debugging.

◆ printOptTab()

void CglRedSplit2::printOptTab ( OsiSolverInterface *  solver) const

Print the current simplex tableau.

◆ clone()

virtual CglCutGenerator* CglRedSplit2::clone ( ) const
virtual

Clone.

Implements CglCutGenerator.

◆ operator=()

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

Assignment operator.

Friends And Related Function Documentation

◆ CglRedSplit2UnitTest

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

A function that tests some of the methods in the CglRedSplit2 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: