CglLandP

Contributor and Maintainer: Pierre Bonami (@pobonomo)

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. A short documentation for using the cut generator is available here.

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

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. DOI: 10.1007/s10107-002-0317-y
• E. Balas, P. Bonami. Generating Lift-and-Project Cuts from the LP Simplex Tableau: Additional tables. Here
• E. Balas, P. Bonami. Detailed examples of lift-and-project separation. Here

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 +∞).

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 a̅_ij is less than this value we don't consider this pivot, the default tolerance is 10^-6.