Lift-and-project cuts for convex mixed integer nonlinear programs

We describe a computationally effective method for generating lift-and-project cuts for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs and in the limit generates an inequality as strong as the lift-and-project cut that can be obtained from solving a cut-generating nonlinear program. Using this procedure, we are able to approximately optimize over the rank one lift-and-project closure for a variety of convex MINLP instances. The results indicate that lift-and-project cuts have the potential to close a significant portion of the integrality gap for convex MINLPs. In addition, we find that using this procedure within a branch-and-cut solver for convex MINLPs significantly reduces the total solution time for many instances. We also demonstrate that combining lift-and-project cuts with an extended formulation that exploits separability of convex functions yields significant improvements in both relaxation bounds and the time to calculate the relaxation. Overall, these results suggest that with an effective separation routine, like the one proposed here, lift-and-project cuts may be as effective for solving convex MINLPs as they have been for solving mixed-integer linear programs.     

Exact MAX-2SAT solution via lift-and-project closure

We present a new approach for exact solution of MAX-2SAT problems based on a strong reformulation deduced from an optimal continuous solution over the elementary closure of lift-and-project cuts. Computational results show that this formulation leads to a reduced number of nodes in the branch-and-bound tree and short computing times.     

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 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.     

Cuts for mixed 0-1 conic programming

In this we paper we study techniques for generating valid convex constraints for mixed 0-1 conic programs. We show that many of the techniques developed for generating linear cuts for mixed 0-1 linear programs, such as the Gomory cuts, the lift-and-project cuts, and cuts from other hierarchies of tighter relaxations, extend in a straightforward manner to mixed 0-1 conic programs. We also show that simple extensions of these techniques lead to methods for generating convex quadratic cuts. Gomory cuts for mixed 0-1 conic programs have interesting implications for comparing the semidefinite programming and the linear programming relaxations of combinatorial optimization problems, e.g. we show that all the subtour elimination inequalities for the traveling salesman problem are rank-1 Gomory cuts with respect to a single semidefinite constraint. We also include results from our preliminary computational experiments with these cuts.Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.     

Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs

Two-stage stochastic mixed-integer programming (SMIP) problems with recourse are generally difficult to solve. This paper presents a first computational study of a disjunctive cutting plane method for stochastic mixed 0-1 programs that uses lift-and-project cuts based on the extensive form of the two-stage SMIP problem. An extension of the method based on where the data uncertainty appears in the problem is made, and it is shown how a valid inequality derived for one scenario can be made valid for other scenarios, potentially reducing solution time. Computational results amply demonstrate the effectiveness of disjunctive cuts in solving several large-scale problem instances from the literature. The results are compared to the computational results of disjunctive cuts based on the subproblem space of the formulation and it is shown that the two methods are equivalently effective on the test instances.     

LaGO: a (heuristic) Branch and Cut algorithm for nonconvex MINLPs

We present a Branch and Cut algorithm of the software package LaGO to solve nonconvex mixed-integer nonlinear programs (MINLPs). A linear outer approximation is constructed from a convex relaxation of the problem. Since we do not require an algebraic representation of the problem, reformulation techniques for the construction of the convex relaxation cannot be applied, and we are restricted to sampling techniques in case of nonquadratic nonconvex functions. The linear relaxation is further improved by mixed-integer-rounding cuts. Also box reduction techniques are applied to improve efficiency. Numerical results on medium size test problems are presented to show the efficiency of the method.     

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.     

Valid inequalities and restrictions for stochastic programming problems with first order stochastic dominance constraints

Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance constraints can be solved by linear programming. However, problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of the associated feasible regions. In this paper we consider a mixed 0–1 linear programming formulation of a discrete first order constrained optimization model and present a relaxation based on second order constraints. We derive some valid inequalities and restrictions by employing the probabilistic structure of the problem. We also generate cuts that are valid inequalities for the disjunctive relaxations arising from the underlying combinatorial structure of the problem by applying the lift-and-project procedure. We describe three heuristic algorithms to construct feasible solutions, based on conditional second order constraints, variable fixing, and conditional value at risk. Finally, we present numerical results for several instances of a real world portfolio optimization problem. This research was supported by the NSF awards DMS-0603728 and DMI-0354678.     

Higher-order cover cuts from zero–one knapsack constraints augmented by two-sided bounding inequalities

Extending our work on second-order cover cuts [F. Glover, H.D. Sherali, Second-order cover cuts, Mathematical Programming (ISSN: 0025-5610 1436-4646) (2007), doi:10.1007/s10107-007-0098-4. (Online)], we introduce a new class of higher-order cover cuts that are derived from the implications of a knapsack constraint in concert with supplementary two-sided inequalities that bound the sums of sets of variables. The new cuts can be appreciably stronger than the second-order cuts, which in turn dominate the classical knapsack cover inequalities. The process of generating these cuts makes it possible to sequentially utilize the second-order cuts by embedding them in systems that define the inequalities from which the higher-order cover cuts are derived. We characterize properties of these cuts, design specialized procedures to generate them, and establish associated dominance relationships. These results are used to devise an algorithm that generates all non-dominated higher-order cover cuts, and, in particular, to formulate and solve suitable separation problems for deriving a higher-order cut that deletes a given fractional solution to an underlying continuous relaxation. We also discuss a lifting procedure for further tightening any generated cut, and establish its polynomial-time operation for unit-coefficient cuts. A numerical example is presented that illustrates these procedures and the relative strength of the generated non-redundant, non-dominated higher-order cuts, all of which turn out to be facet-defining for this example. Some preliminary computational results are also presented to demonstrate the efficacy of these cuts in comparison with lifted minimal cover inequalities for the underlying knapsack polytope.     

Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra

