= CglLandP =
Contributor: [mailto:pierre.bonami@gmail.com Pierre Bonami][[BR]]
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. [http://www.springerlink.com/content/p8qbm2p9jeha4wp1 Link to journal]
* M. Perregaard. A practical implementation of lift-and-project cuts. International Symposium on Mathematical Programming, Copenhagen (2003). [http://www.google.com/url?sa=t&ct=res&cd=2&url=http%3A%2F%2Fwww.dashoptimization.com%2Fhome%2Fdownloads%2Fpdf%2Fismp2003_MP.pdf&ei=4gI5RYC-N4fIwAKL_5yuAw&sig=__FplD3qNw1ASLiJhVLN4uoASymx0=&sig2=Tkw-M9tkcet5ltcby28nDA 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. [https://projects.coin-or.org/Cgl/attachment/wiki/CglLandP/sup_table.pdf Here]
* E. Balas, P. Bonami. Detailed examples of lift-and-project separation. [https://projects.coin-or.org/Cgl/attachment/wiki/CglLandP/pivotsv5.pdf 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 [https://projects.coin-or.org/Cgl/attachment/wiki/CglLandP/CglLandP.pdf?format=raw here].
See also the section "Project Links" on the {{{Cgl}}} [WikiStart main Trac page].