A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming

 We establish a precise correspondence between lift-and-project cuts for mixed 0-1 programs, simple disjunctive cuts (intersection cuts) and mixed-integer Gomory cuts. The correspondence maps members of one family onto members of the others. It also maps bases of the higher-dimensional cut generating linear program (CGLP) into bases of the linear programming relaxation. It provides new bounds on the number of facets of the elementary closure, and on the rank, of the standard linear programming relaxation of the mixed 0-1 polyhedron with respect to the above families of cutting planes. Based on the above correspondence, we develop an algorithm that solves (CGLP) without explicitly constructing it, by mimicking the pivoting steps of the higher dimensional (CGLP) simplex tableau by certain pivoting steps in the lower dimensional (LP) simplex tableau. In particular, we show how to calculate the reduced costs of the big tableau from the entries of the small tableau and based on this, how to identify a pivot in the small tableau that corresponds to one or several improving pivots in the big tableau. The overall effect is a much improved lift-and-project cut generating procedure, which can also be interpreted as an algorithm for a systematic improvement of mixed integer Gomory cuts from the small tableau. Received: October 5, 2000 / Accepted: March 19, 2002 Published online: September 5, 2002 Research was supported by the National Science Foundation through grant #DMI-9802773 and by the Office of Naval Research through contract N00014-97-1-0196.     

Monoidal cut strengthening revisited

There are two distinct strengthening methods for disjunctive cuts with some integer variables; they differ in the way they modularize the coefficients. In this paper, we introduce a new variant of one of these methods, the monoidal cut strengthening procedure, based on the paradox that sometimes weakening a disjunction helps the strengthening procedure and results in sharper cuts. We first derive a general result that applies to cuts from disjunctions with any number of terms. It defines the coefficients of the cut in a way that takes advantage of the option of adding new terms to the disjunction. We then specialize this result to the case of split cuts for mixed integer programs with some binary variables, in particular Gomory mixed integer cuts, and to intersection cuts from multiple rows of a simplex tableau. In both instances we specify the conditions under which the new cuts have smaller coefficients than the cuts obtained by either of the two currently known strengthening procedures.     

Projection, Lifting and Extended Formulation in Integer and Combinatorial Optimization

This is an overview of the significance and main uses of projection, lifting and extended formulation in integer and combinatorial optimization. Its first two sections deal with those basic properties of projection that make it such an effective and useful bridge between problem formulations in different spaces, i.e. different sets of variables. They discuss topics like projection and restriction, the integrality-preserving property of projection, the dimension of projected polyhedra, conditions for facets of a polyhedron to project into facets of its projections, and so on. The next two sections describe the use of projection for comparing the strength of different formulations of the same problem, and for proving the integrality of polyhedra by using extended formulations or lifting. Section 5 deals with disjunctive programming, or optimization over unions of polyhedra, whose most important incarnation are mixed 0-1 programs and their partial relaxations. It discusses the compact representation of the convex hull of a union of polyhedra through extended formulation, the connection between the projection of the latter and the polar of the convex hull, as well as the sequential convexification of facial disjunctive programs, among them mixed 0-1 programs, with the related concept of disjunctive rank. Section 6 reviews lift-and-project cuts, the construction of cut generating linear programs, and techniques for lifting and for strengthening disjunctive cuts. Section 7 discusses the recently discovered possibility of solving the higher dimensional cut generating linear program without explicitly constructing it, by a sequence of properly chosen pivots in the simplex tableau of the linear programming relaxation. Finally, section 8 deals with different ways of combining cuts with branch and bound, and briefly discusses computational experience with lift-and-project cuts. This is an updated and extended version of the paper published in LNCS 2241, Springer, 2001 (as given in Balas, 2001). Research was supported by the National Science Foundation through grant #DMI-9802773 and by the Office of Naval Research through contract N00014-97-1-0196.     

Lift-and-project for general two-term disjunctions

In this paper we generalize the cut strengthening method of Balas and Perregaard for 0/1 mixed-integer programming to disjunctive programs with general two-term disjunctions. We apply our results to linear programs with complementarity constraints.     

On the separation of disjunctive cuts

