Version 14 (modified by pbonami, 11 years ago) (diff) 

CglLandP
Contributor: Pierre Bonami
Maintainer: Pierre Bonami
Introduction
This procedure implements different variants of the liftandproject 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
 Balas and M. Perregaard. A precise correspondence between liftandproject cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 01 programming. Math. Program., 94(203,Ser. B):221245,2003. Link to journal
 Perregaard. A practical implementation of liftandproject cuts. International Symposium on Mathematical Programming, Copenhagen (2003). Presentation in PDF
 Balas, P. Bonami. New variants of liftandproject cut generation from the LP tableau: open source implementation and testing. IPCO2007, June 2007, Cornell University.
 Balas, P. Bonami. Generating LiftandPro ject Cuts from the LP Simplex Tableau: Additional tables. 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 righthandside. 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 main Trac page.
Attachments (4)

CglLandP.pdf
(108.9 KB) 
added by pbonami 14 years ago.
Latex Documentation of CglLandP
 sup_table.pdf (57.1 KB)  added by pbonami 11 years ago.
 pivotsv4.pdf (112.0 KB)  added by pbonami 11 years ago.
 pivotsv5.pdf (107.0 KB)  added by pbonami 11 years ago.
Download all attachments as: .zip