The triangle closure is a polyhedron

Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron. Although some fairly general results were obtained by Andersen et al. (Math Oper Res 35(1):233–256, 2010) and Averkov (Discret Optimiz 9(4):209–215, 2012), some basic questions have remained unresolved. For example, maximal lattice-free triangles are the natural family to study beyond the family of splits and it has been a standing open problem to decide whether the triangle closure is a polyhedron. In this paper, we show that when the number of integer variables $m=2$ the triangle closure is indeed a polyhedron and its number of facets can be bounded by a polynomial in the size of the input data. The techniques of this proof are also used to give a refinement of necessary conditions for valid inequalities being facet-defining due to Cornuéjols and Margot (Math Program 120:429–456, 2009) and obtain polynomial complexity results about the mixed integer hull.     

Strengthening lattice-free cuts using non-negativity

In recent years there has been growing interest in generating valid inequalities for mixed-integer programs using sets with two or more constraints. In particular, Andersen et al. (2007) [2] and Borozan and Cornuéjols (2009) [3] have studied sets defined by equations that contain exactly one integer variable per row. The integer variables are not restricted in sign. Cutting planes based on this approach have already been computationally studied by Espinoza (2008) [8] for general mixed-integer problems, and there is ongoing computational research in this area.In this paper, we extend the model studied in the earlier papers and require the integer variables to be non-negative. We extend the results in [2] and [3] to our case, and show that cuts generated by their approach can be strengthened by using the non-negativity of the integer variables. In particular, it is possible to obtain cuts which have negative coefficients for some variables.     

On degenerate multi-row Gomory cuts

Borozan and Cornuéjols show that valid inequalities for an infinite relaxation for MIPs, relative to some vertex f of the linear relaxation, are determined by maximal lattice-free convex sets containing f. We show that cuts for the original MIP are given by such sets with f in the interior.     

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.     

Unique lifting of integer variables in minimal inequalities

This paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic variables are continuous; they are derived using the gauge function of maximal lattice-free convex sets. In this paper we study lifting functions for the nonbasic integer variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is equal to the coefficient of the corresponding continuous variable in every minimal lifting (This result first appeared in the proceedings of IPCO 2010). The answer is a nonconvex region that can be obtained as a finite union of convex polyhedra. We then establish a necessary and sufficient condition for the uniqueness of the lifting function.     

A disjunctive cutting plane procedure for general mixed-integer linear programs

In this paper we develop a cutting plane algorithm for solving mixed-integer linear programs with general-integer variables. A novel feature of the algorithm is that it generates inequalities at all γ-optimal vertices of the LP-relaxation at each iteration. The cutting planes generated in the procedure are found by considering a natural generalization of the 0-1 disjunction used by Balas, Ceria, and Cornuéjols in the context of solving binary mixed-integer linear programs [3, 4]. Received: January 1999 / Accepted: March 2000?Published online December 15, 2000     

Minimal cut-generating functions are nearly extreme

We study continuous (strongly) minimal cut generating functions for the model where all variables are integer. We consider both the original Gomory–Johnson setting as well as a recent extension by Y?ld?z and Cornuéjols (Math Oper Res 41:1381–1403, 2016). We show that for any continuous minimal or strongly minimal cut generating function, there exists an extreme cut generating function that approximates the (strongly) minimal function as closely as desired. In other words, the extreme functions are “dense” in the set of continuous (strongly) minimal functions.     

Valid inequalities for MIPs and group polyhedra from approximate liftings

In this paper, we present an approximate lifting scheme to derive valid inequalities for general mixed integer programs and for the group problem. This scheme uses superadditive functions as the building block of integer and continuous lifting procedures. It yields a simple derivation of new and known families of cuts that correspond to extreme inequalities for group problems. This new approximate lifting approach is constructive and potentially efficient in computation. J.-P. P. Richard was supported by NSF grant DMI-348611.     

A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts

We consider mixed integer linear sets defined by two equations involving two integer variables and any number of non-negative continuous variables. We analyze the benefit from adding a non-split inequality on top of the split closure. Applying a probabilistic model, we show that the importance of a type 2 triangle inequality decreases with decreasing lattice width, on average. Our results suggest that this is also true for type 3 triangle and quadrilateral inequalities.     

Lifting two-integer knapsack inequalities

In this paper we discuss the derivation of strong valid inequalities for (mixed) integer knapsack sets based on lifting of valid inequalities for basic knapsack sets with two integer variables (and one continuous variable). The basic polyhedra can be described in polynomial time. We use superadditive valid lifting functions in order to obtain sequence independent lifting. Most of these superadditive functions and valid inequalities are not obtained in polynomial time.     

Intersection cuts for single row corner relaxations

We consider the problem of generating inequalities that are valid for one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic integer variable. This relaxation is related to a simple knapsack set with two integer variables and two continuous variables. We study its facial structure by rewriting it as a constrained two-row model, and prove that all its facets arise from a finite number of maximal \(\left( \mathbb {Z}\times \mathbb {Z}_+\right) \)-free splits and wedges. The resulting cuts generalize both MIR and 2-step MIR inequalities. Then, we describe an algorithm for enumerating all the maximal \(\left( \mathbb {Z}\times \mathbb {Z}_+\right) \)-free sets corresponding to facet-defining inequalities, and we provide an upper bound on the split rank of those inequalities. Finally, we run computational experiments to compare the strength of wedge cuts against MIR cuts. In our computations, we use the so-called trivial fill-in function to exploit the integrality of more non-basic variables. To that end, we present a practical algorithm for computing the coefficients of this lifting function.     