Disjunctive cuts for Mixed-Integer Linear Programs (MIPs) were introduced by Egon Balas in the late 1970s and have been successfully exploited in practice since the late 1990s. In this paper we investigate the main ingredients of a disjunctive cut separation procedure, and analyze their impact on the quality of the root-node bound for a set of instances taken from MIPLIB library. We compare alternative normalization conditions, and try to better understand their role. In particular, we point out that constraints that become redundant (because of the disjunction used) can produce over-weak cuts, and analyze this property with respect to the normalization used. Finally, we introduce a new normalization condition and analyze its theoretical properties and computational behavior. Along the way, we make use of a number of small numerical examples to illustrate some basic (and often misinterpreted) disjunctive programming features.     

On optimizing over lift-and-project closures

The strengthened lift-and-project closure of a mixed integer linear program is the polyhedron obtained by intersecting all strengthened lift-and-project cuts obtained from its initial formulation, or equivalently all mixed integer Gomory cuts read from all tableaux corresponding to feasible and infeasible bases of the LP relaxation. In this paper, we present an algorithm for approximately optimizing over the strengthened lift-and-project closure. The originality of our method is that it relies on a cut generation linear programming problem which is obtained from the original LP relaxation by only modifying the bounds on the variables and constraints. This separation LP can also be seen as dual to the cut generation LP used in disjunctive programming procedures with a particular normalization. We study properties of this separation LP, and discuss how to use it to approximately optimize over the strengthened lift-and-project closure. Finally, we present computational experiments and comparisons with recent related works.     

A note on the MIR closure and basic relaxations of polyhedra

Anderson et al. (2005) [1] show that for a polyhedral mixed integer set defined by a constraint system Ax≥b, along with integrality restrictions on some of the variables, any split cut is in fact a split cut for a basic relaxation, i.e., one defined by a subset of linearly independent constraints. This result implies that any split cut can be obtained as an intersection cut. Equivalence between split cuts obtained from simple disjunctions of the form x_j≤0 or x_j≥1 and intersection cuts was shown earlier for 0/1-mixed integer sets by Balas and Perregaard (2002) [4]. We give a short proof of the result of Anderson, Cornuéjols and Li using the equivalence between mixed integer rounding (MIR) cuts and split cuts.     

A lift-and-project cutting plane algorithm for mixed 0–1 programs

We propose a cutting plane algorithm for mixed 0–1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthening step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovász and Schrijver and the hierarchy of relaxations of Sherali and Adams.The research underlying this report was supported by National Science Foundation Grant #DDM-8901495 and Office of Naval Research Contract N00014-85-K-0198.     

Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra

In this paper, we study the relationship between 2D lattice-free cuts, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in ${\mathbb{R}^2}$ , and various types of disjunctions. Recently Li and Richard (2008), studied disjunctive cuts obtained from t-branch split disjunctions of mixed-integer sets (these cuts generalize split cuts). Balas (Presentation at the Spring Meeting of the American Mathematical Society (Western Section), San Francisco, 2009) initiated the study of cuts for the two-row continuous group relaxation obtained from 2-branch split disjunctions. We study these cuts (and call them cross cuts) for the two-row continuous group relaxation, and for general MIPs. We also consider cuts obtained from asymmetric 2-branch disjunctions which we call crooked cross cuts. For the two-row continuous group relaxation, we show that unimodular cross cuts (the coefficients of the two split inequalities form a unimodular matrix) are equivalent to the cuts obtained from maximal lattice-free sets other than type 3 triangles. We also prove that all 2D lattice-free cuts and their S-free extensions are crooked cross cuts. For general mixed integer sets, we show that crooked cross cuts can be generated from a structured three-row relaxation. Finally, we show that for the corner relaxation of an MIP, every crooked cross cut is a 2D lattice-free cut.     

Valid Inequalities for the Lasdon-Terjung Production Model

We consider a very simple integer program involving production of a single item and start-up costs for the standard machines first studied by Lasdon and Terjung. Solving directly as an integer program leads to prohibitively large branch and bound trees. Here, we show how using a simple family of valid inequalities and a heuristic procedure to choose one of these inequalities as a cut, it is possible to reduce substantially the size of the tree, and in several cases to eliminate the need for branch and bound. The valid inequalities used are all simple Gomory cuts. However, they are derived from the initial problem formulation rather than from the optimal linear programming tableau.     

A finitely convergent procedure for facial disjunctive programs

