CglRedSplit

Contributor and Maintainer: Francois Margot

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.

Publication:

• K. Anderson, G. Cornuejols, Yanjun Li, Reduce-and-Split Cuts: Improving the Performance of Mixed Integer Gomory Cuts, Management Science 51, 2005

Notes:

• 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.
• This generator might not be able to generate cuts for some solutions violating integrality constraints.
• 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). If the first condition is not met, no cuts are generated. If the second condition is not met, no cuts or invalid cuts may be generated.

Parameters of the generator are listed below. Modifying the default values for parameters other than the last five might result in invalid cuts.

• LUB: Value considered large for the absolute value of a lower or upper bound on a variable.
  • Default value: 1000. See method setLUB().
• EPS: Precision of double computations.
  • Default value: 1e-7. See method setEPS().
• EPS_COEFF: Precision for deciding if a coefficient of a generated cut is zero.
  • Default value: 1e-8. See method setEPS_COEFF().
• EPS_COEFF_LUB: Precision for deciding if a coefficient of a generated cut is zero when the corresponding variable has a lower or upper bound larger than LUB in absolute value.
  • Default value: 1e-13. See method setEPS_COEFF_LUB().
• EPS_RELAX: Value used to relax slightly the right hand side of each generated cut.
  • Default value: 1e-8. See method setEPS_RELAX().
• normIsZero: Norm of a vector is considered zero if smaller than this value.
  • Default value: 1e-5. See method setNormIsZero().
• minReduc: Reduction is performed only if the norm of the vector is reduced by this fraction.
  • Default value: 0.05. See method setMinReduc().
• limit: Generate cuts with at most this number of nonzero entries.
  • Default value: 50. See method setLimit().
• away: Look only at basic integer variables whose current value is at least this value from being integer.
  • Default value: 0.05. See method setAway().
• maxTab: Controls the number of rows selected for the generation.
  • Default value: 1e7. See method setMaxTab().