#include <CglRedSplit.hpp>
Inheritance diagram for CglRedSplit:
Public Member Functions | |
Generate Cuts | |
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. | |
virtual void | generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const |
For compatibility with CglCutGenerator (const method). | |
virtual bool | needsOptimalBasis () const |
Return true if needs optimal basis to do cuts (will return true). | |
Parameters | |
void | setLimit (int limit) |
Set limit, the maximum number of non zero coefficients in generated cut; Default: 50. | |
int | getLimit () const |
Get value of limit. | |
void | setAway (double value) |
Set away, the minimum distance from being integer used for selecting rows for cut generation; all rows whose pivot variable should be integer but is more than away from integrality will be selected; Default: 0.05. | |
double | getAway () const |
Get value of away. | |
void | setLUB (double value) |
Set the value of LUB, value considered large for the absolute value of a lower or upper bound on a variable; Default: 1000. | |
double | getLUB () const |
Get the value of LUB. | |
void | setEPS (double value) |
Set the value of EPS, epsilon for double computations; Default: 1e-7. | |
double | getEPS () const |
Get the value of EPS. | |
void | setEPS_COEFF (double value) |
Set the value of EPS_COEFF, epsilon for values of coefficients; Default: 1e-8. | |
double | getEPS_COEFF () const |
Get the value of EPS_COEFF. | |
void | setEPS_COEFF_LUB (double value) |
Set the value of EPS_COEFF_LUB, epsilon for values of coefficients for variables with absolute value of lower or upper bound larger than LUB; Default: 1e-13. | |
double | getEPS_COEFF_LUB () const |
Get the value of EPS_COEFF_LUB. | |
void | setEPS_RELAX (double value) |
Set the value of EPS_RELAX, value used for relaxing the right hand side of each generated cut; Default: 1e-8. | |
double | getEPS_RELAX () const |
Get the value of EPS_RELAX. | |
void | setNormIsZero (double value) |
Set the value of normIsZero, the threshold for considering a norm to be 0; Default: 1e-5. | |
double | getNormIsZero () const |
Get the value of normIsZero. | |
void | setMinReduc (double value) |
Set the value of minReduc, threshold for relative norm improvement for performing a reduction; Default: 0.05. | |
double | getMinReduc () const |
Get the value of minReduc. | |
void | setMaxTab (double value) |
Set the maximum allowed value for (mTab * mTab * max(mTab, nTab)) where mTab is the number of rows used in the combinations and nTab is the number of continuous non basic variables. | |
double | getMaxTab () const |
Get the value of maxTab. | |
void | set_given_optsol (const double *given_sol, const int card_sol) |
Set given_optsol to the given optimal solution given_sol. | |
void | print () const |
Print some of the data members. | |
void | printOptTab (OsiSolverInterface *solver) const |
Print the current simplex tableau. | |
Constructors and destructors | |
CglRedSplit () | |
Default constructor. | |
CglRedSplit (const CglRedSplit &) | |
Copy constructor. | |
virtual CglCutGenerator * | clone () const |
Clone. | |
CglRedSplit & | operator= (const CglRedSplit &rhs) |
Assignment operator. | |
virtual | ~CglRedSplit () |
Destructor. | |
virtual std::string | generateCpp (FILE *fp) |
Create C++ lines to get to current state. | |
Private Member Functions | |
Private member methods | |
double | rs_above_integer (double value) |
Compute the fractional part of value, allowing for small error. | |
void | update_pi_mat (int r1, int r2, int step) |
Perform row r1 of pi := row r1 of pi - step * row r2 of pi. | |
void | update_redTab (int r1, int r2, int step) |
Perform row r1 of tab := row r1 of tab - step * row r2 of tab. | |
void | find_step (int r1, int r2, int *step, double *reduc, double *norm) |
Find optimal integer step for changing row r1 by adding to it a multiple of another row r2. | |
int | test_pair (int r1, int r2, double *norm) |
Test if an ordered pair of rows yields a reduction. | |
void | reduce_contNonBasicTab () |
Reduce rows of contNonBasicTab. | |
void | generate_row (int index_row, double *row) |
Generate a row of the current LP tableau. | |
int | generate_cgcut (double *row, double *rhs) |
Generate a mixed integer Chvatal-Gomory cut, when all non basic variables are non negative and at their lower bound. | |
void | eliminate_slacks (double *row, const double *elements, const int *start, const int *indices, const int *rowLength, const double *rhs, double *rowrhs) |
Use multiples of the initial inequalities to cancel out the coefficients of the slack variables. | |
void | flip (double *row) |
Change the sign of the coefficients of the continuous non basic variables at their upper bound. | |
void | unflip (double *row, double *rowrhs, const double *colLower, const double *colUpper, double *slack_val) |
Change the sign of the coefficients of the continuous non basic variables at their upper bound and do the translations restoring the original bounds. | |
int | generate_packed_row (const OsiSolverInterface *solver, double *row, int *rowind, double *rowelem, int *card_row, double &rhs) |
Generate the packed cut from the row representation. | |
void | check_optsol (const OsiSolverInterface *solver, const int calling_place, const double *xlp, const double *slack_val, const int do_flip) |
Check that the generated cuts do not cut a given optimal solution. | |
void | check_optsol (const OsiSolverInterface *solver, const int calling_place, const double *ck_row, const double ck_rhs, const int cut_number, const int do_flip) |
Check that the generated cuts do not cut a given optimal solution. | |
Private Attributes | |
Private member data | |
int | nrow |
Number of rows ( = number of slack variables) in the current LP. | |
int | ncol |
Number of structural variables in the current LP. | |
double | LUB |
Value considered large for the absolute value of lower or upper bound on a variable. | |
double | EPS |
Epsilon for precision. Default: 1e-7. | |
double | EPS_COEFF |
Epsilon for value of coefficients. Default: 1e-8. | |
double | EPS_COEFF_LUB |
Epsilon for value of coefficients for variables with absolute value of lower or upper bound larger than LUB. | |
double | EPS_RELAX |
Epsilon for relaxing the right hand side of each generated constraint. | |
double | normIsZero |
Norm of a vector is considered zero if smaller than normIsZero; Default: 1e-5. | |
double | minReduc |
Minimum reduction in percent that must be achieved by a potential reduction step in order to be performed; Between 0 and 1, default: 0.05. | |
int | card_intBasicVar_frac |
Number of integer basic structural variables that are fractional in the current lp solution (at least away_ from being integer). | |
int | card_intNonBasicVar |
Number of integer non basic structural variables in the current lp solution. | |
int | card_contNonBasicVar |
Number of continuous non basic variables (structural or slack) in the current lp solution. | |
int | card_nonBasicAtUpper |
Number of non basic variables (structural or slack) at their upper bound in the current lp solution. | |
int | card_nonBasicAtLower |
Number of non basic variables (structural or slack) at their lower bound in the current lp solution. | |
int * | cv_intBasicVar_frac |
Characteristic vector for integer basic structural variables with non integer value in the current lp solution. | |
int * | intBasicVar_frac |
List of integer structural basic variables (in order of pivot in selected rows for cut generation). | |
int * | intNonBasicVar |
List of integer structural non basic variables. | |
int * | contNonBasicVar |
List of continuous non basic variables (structural or slack). | |
int * | nonBasicAtUpper |
List of non basic variables (structural or slack) at their upper bound. | |
int * | nonBasicAtLower |
List of non basic variables (structural or slack) at their lower bound. | |
int | mTab |
Number of rows in the reduced tableau (= card_intBasicVar_frac). | |
int | nTab |
Number of columns in the reduced tableau (= card_contNonBasicVar). | |
int ** | pi_mat |
Tableau of multipliers used to alter the rows used in generation. | |
double ** | contNonBasicTab |
Current tableau for continuous non basic variables (structural or slack). | |
double ** | intNonBasicTab |
Current tableau for integer non basic structural variables. | |
double * | rhsTab |
Right hand side of the tableau. | |
double | away_ |
Use row only if pivot variable should be integer but is more than away_ from being integer. | |
int | limit_ |
Generate cut only if at most limit_ non zero coefficients in cut. | |
double | maxTab_ |
Maximum value for (mTab * mTab * max(mTab, nTab)). | |
double * | given_optsol |
Given optimal solution that should not be cut; only for debug. | |
int | card_given_optsol |
Number of entries in given_optsol. |
Based on the paper by K. Anderson, G. Cornuejols, Yanjun Li, "Reduce-and-Split Cuts: Improving the Performance of Mixed Integer Gomory Cuts", (2005), to appear in Management Science
Definition at line 22 of file CglRedSplit.hpp.
CglRedSplit::CglRedSplit | ( | ) |
Default constructor.
CglRedSplit::CglRedSplit | ( | const CglRedSplit & | ) |
Copy constructor.
virtual CglRedSplit::~CglRedSplit | ( | ) | [virtual] |
Destructor.
virtual void CglRedSplit::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.
Warning: 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 variants of Gomory cuts: Starting from the current optimal tableau, linear combinations of the rows of the current optimal simplex tableau are used for generating Gomory cuts. The choice of the linear combinations is driven by the objective of reducing the coefficients of the non basic continuous variables in the resulting row. Note that this generator might not be able to generate cuts for some solutions violating integrality constraints.
Parameters of the generator are listed below. Modifying the default values for parameters other than the last five might result in invalid cuts.
virtual void CglRedSplit::generateCuts | ( | const OsiSolverInterface & | si, | |
OsiCuts & | cs, | |||
const CglTreeInfo | info = CglTreeInfo() | |||
) | const [virtual] |
virtual bool CglRedSplit::needsOptimalBasis | ( | ) | const [virtual] |
Return true if needs optimal basis to do cuts (will return true).
Reimplemented from CglCutGenerator.
void CglRedSplit::setLimit | ( | int | limit | ) |
Set limit, the maximum number of non zero coefficients in generated cut; Default: 50.
int CglRedSplit::getLimit | ( | ) | const |
Get value of limit.
void CglRedSplit::setAway | ( | double | value | ) |
Set away, the minimum distance from being integer used for selecting rows for cut generation; all rows whose pivot variable should be integer but is more than away from integrality will be selected; Default: 0.05.
double CglRedSplit::getAway | ( | ) | const |
Get value of away.
void CglRedSplit::setLUB | ( | double | value | ) |
Set the value of LUB, value considered large for the absolute value of a lower or upper bound on a variable; Default: 1000.
double CglRedSplit::getLUB | ( | ) | const |
Get the value of LUB.
void CglRedSplit::setEPS | ( | double | value | ) |
Set the value of EPS, epsilon for double computations; Default: 1e-7.
double CglRedSplit::getEPS | ( | ) | const |
Get the value of EPS.
void CglRedSplit::setEPS_COEFF | ( | double | value | ) |
Set the value of EPS_COEFF, epsilon for values of coefficients; Default: 1e-8.
double CglRedSplit::getEPS_COEFF | ( | ) | const |
Get the value of EPS_COEFF.
void CglRedSplit::setEPS_COEFF_LUB | ( | double | value | ) |
Set the value of EPS_COEFF_LUB, epsilon for values of coefficients for variables with absolute value of lower or upper bound larger than LUB; Default: 1e-13.
double CglRedSplit::getEPS_COEFF_LUB | ( | ) | const |
Get the value of EPS_COEFF_LUB.
void CglRedSplit::setEPS_RELAX | ( | double | value | ) |
Set the value of EPS_RELAX, value used for relaxing the right hand side of each generated cut; Default: 1e-8.
double CglRedSplit::getEPS_RELAX | ( | ) | const |
Get the value of EPS_RELAX.
void CglRedSplit::setNormIsZero | ( | double | value | ) |
Set the value of normIsZero, the threshold for considering a norm to be 0; Default: 1e-5.
double CglRedSplit::getNormIsZero | ( | ) | const |
Get the value of normIsZero.
void CglRedSplit::setMinReduc | ( | double | value | ) |
Set the value of minReduc, threshold for relative norm improvement for performing a reduction; Default: 0.05.
double CglRedSplit::getMinReduc | ( | ) | const |
Get the value of minReduc.
void CglRedSplit::setMaxTab | ( | double | value | ) |
Set the maximum allowed value for (mTab * mTab * max(mTab, nTab)) where mTab is the number of rows used in the combinations and nTab is the number of continuous non basic variables.
The work of the generator is proportional to (mTab * mTab * max(mTab, nTab)). Reducing the value of maxTab makes the generator faster, but weaker. Default: 1e7.
double CglRedSplit::getMaxTab | ( | ) | const |
Get the value of maxTab.
void CglRedSplit::set_given_optsol | ( | const double * | given_sol, | |
const int | card_sol | |||
) |
Set given_optsol to the given optimal solution given_sol.
If given_optsol is set using this method, the code will stop as soon as a generated cut is violated by the given solution; exclusively for debugging purposes.
void CglRedSplit::print | ( | ) | const |
Print some of the data members.
void CglRedSplit::printOptTab | ( | OsiSolverInterface * | solver | ) | const |
Print the current simplex tableau.
virtual CglCutGenerator* CglRedSplit::clone | ( | ) | const [virtual] |
CglRedSplit& CglRedSplit::operator= | ( | const CglRedSplit & | rhs | ) |
Assignment operator.
virtual std::string CglRedSplit::generateCpp | ( | FILE * | fp | ) | [virtual] |
double CglRedSplit::rs_above_integer | ( | double | value | ) | [inline, private] |
Compute the fractional part of value, allowing for small error.
void CglRedSplit::update_pi_mat | ( | int | r1, | |
int | r2, | |||
int | step | |||
) | [private] |
Perform row r1 of pi := row r1 of pi - step * row r2 of pi.
void CglRedSplit::update_redTab | ( | int | r1, | |
int | r2, | |||
int | step | |||
) | [private] |
Perform row r1 of tab := row r1 of tab - step * row r2 of tab.
void CglRedSplit::find_step | ( | int | r1, | |
int | r2, | |||
int * | step, | |||
double * | reduc, | |||
double * | norm | |||
) | [private] |
Find optimal integer step for changing row r1 by adding to it a multiple of another row r2.
int CglRedSplit::test_pair | ( | int | r1, | |
int | r2, | |||
double * | norm | |||
) | [private] |
Test if an ordered pair of rows yields a reduction.
Perform the reduction if it is acceptable.
void CglRedSplit::reduce_contNonBasicTab | ( | ) | [private] |
Reduce rows of contNonBasicTab.
void CglRedSplit::generate_row | ( | int | index_row, | |
double * | row | |||
) | [private] |
Generate a row of the current LP tableau.
int CglRedSplit::generate_cgcut | ( | double * | row, | |
double * | rhs | |||
) | [private] |
Generate a mixed integer Chvatal-Gomory cut, when all non basic variables are non negative and at their lower bound.
void CglRedSplit::eliminate_slacks | ( | double * | row, | |
const double * | elements, | |||
const int * | start, | |||
const int * | indices, | |||
const int * | rowLength, | |||
const double * | rhs, | |||
double * | rowrhs | |||
) | [private] |
Use multiples of the initial inequalities to cancel out the coefficients of the slack variables.
void CglRedSplit::flip | ( | double * | row | ) | [private] |
Change the sign of the coefficients of the continuous non basic variables at their upper bound.
void CglRedSplit::unflip | ( | double * | row, | |
double * | rowrhs, | |||
const double * | colLower, | |||
const double * | colUpper, | |||
double * | slack_val | |||
) | [private] |
Change the sign of the coefficients of the continuous non basic variables at their upper bound and do the translations restoring the original bounds.
Modify the right hand side accordingly.
int CglRedSplit::generate_packed_row | ( | const OsiSolverInterface * | solver, | |
double * | row, | |||
int * | rowind, | |||
double * | rowelem, | |||
int * | card_row, | |||
double & | rhs | |||
) | [private] |
Generate the packed cut from the row representation.
void CglRedSplit::check_optsol | ( | const OsiSolverInterface * | solver, | |
const int | calling_place, | |||
const double * | xlp, | |||
const double * | slack_val, | |||
const int | do_flip | |||
) | [private] |
Check that the generated cuts do not cut a given optimal solution.
void CglRedSplit::check_optsol | ( | const OsiSolverInterface * | solver, | |
const int | calling_place, | |||
const double * | ck_row, | |||
const double | ck_rhs, | |||
const int | cut_number, | |||
const int | do_flip | |||
) | [private] |
Check that the generated cuts do not cut a given optimal solution.
int CglRedSplit::nrow [private] |
Number of rows ( = number of slack variables) in the current LP.
Definition at line 282 of file CglRedSplit.hpp.
int CglRedSplit::ncol [private] |
double CglRedSplit::LUB [private] |
Value considered large for the absolute value of lower or upper bound on a variable.
Default: 1000.
Definition at line 289 of file CglRedSplit.hpp.
double CglRedSplit::EPS [private] |
double CglRedSplit::EPS_COEFF [private] |
double CglRedSplit::EPS_COEFF_LUB [private] |
Epsilon for value of coefficients for variables with absolute value of lower or upper bound larger than LUB.
Default: 1e-13.
Definition at line 299 of file CglRedSplit.hpp.
double CglRedSplit::EPS_RELAX [private] |
Epsilon for relaxing the right hand side of each generated constraint.
Default: 1e-8.
Definition at line 303 of file CglRedSplit.hpp.
double CglRedSplit::normIsZero [private] |
Norm of a vector is considered zero if smaller than normIsZero; Default: 1e-5.
Definition at line 307 of file CglRedSplit.hpp.
double CglRedSplit::minReduc [private] |
Minimum reduction in percent that must be achieved by a potential reduction step in order to be performed; Between 0 and 1, default: 0.05.
Definition at line 311 of file CglRedSplit.hpp.
int CglRedSplit::card_intBasicVar_frac [private] |
Number of integer basic structural variables that are fractional in the current lp solution (at least away_ from being integer).
Definition at line 315 of file CglRedSplit.hpp.
int CglRedSplit::card_intNonBasicVar [private] |
Number of integer non basic structural variables in the current lp solution.
Definition at line 319 of file CglRedSplit.hpp.
int CglRedSplit::card_contNonBasicVar [private] |
Number of continuous non basic variables (structural or slack) in the current lp solution.
Definition at line 323 of file CglRedSplit.hpp.
int CglRedSplit::card_nonBasicAtUpper [private] |
Number of non basic variables (structural or slack) at their upper bound in the current lp solution.
Definition at line 327 of file CglRedSplit.hpp.
int CglRedSplit::card_nonBasicAtLower [private] |
Number of non basic variables (structural or slack) at their lower bound in the current lp solution.
Definition at line 331 of file CglRedSplit.hpp.
int* CglRedSplit::cv_intBasicVar_frac [private] |
Characteristic vector for integer basic structural variables with non integer value in the current lp solution.
Definition at line 335 of file CglRedSplit.hpp.
int* CglRedSplit::intBasicVar_frac [private] |
List of integer structural basic variables (in order of pivot in selected rows for cut generation).
Definition at line 339 of file CglRedSplit.hpp.
int* CglRedSplit::intNonBasicVar [private] |
int* CglRedSplit::contNonBasicVar [private] |
List of continuous non basic variables (structural or slack).
Definition at line 346 of file CglRedSplit.hpp.
int* CglRedSplit::nonBasicAtUpper [private] |
List of non basic variables (structural or slack) at their upper bound.
Definition at line 350 of file CglRedSplit.hpp.
int* CglRedSplit::nonBasicAtLower [private] |
List of non basic variables (structural or slack) at their lower bound.
Definition at line 354 of file CglRedSplit.hpp.
int CglRedSplit::mTab [private] |
Number of rows in the reduced tableau (= card_intBasicVar_frac).
Definition at line 357 of file CglRedSplit.hpp.
int CglRedSplit::nTab [private] |
Number of columns in the reduced tableau (= card_contNonBasicVar).
Definition at line 360 of file CglRedSplit.hpp.
int** CglRedSplit::pi_mat [private] |
Tableau of multipliers used to alter the rows used in generation.
Dimensions: mTab by mTab. Initially, pi_mat is the identity matrix.
Definition at line 364 of file CglRedSplit.hpp.
double** CglRedSplit::contNonBasicTab [private] |
Current tableau for continuous non basic variables (structural or slack).
Only rows used for generation. Dimensions: mTab by nTab.
Definition at line 369 of file CglRedSplit.hpp.
double** CglRedSplit::intNonBasicTab [private] |
Current tableau for integer non basic structural variables.
Only rows used for generation.
Definition at line 374 of file CglRedSplit.hpp.
double* CglRedSplit::rhsTab [private] |
Right hand side of the tableau.
Only rows used for generation.
Definition at line 378 of file CglRedSplit.hpp.
double CglRedSplit::away_ [private] |
Use row only if pivot variable should be integer but is more than away_ from being integer.
Definition at line 382 of file CglRedSplit.hpp.
int CglRedSplit::limit_ [private] |
Generate cut only if at most limit_ non zero coefficients in cut.
Definition at line 384 of file CglRedSplit.hpp.
double CglRedSplit::maxTab_ [private] |
Maximum value for (mTab * mTab * max(mTab, nTab)).
See method setMaxTab().
Definition at line 388 of file CglRedSplit.hpp.
double* CglRedSplit::given_optsol [private] |
Given optimal solution that should not be cut; only for debug.
Definition at line 391 of file CglRedSplit.hpp.
int CglRedSplit::card_given_optsol [private] |