We present a unifying framework to establish a lower bound on the number of semidefinite-programming-based lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by Lovász and Schrijver and have been used usually implicitly in the previous lower-bound analyses. In this paper, we formalize the lift-and-project commutative maps and propose a general framework for lower-bound analysis, in which we can recapture many of the previous lower-bound results on the lift-and-project ranks.     

A heuristic to generate rank-1 GMI cuts

Gomory mixed-integer (GMI) cuts are among the most effective cutting planes for general mixed-integer programs (MIP). They are traditionally generated from an optimal basis of a linear programming (LP) relaxation of a MIP. In this paper we propose a heuristic to generate useful GMI cuts from additional bases of the initial LP relaxation. The cuts we generate have rank one, i.e., they do not use previously generated GMI cuts. We demonstrate that for problems in MIPLIB 3.0 and MIPLIB 2003, the cuts we generate form an important subclass of all rank-1 mixed-integer rounding cuts. Further, we use our heuristic to generate globally valid rank-1 GMI cuts at nodes of a branch-and-cut tree and use these cuts to solve a difficult problem from MIPLIB 2003, namely timtab2, without using problem-specific cuts.     

Surrogate-RLT cuts for zero–one integer programs

In this paper, we consider the class of 0–1 integer problems and develop an effective cutting plane algorithm that gives valid inequalities called surrogate-RLT cuts (SR cuts). Here we implement the surrogate constraint analysis along with the reformulation–linearization technique (RLT) to generate strong valid inequalities. In this approach, we construct a tighter linear relaxation by augmenting SR cuts to the problem. The level-\(d\) SR closure of a 0–1 integer program is the polyhedron obtained by intersecting all the SR cuts obtained from RLT polyhedron formed over each set of \(d\) variables with its initial formulation. We present an algorithm for approximately optimizing over the SR closure. Finally, we present the computational result of SR cuts for solving 0–1 integer programming problems of well-known benchmark instances from MIPLIB 3.0.     

Approximate fixed-rank closures of covering problems

Consider a 0/1 integer program min{c^Tx :Ax≥b, x ∈ {0,1}ⁿ} where A is nonnegative. We show that if the number of minimal covers of Ax≥b is polynomially bounded, then for any ε>0 and any fixed q, there is a polynomially large lift-and-project relaxation whose value is at least (1−ε) times the value of the rank ≤q relaxation. A special case of this result is that given by set-covering problems, or, generally, problems where the coefficients in A and b are bounded. This research was partially funded by NSF awards ITR:CCR-0213848 and DMI-0200221 formerly: Set covering problems and Chvátal-Gomory cuts     

Experiments in integer programming

A hybrid algorithm to solve large scale zero–one integer programming problems has been developed. The algorithm combines branch-and-bound, enumeration and cutting plane techniques. Mixed-integer cuts are generated in the initial phase of the algorithm and added to the L.P. Benders cuts are derived and used implicitly but, except for the cut from the initial LP, are not stored. The algorithm has been implemented on an experimental basis in MPSX/370 using its Extended Control Language and Algorithmic Tools. A computational study based on five well-known difficult test problems and on three practical problems with up to 2000 zer–one variables shows that the hybrid code compares favorably with MIP/370 and with results published for other algorithms.     

An application of the Lovász–Schrijver <Emphasis Type="Italic">M</Emphasis>(<Emphasis Type="Italic">K</Emphasis>, <Emphasis Type="Italic">K</Emphasis>) operator to the stable set problem

Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.      

Valid inequalities for mixed integer linear programs

This tutorial presents a theory of valid inequalities for mixed integer linear sets. It introduces the necessary tools from polyhedral theory and gives a geometric understanding of several classical families of valid inequalities such as lift-and-project cuts, Gomory mixed integer cuts, mixed integer rounding cuts, split cuts and intersection cuts, and it reveals the relationships between these families. The tutorial also discusses computational aspects of generating the cuts and their strength. Supported by NSF grant DMI-0352885, ONR grant N00014-03-1-0188 and ANR grant BLAN06-1-138894.     

Some Fundamental Properties of Successive Convex Relaxation Methods on LCP and Related Problems

General successive convex relaxation methods (SRCMs) can be used to compute the convex hull of any compact set, in an Euclidean space, described by a system of quadratic inequalities and a compact convex set. Linear complementarity problems (LCPs) make an interesting and rich class of structured nonconvex optimization problems. In this paper, we study a few of the specialized lift-and-project methods and some of the possible ways of applying the general SCRMs to LCPs and related problems.