A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting

We study the set of 0–1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP), which generalizes the classical 0–1 knapsack polytope and the 0–1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions using sequence-independent lifting. For problems with a single cardinality constraint, we derive two-dimensional superadditive lifting functions and prove that they are maximal and non-dominated under some mild conditions. We then show that these functions can be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints. Finally, we present preliminary computational results aimed at evaluating the strength of the cuts obtained from sequence-independent lifting with respect to those obtained from sequential lifting.     

On the separation of split cuts and related inequalities

 The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other well-known cuts as special cases. To detect violated split cuts, one has to solve the associated separation problem. The complexity of split cut separation was recently cited as an open problem by Cornuéjols & Li CL01. In this paper we settle this question by proving strong 𝒩𝒫-completeness of separation for split cuts. As a by-product we also show 𝒩𝒫-completeness of separation for several other classes of inequalities, including the MIR-inequalities of Nemhauser and Wolsey and some new inequalities which we call balanced split cuts and binary split cuts. We also strengthen 𝒩𝒫-completeness results of Caprara & Fischetti CF96 (for -cuts) and Eisenbrand E99 (for Chvátal-Gomory cuts). To compensate for this bleak picture, we also give a positive result for the Symmetric Travelling Salesman Problem. We show how to separate in polynomial time over a class of split cuts which includes all comb inequalities with a fixed handle. Received: October 23, 2000 / Accepted: October 03, 2001 Published online: September 5, 2002 Key words. cutting planes – separation – complexity – travelling salesman problem – comb inequalities     

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.     

On the set covering polyhedron of circulant matrices

A well known family of minimally nonideal matrices is the family of the incidence matrices of chordless odd cycles. A natural generalization of these matrices is given by the family of circulant matrices. Ideal and minimally nonideal circulant matrices have been completely identified by Cornuéjols and Novick [G. Cornuéjols, B. Novick, Ideal 0 - 1 matrices, Journal of Combinatorial Theory B 60 (1994) 145–157]. In this work we classify circulant matrices and their blockers in terms of the inequalities involved in their set covering polyhedra. We exploit the results due to Cornuéjols and Novick in the above-cited reference for describing the set covering polyhedron of blockers of circulant matrices. Finally, we point out that the results found on circulant matrices and their blockers present a remarkable analogy with a similar analysis of webs and antiwebs due to Pêcher and Wagler [A. Pêcher, A. Wagler, A construction for non-rank facets of stable set polytopes of webs, European Journal of Combinatorics 27 (2006) 1172–1185; A. Pêcher, A. Wagler, Almost all webs are not rank-perfect, Mathematical Programming Series B 105 (2006) 311–328] and Wagler [A. Wagler, Relaxing perfectness: Which graphs are ‘Almost’ perfect?, in: M. Groetschel (Ed.), The Sharpest Cut, Impact of Manfred Padberg and his work, in: SIAM/MPS Series on Optimization, vol. 4, Philadelphia, 2004; A. Wagler, Antiwebs are rank-perfect, 4OR 2 (2004) 149–152].     

Projected Chvátal–Gomory cuts for mixed integer linear programs

Recent experiments by Fischetti and Lodi show that the first Chvátal closure of a pure integer linear program (ILP) often gives a surprisingly tight approximation of the integer hull. They optimize over the first Chvátal closure by modeling the Chvátal–Gomory (CG) separation problem as a mixed integer linear program (MILP) which is then solved by a general- purpose MILP solver. Unfortunately, this approach does not extend immediately to the Gomory mixed integer (GMI) closure of an MILP, since the GMI separation problem involves the solution of a nonlinear mixed integer program or a parametric MILP. In this paper we introduce a projected version of the CG cuts, and study their practical effectiveness for MILP problems. The idea is to project first the linear programming relaxation of the MILP at hand onto the space of the integer variables, and then to derive Chvátal–Gomory cuts for the projected polyhedron. Though theoretically dominated by GMI cuts, projected CG cuts have the advantage of producing a separation model very similar to the one introduced by Fischetti and Lodi, which can typically be solved in a reasonable amount of computing time. Gérard Cornuéjols was supported in part by NSF grant DMI-0352885, ONR grant N00014-03-1-0188, and ANR grant BLAN 06-1-138894. Matteo Fischetti was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n. FP6-021235-2). Andrea Lodi was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n. FP6-021235-2).     

Tiling Polygons with Lattice Triangles

Given a simple polygon with rational coordinates having one vertex at the origin and an adjacent vertex on the x-axis, we look at the problem of the location of the vertices for a tiling of the polygon using lattice triangles (i.e., triangles which are congruent to a triangle with the coordinates of the vertices being integer). We show that the coordinates of the vertices in any tiling are rationals with the possible denominators odd numbers dependent on the cotangents of the angles in the triangles.     

Generalized intersection cuts and a new cut generating paradigm

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate in a non-recursive fashion cuts that would require several recursive applications of some standard cut generating routine. A procedure is also given for strengthening the coefficients of the integer-constrained variables of a generalized intersection cut. The new cutting plane paradigm yields a new characterization of the closure of intersection cuts and their strengthened variants. This characterization is minimal in the sense that every one of the inequalities it uses defines a facet of the closure.     

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