Cgl
0.59.9
|
Reduce-and-Split Cut Generator Class; See method generateCuts(). More...
#include <CglRedSplit2.hpp>
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) |
CglRedSplit2Param & | getParam () |
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 CglCutGenerator * | clone () const |
Clone. More... | |
CglRedSplit2 & | operator= (const CglRedSplit2 &rhs) |
Assignment operator. More... | |
virtual | ~CglRedSplit2 () |
Destructor. More... | |
![]() | |
CglCutGenerator () | |
Default constructor. More... | |
CglCutGenerator (const CglCutGenerator &) | |
Copy constructor. More... | |
CglCutGenerator & | operator= (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 | |
![]() | |
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... | |
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.
CglRedSplit2::CglRedSplit2 | ( | ) |
Default constructor.
CglRedSplit2::CglRedSplit2 | ( | const CglRedSplit2Param & | RS_param | ) |
Constructor with specified parameters.
CglRedSplit2::CglRedSplit2 | ( | const CglRedSplit2 & | ) |
Copy constructor.
|
virtual |
Destructor.
|
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.
|
virtual |
Return true if needs optimal basis to do cuts (will return true)
Reimplemented from CglCutGenerator.
int CglRedSplit2::generateMultipliers | ( | const OsiSolverInterface & | si, |
int * | lambda, | ||
int | maxNumMultipliers, | ||
int * | basicVariables = NULL , |
||
OsiCuts * | cs = NULL |
||
) |
int CglRedSplit2::tiltLandPcut | ( | const OsiSolverInterface * | si, |
double * | row, | ||
double | rowRhs, | ||
int | rownumber, | ||
const double * | xbar, | ||
const int * | newnonbasics, | ||
OsiRowCut * | cs, | ||
int * | lambda = NULL |
||
) |
void CglRedSplit2::setParam | ( | const CglRedSplit2Param & | source | ) |
|
inline |
Definition at line 132 of file CglRedSplit2.hpp.
void CglRedSplit2::print | ( | ) | const |
Print some of the data members; used for debugging.
void CglRedSplit2::printOptTab | ( | OsiSolverInterface * | solver | ) | const |
Print the current simplex tableau.
|
virtual |
Clone.
Implements CglCutGenerator.
CglRedSplit2& CglRedSplit2::operator= | ( | const CglRedSplit2 & | rhs | ) |
Assignment operator.
|
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.