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.     

A relax-and-cut framework for Gomory mixed-integer cuts

Gomory mixed-integer cuts (GMICs) are widely used in modern branch-and-cut codes for the solution of mixed-integer programs. Typically, GMICs are iteratively generated from the optimal basis of the current linear programming (LP) relaxation, and immediately added to the LP before the next round of cuts is generated. Unfortunately, this approach is prone to instability. In this paper we analyze a different scheme for the generation of rank-1 GMICs read from a basis of the original LP—the one before the addition of any cut. We adopt a relax-and-cut approach where the generated GMICs are not added to the current LP, but immediately relaxed in a Lagrangian fashion. Various elaborations of the basic idea are presented, that lead to very fast—yet accurate—variants of the basic scheme. Very encouraging computational results are presented, with a comparison with alternative techniques from the literature also aimed at improving the GMIC quality. We also show how our method can be integrated with other cut generators, and successfully used in a cut-and-branch enumerative framework.     

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.     

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.     

On the strength of Gomory mixed-integer cuts as group cuts

Gomory mixed-integer (GMI) cuts generated from optimal simplex tableaus are known to be useful in solving mixed-integer programs. Further, it is well-known that GMI cuts can be derived from facets of Gomory’s master cyclic group polyhedron and its mixed-integer extension studied by Gomory and Johnson. In this paper we examine why cutting planes derived from other facets of master cyclic group polyhedra (group cuts) do not seem to be as useful when used in conjunction with GMI cuts. For many practical problem instances, we numerically show that once GMI cuts from different rows of the optimal simplex tableau are added to the formulation, all other group cuts from the same tableau rows are satisfied.     

On the complexity of cutting-plane proofs using split cuts

We prove a monotone interpolation property for split cuts which, together with results from Pudlák (1997) [20], implies that cutting-plane proofs which use split cuts (or, equivalently, mixed-integer rounding cuts or Gomory mixed-integer cuts) have exponential length in the worst case.     

Testing cut generators for mixed-integer linear programming

In this paper, a methodology for testing the accuracy and strength of cut generators for mixed-integer linear programming is presented. The procedure amounts to random diving towards a feasible solution, recording several kinds of failures. This allows for a ranking of the accuracy of the generators. Then, for generators deemed to have similar accuracy, statistical tests are performed to compare their relative strength. An application on eight Gomory cut generators and six Reduce-and-Split cut generators is given. The problem of constructing benchmark instances for which feasible solutions can be obtained is also addressed. Supported by ONR grant N00014-09-1-0033.     

Valid inequalities based on the interpolation procedure

We study the interpolation procedure of Gomory and Johnson (1972), which generates cutting planes for general integer programs from facets of cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We compare inequalities generated by this procedure with mixed-integer rounding (MIR) based inequalities discussed in Dash and Gunluk (2003). We first analyze and extend the shooting experiment described in Gomory, Johnson and Evans. We show that MIR based inequalities dominate inequalities generated by the interpolation procedure in some important cases. We also show that the Gomory mixed-integer cut is likely to dominate any inequality generated by the interpolation procedure in a certain probabilistic sense. We also generalize a result of Cornuéjols, Li and Vandenbussche (2003) on comparing the strength of the Gomory mixed-integer cut with related inequalities.     

A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting

The one-dimensional cutting stock problem (1D-CSP) and the two-dimensional two-stage guillotine constrained cutting problem (2D-2CP) are considered in this paper. The Gilmore–Gomory models of these problems have very strong continuous relaxations providing a good bound in an LP-based solution approach. In recent years, there have been several efforts to attack the one-dimensional problem by LP-based branch-and-bound with column generation (called branch-and-price) and by general-purpose Chvátal–Gomory cutting planes. In this paper we investigate a combination of both approaches, i.e., the LP relaxation at each branch-and-price node is strengthened by Chvátal–Gomory and Gomory mixed-integer cuts. The branching rule is that of branching on variables of the Gilmore–Gomory formulation. Tests show that, for 1D-CSP, general-purpose cuts are useful only in exceptional cases. However, for 2D-2CP their combination with branching is more effective than either approach alone and mostly better than other methods from the literature.     

