Lift-and-project Cuts: An efficient Solution Method for Mixed Integer Programs

Sebastian Ceria (sebas@cumparsita.gsb.columbia.edu)
Columbia University

Download slides in PostScript format, PDF format, or PowerPoint format.

Introduction

The topic of this talk is the solution of general mixed integer programs using cutting planes derived from disjunctive formulations. Although the theory applies to general integer programs, this talk is restricted to 0/1-programs, where the integer constrained variables can only take the values 0 or 1.
    The basic formulation of a 0/1-program is shown in slide 2. In Branch-and-Bound the LP-relaxation of that formulation, also shown in slide 2, is typically used as a lower bound. The lift-and-project approach is a method to find inequalities that are valid for the 0/1-program but are violated at the optimal solution to the LP-relaxation. Hence adding these inequalities to the LP-relaxation, tightens the formulation and thereby strengthens the lower bounds in a Branch-and-Bound framework. The original lift-and-project method is due to Egon Balas, Gerard Cornuéjols and Sebastian Ceria [3].

Basic Theory

Since each 0/1-variable xi must take either the value 0 or 1, any feasible solution to the 0/1-program must also satisfy the disjunction shown in slide 4. This disjunction should be read as, either a feasible solution x must satisfy the left term or it must satisfy the right term. Such a disjunction is a strengthening of the LP-relaxation if the variable xi is fractional in the optimal solution to the LP-relaxation. What we seek are inequalities valid for Pi, the set of solutions x that satisfies the disjunction, but which are violated at the optimal solution to the LP-relaxation.
    Slides 5-13 illustrate a three-dimensional example where a cutting plane is found, based on the two term disjunction in slide 7, which separates the optimal LP-relaxation solution from the set of feasible solutions to the 0/1-program.
    In [1] Egon Balas describes how the convex hull of the feasible solutions to a disjunctive program can be represented using a higher dimensional linear formulation. In slide 15 the higher dimensional formulation representing Pi is shown. Here x1 can be interpreted as a feasible solution to the first term of the disjunction and likewise x2 is a feasible solution  to the second term. The interpretation of this program is that an x belongs to Pi if and only if it can be written as a convex combination of an x1 satisfying the first term, and an x2 satisfying the second term. To get the valid inequalities for x implied by this program, the higher dimensional variables x1 and x2 are projected out. In slide 14 is shown the corresponding projection cone.

Normalization

A cut is valid for Pi if and only if it is feasible in this linear program. Hence a valid inequality for Pi and thereby the 0/1-program can be obtained by optimizing a linear program similar, with an objective of cutting off the LP relaxation solution (slide 16). The problem with the linear program in slide 14 is that it describes a cone and is therefore unbounded (or zero). Interpreting this linear program as the dual, the corresponding primal problem (slide 17) is then infeasible. The infeasibility comes from trying to describe the LP-relaxation solution as a convex combination of solutions to the two terms of the disjunction. Slide 18 illustrates this infeasiblity. The solution is to normalize the cut generation linear program by adding a constraint (or constraints) which bounds the cone. This corresponds to relaxing the primal formulation to make it feasible. In slide 19 is proposed one such normalization. If the norm used in the dual is the (1+p)-norm then the corresponding norm in the primal is the (1+1/p)-norm. The geometric interpretation of this type of normalization is to introduce an extra point x* inside the convex hull and then minimize the distance between x* and the LP-relaxation solution, in the (1+1/p)-norm. This is illustrated in slide 20.
    An alternative normalization is to restrict the multipliers (slide 21). The primal interpretation of this is to relax all constraints by the same amount t. The geometrical interpretation is to expand the feasible regions for each disjunctive term, until the LP-relaxation solution lies within the convex hull of these relaxed sets. This is illustrated in slide 22.

Lifting

Slide 23 gives a look at the structure of the cut generation linear program. This program is quite large compared against the LP-relaxation and requires substantial effort to solve. One of the key ideas that makes the lift-and-project method work in practice is the observation that it is possible to ignore all variables that are at a bound in the LP-relaxation solution (slide 24). Thus the cut LP can be formulated and optimized in the subspace of the fractional variables only. Using the solution from this subspace formulation a full-space cut can easily be constructed. Since branching in Branch-and-Bound is usually accomplished by fixing one variable to either 0 or 1, then in the LP-relaxation solution, the fixed variables will be at a bound and hence lifted. Therefore the subspace formulation will not contain any fixed variables and the resulting cut can easily be made globally valid when lifted to the full space.
Another idea towards reducing computational time is to include only those original constraints tight at the LP-relaxation solution (slide 25). The resulting cuts might be weaker, but computational testing in [4] indicates that the reduction in computational time is worth it.
    In slide 26 is displayed the resulting cut LP used along with the deleted rows and columns corresponding to lifted variables and the deleted columns corresponding to ignored original constraints.

Multiple Cut Generation

Since each basic solution to the cut LP corresponds to a valid inequality for the 0/1-program, several different cuts can be obtained by exploring different basic solutions. One idea, shown in slide 27, is to force some of the multipliers currently basic in the cut LP to be non-basic. This is accomplished by forcing them to zero. Reoptimizing the cut LP will then yield a different basic solution which might result in a different cut. An alternative approach suggested by Egon Balas [2] is to do some pivots in the cut LP to reach alternative solutions.
    A second idea to obtain alternative cuts (slide 28) is to find several solutions to the LP-relaxation and optimize the cut LP with the objective of cutting off each of these solutions. These extra LP-relaxation can be obtained by doing pivots in the LP-relaxation.

Results

Slide 29 introduces the settings under which the lift-and-project method was tested. The mentioned strong branching is a feature of CPLEX which for each 0/1-variable computes the penalty of forcing it to either zero or one. The penalty is computed by solving the LP-relaxation with each variable fixed to either zero or one in turn, within a fixed iteration limit. Strong branching is then used to determine which fractional variables to use for cut generation. At most 50 fractional variables are selected.
    Slide 30 describes how the lift-and-project cuts are used. Basically, a pool of cuts is generated and added to the 0/1-program. The strengthened formulation is then given over to either CPLEX 5.0 or XPRESS-MP to solve to completion. For cut generation, the idea presented in slide 27 (fixing multipliers) is used to generate multiple cuts from each cut LP. Not mentioned in the talk, but in the paper [3], each cut is strengthened by exploiting the integrality condition on other variables than the one used to build the disjunction. The strengthening procedure is described in [5].
    The following slides 31-35 presents the computational results of the lift-and-project method compared against CPLEX 5.0. Here C&B = Cut-and-Branch, where the 0/1-program is first strengthened using lift-and-project cuts and the resulting program then solved by CPLEX 5.0.

References

[1] E. Balas, Disjunctive Programming, Annals of Discrete Mathematics, 5(1979) 3-51.
[2] E. Balas, Recent Advances in Lift-and-Project, Technical Report, GSIA, Carnegie Mellon University (1997).
[3] E. Balas, S. Ceria, G. Cornuéjols, A lift-and-project cutting plane algorithm for mixed 0-1 programs, Mathematical Programming, 58 (1993) 295-324.
[4] E. Balas, S. Ceria, G. Cornuéjols, Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework, Management Science, 42 (1996) 1229-1246.
[5] E. Balas, R.G. Jeroslow, Strengthening cuts for mixed integer programs, European Journal of Operational Research, 4 (1980) 224-234.
[6] S. Ceria, G. Pataki, Solving Integer and Disjunctive Programs by Lift and Project, Proceedings of the 6th International IPCO Conference (1998) 271-283.