This paper addresses an important class of disjunctive programs called facial disjunctive programs, examples of which include the zero-one linear integer programming problem and the linear complementarity problem. Balas has characterized some fundamental properties of such problems, one of which has been used by Jeroslow to obtain a finitely convergent procedure. This paper exploits another basic property of facial disjunctive programs in order to develop an alternative finitely convergent algorithm.     

A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization

We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization (MISOCO) problem. We extend our prior work on disjunctive conic cuts (DCCs), which has thus far been restricted to the case in which the intersection of the hyperplanes and the feasible set is bounded. Using a similar technique, we show that one can extend our previous results to the case in which that intersection is unbounded. We provide a complete characterization in closed form of the conic inequalities required to describe the convex hull when the hyperplanes defining the disjunction are parallel.     

Practical strategies for generating rank-1 split cuts in mixed-integer linear programming

In this paper we propose practical strategies for generating split cuts, by considering integer linear combinations of the rows of the optimal simplex tableau, and deriving the corresponding Gomory mixed-integer cuts; potentially, we can generate a huge number of cuts. A key idea is to select subsets of variables, and cut deeply in the space of these variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. An extensive computational evaluation of these cuts points to the following two conclusions. The first is that our rank-1 cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, Reduce-and-Split, Lift-and-Project, Flow and Knapsack cover): on MIPLIB instances, these generators close 24% of the integrality gap on average; adding our cuts yields an additional 5%. The second conclusion is that, when incorporated in a Branch-and-Cut framework, these new cuts can improve computing time on difficult instances.     

Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems

Branch and cut methods for integer programming problems solve a sequence of linear programming problems. Traditionally, these linear programming relaxations have been solved using the simplex method. The reduced costs available at the optimal solution to a relaxation may make it possible to fix variables at zero or one. If the solution to a relaxation is fractional, additional constraints can be generated which cut off the solution to the relaxation, but donot cut off any feasible integer points. Gomory cutting planes and other classes of cutting planes are generated from the final tableau. In this paper, we consider using an interior point method to solve the linear programming relaxations. We show that it is still possible to generate Gomory cuts and other cuts without having to recreate a tableau, and we also show how variables can be fixed without using the optimal reduced costs. The procedures we develop do not require that the current relaxation be solved to optimality; this is useful for an interior point method because early termination of the current relaxation results in an improved starting point for the next relaxation.     

Sequential pairing of mixed integer inequalities

We investigate a scheme, called pairing, for generating new valid inequalities for mixed integer programs by taking pairwise combinations of existing valid inequalities. The pairing scheme essentially produces a split cut corresponding to a specific disjunction, and can also be derived through the mixed integer rounding procedure. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that lead to a manageable set of non-dominated inequalities. We illustrate the framework for some deterministic and stochastic integer programs and we present computational results showing the efficiency of adding the new generated inequalities as cuts.     

Note on: N.E. Aguilera, M.S. Escalante, G.L. Nasini, “The disjunctive procedure and blocker duality”

Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–13] give a generalization of a theorem of Lehman through an extension of the disjunctive procedure defined by Balas, Ceria and Cornuéjols. This generalization can be formulated as(A) For every clutter , the disjunctive index of its set covering polyhedron coincides with the disjunctive index of the set covering polyhedron of its blocker, .In Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–3], (A) is indeed a corollary of the stronger result(B) .Motivated by the work of Gerards et al. [Math. Oper. Res. 28 (2003) 884–885] we propose a simpler proof of (B) as well as an alternative proof of (A), independent of (B). Both of them are based on the relationship between the “disjunctive relaxations” obtained by and the set covering polyhedra associated with some particular minors of .     

Equivalence between intersection cuts and the corner polyhedron

Intersection cuts were introduced by Balas and the corner polyhedron by Gomory. Balas showed that intersection cuts are valid for the corner polyhedron. In this paper we show that, conversely, every nontrivial facet-defining inequality for the corner polyhedron is an intersection cut.     

A branch-and-cut method for 0-1 mixed convex programming

We generalize the disjunctive approach of Balas, Ceria, and Cornuéjols [2] and devevlop a branch-and-cut method for solving 0-1 convex programming problems. We show that cuts can be generated by solving a single convex program. We show how to construct regions similar to those of Sherali and Adams [20] and Lovász and Schrijver [12] for the convex case. Finally, we give some preliminary computational results for our method. Received January 16, 1996 / Revised version received April 23, 1999?Published online June 28, 1999