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

# CglRedSplit

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()`.