Version 3 (modified by guest, 14 years ago) (diff)



Contributor: Francois Margot
Maintainer: Francois Margot, fmargot@…

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.

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.

Note that this generator might not be able to generate cuts for some solutions violating integrality constraints.

See 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 for more details.

Note also that 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).

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. See method setLUB().
  • EPS: Precision of double computations. See method setEPS().
  • EPS_COEFF: Precision for deciding if a coefficient of a generated cut is zero. 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. See method setEPS_COEFF_LUB().
  • EPS_RELAX: Value used to relax slightly the right hand side of each generated cut. See method setEPS_RELAX().
  • normIsZero: Norm of a vector is considered zero if smaller than this value. See method setNormIsZero().
  • minReduc: Reduction is performed only if the norm of the vector is reduced by this fraction. See method setMinReduc().
  • limit: Generate cuts with at most this number of nonzero entries. See method setLimit().
  • away: Look only at basic integer variables whose current value is at least this value from being integer. See method setAway().
  • maxTab: Controls the number of rows selected for the generation. See method setMaxTab().