Skip to content

CglLandP

Jump to bottom
Stefan Vigerske edited this page Mar 2, 2019 · 2 revisions

Contributor: [mailto:pierre.bonami@gmail.com Pierre Bonami]

Maintainer: [mailto:pierre.bonami@gmail.com Pierre Bonami]

Introduction

This procedure implements different variants of the lift-and-project procedure executed in the LP simplex tableau described by Balas and Perregaard. The code has been developped in a joint work with Egon Balas.

References

  • E. Balas and M. Perregaard. A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 0-1 programming. Math. Program., 94(203,Ser. B):221-245,2003. Link to journal

  • M. Perregaard. A practical implementation of lift-and-project cuts. International Symposium on Mathematical Programming, Copenhagen (2003). Presentation in PDF

  • E. Balas, P. Bonami. New variants of lift-and-project cut generation from the LP tableau: open source implementation and testing. IPCO2007, June 2007, Cornell University.

  • E. Balas, P. Bonami. Generating Lift-and-Pro ject Cuts from the LP Simplex Tableau: Additional tables. Here

  • E. Balas, P. Bonami. Detailed examples of lift-and-project separation. Here

Notes

This generator currently works only with Clp, due to its use of advanced features not implemented (yet?) for other linear solvers in Osi.

Parameters

Parameters can be changed by using the member function parameters() of the class CglLandP. For example to change the default parameters for the time limit and the maximum number of pivots per cut: {{{ CglLandP landpGen;

landpGen.parameter().timeLimit = 10.; landpGen.parameter().pivotLimit = 2; }}}

Algorithm Choices

  • selectionRule Rule for choosing pivoting variables. Possible values are:

    • mostNegativeRc Select variable with most negative reduced cost for entering the basis,
    • bestPivot Select leaving and entering variables according to the Most Violated Cut Selection Rule.

    The default value is mostNegativeRc.

  • modularize If set to 1, after each pivot modularize source row (set to 0 by default)

  • reducedSpace If set to 1, perform the cut generation in the reduced space (set to 1 by default).

Per Round Limits

  • maxCutPerRound Maximum number of cuts generated in each round, the default value is 50.
  • timeLimit global time limit in seconds for performing one round of separation (default value is a very large number).
  • away In the current LP optimum, a basic variable have to be at least this much away from an integer value for a cut to be generated for the corresponding row. The default value is 5.10^-3^.

Limits for the Separation of Each Cut

  • pivotLimit Maximum number of pivots performed for each cut. The default value is $20$.
  • degeneratePivotLimit limit the number of consecutive degenerate pivot, default value is $0$.
  • singleCutTimeLimit time limit in seconds for each cut separation (default value is $+\infty$).

Cut Parameters

  • scaleCuts If set to true cuts are scaled to have +-1 right-hand-side. Most linear programming solvers (Clp, Cplex, Xpress,...) already include an automatic scaling of the problem and therefore by default no scaling is performed.

Pivoting Tolerances

  • pivotTol if the pivot element $\overline a_{ij}$ is less than this value we don't consider this pivot, the default tolerance is 10^-6^.

Documentation and Bug Reports

A short documentation for using the cut generator is available here.

See also the section "Project Links" on the Cgl [WikiStart main Trac page].

Attachments:

Clone this wiki locally