Valid inequalities based on simple mixed-integer sets

In this paper we use facets of simple mixed-integer sets with three variables to derive a parametric family of valid inequalities for general mixed-integer sets. We call these inequalities two-step MIR inequalities as they can be derived by applying the simple mixed-integer rounding (MIR) principle of Wolsey (1998) twice. The two-step MIR inequalities define facets of the master cyclic group polyhedron of Gomory (1969). In addition, they dominate the strong fractional cuts of Letchford and Lodi (2002).     

Mixed-Integer Cuts from Cyclic Groups

We analyze a separation procedure for Mixed-Integer Programs related to the work of Gomory and Johnson on interpolated subadditive functions. This approach has its roots in the Gomory-Johnson characterization on the master cyclic group polyhedron. To our knowledge, the practical benefit that can be obtained by embedding interpolated subadditive cuts in a cutting plane algorithm was not investigated computationally by previous authors. In this paper we compute, for the first time, the lower bound value obtained when adding (implicitly) all the interpolated subadditive cuts that can be derived from the individual rows of an optimal LP tableau, thus approximating the optimization over the intersection of the Gomory corner polyhedron with the LP relaxation of the original problem formulation. The computed bound is compared with that obtained when only Gomory mixed-integer cuts are used, on a very large test-bed of MIP 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.     

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.     

Lifting inequalities: a framework for generating strong cuts for nonlinear programs

In this paper, we introduce the first generic lifting techniques for deriving strong globally valid cuts for nonlinear programs. The theory is geometric and provides insights into lifting-based cut generation procedures, yielding short proofs of earlier results in mixed-integer programming. Using convex extensions, we obtain conditions that allow for sequence-independent lifting in nonlinear settings, paving a way for efficient cut-generation procedures for nonlinear programs. This sequence-independent lifting framework also subsumes the superadditive lifting theory that has been used to generate many general-purpose, strong cuts for integer programs. We specialize our lifting results to derive facet-defining inequalities for mixed-integer bilinear knapsack sets. Finally, we demonstrate the strength of nonlinear lifting by showing that these inequalities cannot be obtained using a single round of traditional integer programming cut-generation techniques applied on a tight reformulation of the problem.      

On mixed-integer sets with two integer variables

We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined in 2010). We extend this result to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables if the coefficients of the integer variables form a matrix of rank 2. We also present an alternative characterization of the crooked cross cut closure of mixed-integer sets similar to the one on the equivalence of different definitions of split cuts presented in Cook et al. (1990) [4]. This characterization implies that crooked cross cuts dominate the 2-branch split cuts defined by Li and Richard (2008) [8]. Finally, we extend our results to mixed-integer sets that are defined as the set of points (with some components being integral) inside a closed, bounded and convex set.     

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.     

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.     

Foundation-penalty cuts for mixed-integer programs

We propose a new class of foundation-penalty (FP) cuts for MIPs that are easy to generate by exploiting routine penalty calculations. Their underlying concept generalizes the lifting process and provides derivations of major classical cuts. (Gomory cuts arise from low level FP cuts by simply ‘plugging in’ standard penalties.)     

Partial convexification cuts for 0–1 mixed-integer programs

In this research, we propose a new cut generation scheme based on constructing a partial convex hull representation for a given 0–1 mixed-integer programming problem by using the reformulation–linearization technique (RLT). We derive a separation problem that projects the extended space of the RLT formulation into the original space, in order to generate a cut that deletes a current fractional solution. Naturally, the success of such a partial convexification based cutting plane scheme depends on the process used to tradeoff the strength of the cut derived and the effort expended. Accordingly, we investigate several variable selection rules for performing this convexification, along with restricted versions of the accompanying separation problems, so as to be able to derive strong cuts within a reasonable effort. We also develop a strengthening procedure that enhances the generated cut by considering the binariness of the remaining unselected 0–1 variables. Finally, we present some promising computational results that provide insights into implementing the proposed cutting plane methodology.