Version 8 (modified by guest, 13 years ago) (diff) |
---|

# CglRedSplit

Contributor: Francois Margot

Maintainer: Francois Margot, fmargot@…

## Introduction

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.

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.

## 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.

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

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)`. If either of the above condition fails, no cuts are generated.

## Parameters

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