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.     

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.     

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.     

DRL*: A hierarchy of strong block-decomposable linear relaxations for 0-1 MIPs

In this paper we introduce DRL*, a new hierarchy of linear relaxations for 0-1 mixed integer linear programs (MIPs), based on the idea of Reformulation-Linearization, and explore its links with the Lift-and-Project (L&P) hierarchy and the Sherali-Adams (RLT) hierarchy. The relaxations of the new hierarchy are shown to be intermediate in strength between L&P and RLT relaxations, and examples are shown for which it leads to significantly stronger bounds than those obtained from Lift-and-Project relaxations. On the other hand, as opposed to the RLT relaxations, a key advantage of the DRL* relaxations is that they feature a decomposable structure when formulated in extended space, therefore lending themselves to more efficient solution algorithms by properly exploiting decomposition. Links between DRL* and both the L&P and RLT hierarchies are further explored, and those constraints which should be added to the rank d L&P relaxation (resp to the rank d RLT relaxation) to make it coincide with the rank d DRL* relaxation (resp: to the rank d RLT relaxation) are identified. Furthermore, a full characterization of those 0-1 MIPs for which the DRL* and RLT relaxations coincide is obtained. As an application, we show that both the RLT and DRL* relaxations are the same up to rank d for the problem of optimizing a pseudoboolean function of degree d over a polyhedron. We report computational results comparing the strengths of the rank 2 L&P, DRL* and RLT relaxations. Impact on possible improved efficiency in computing some bounds for the quadratic assignment problem and other directions for future research are suggested in the conclusions.     

Strong lift-and-project cutting planes for the stable set problem

A great deal of research has been focusing, since the early seventies, on finding strong relaxations for the stable set problem. Polyhedral combinatorics techniques have been at first developed to strengthen the natural linear formulation. Afterward, strong semidefinite programming relaxations have been deeply investigated. Nevertheless, the resulting integer programming (IP) algorithms cannot be regarded as being quite successful in practice, as most of the relaxations give rise to one out of two extreme situations: either provide weak bounds at low computational cost or give good bounds (sometimes excellent) but too demanding to compute. In this paper we present a method to bridge such a gap. In particular, a new lift-and-project relaxation is obtained by a problem-specific variant of the lifting operator M(K, K) by Lovász and Schrijver, combined with Benders decomposition. This yields strong cutting planes, generated by solving a cut generating linear program. An extensive computational experience shows that embedding these cuts in a branch-and-cut framework significantly reduces the size of the enumeration trees as well as the CPU times with respect to state-of-the-art IP algorithms.     

Intersection cuts for convex mixed integer programs from translated cones

We develop a general framework for linear intersection cuts for convex integer programs with full-dimensional feasible regions by studying integer points of their translated tangent cones, generalizing the idea of Balas (1971). For proper (i.e, full-dimensional, closed, convex, pointed) translated cones with fractional vertices, we show that under certain mild conditions all intersection cuts are indeed valid for the integer hull, and a large class of valid inequalities for the integer hull are intersection cuts, computable via polyhedral approximations. We also give necessary conditions for a class of valid inequalities to be tangent halfspaces of the integer hull of proper translated cones. We also show that valid inequalities for non-pointed regular translated cones can be derived as intersection cuts for associated proper translated cones under some mild assumptions.     

A note on the split rank of intersection cuts

In this note, we present a simple geometric argument to determine a lower bound on the split rank of intersection cuts. As a first step of this argument, a polyhedral subset of the lattice-free convex set that is used to generate the intersection cut is constructed. We call this subset the restricted lattice-free set. It is then shown that élog₂ (l)ù{\lceil \log_2 (l)\rceil} is a lower bound on the split rank of the intersection cut, where l is the number of integer points lying on the boundary of the restricted lattice-free set satisfying the condition that no two points lie on the same facet of the restricted lattice-free set. The use of this result is illustrated by obtaining a lower bound of élog₂( n+1) ù{\lceil \log_2( n+1) \rceil} on the split rank of n-row mixing inequalities.     

More on block intersection polynomials and new applications to graphs and block designs

The concept of intersection numbers of order r for t-designs is generalized to graphs and to block designs which are not necessarily t-designs. These intersection numbers satisfy certain integer linear equations involving binomial coefficients, and information on the non-negative integer solutions to these equations can be obtained using the block intersection polynomials introduced by P.J. Cameron and the present author. The theory of block intersection polynomials is extended, and new applications of these polynomials to the studies of graphs and block designs are obtained. In particular, we obtain a new method of bounding the size of a clique in an edge-regular graph with given parameters, which can improve on the Hoffman bound when applicable, and a new method for studying the possibility of a graph with given vertex-degree sequence being an induced subgraph of a strongly regular graph with given parameters.     

On t-branch split cuts for mixed-integer programs

In this paper we study the t-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). They presented a family of mixed-integer programs with n integer variables and a single continuous variable and conjectured that the convex hull of integer solutions for any n has unbounded rank with respect to (n?1)-branch split cuts. It was shown earlier by Cook et al. (Math Program 47:155–174, 1990) that this conjecture is true when n = 2, and Li and Richard proved the conjecture when n = 3. In this paper we show that this conjecture is also true for all n > 3.     

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.     

Using rank-1 lift-and-project closures to generate cuts for 0–1 MIPs, a computational investigation

Various techniques for building relaxations and generating valid inequalities for pure or mixed integer programming problems without special structure are reviewed and compared computationally. Besides classical techniques such as Gomory cuts, Mixed Integer Rounding cuts, lift-and-project and reformulation–linearization techniques, a new variant is also investigated: the use of the relaxation corresponding to the intersection of simple disjunction polyhedra (i.e. the so-called elementary closure of lift-and-project cuts). Systematic comparative computational results are reported on series of test problems including multidimensional knapsack problems (MKP) and MIPLIB test problems. From the results obtained, the relaxation based on the elementary closure of lift-and-project cuts appears to be one of the most promising.     

Better <Emphasis Type="Italic">s</Emphasis>–<Emphasis Type="Italic">t</Emphasis>-tours by Gao trees

We consider the s–t-path TSP: given a finite metric space with two elements s and t, we look for a path from s to t that contains all the elements and has minimum total distance. We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous algorithms, we solve the natural LP relaxation and represent an optimum solution \(x^*\) as a convex combination of spanning trees. Gao showed that there exists a spanning tree in the support of \(x^*\) that has only one edge in each narrow cut [i.e., each cut C with \(x^*(C)<2\)]. Our main theorem says that the spanning trees in the convex combination can be chosen such that many of them are such “Gao trees” simultaneously at all sufficiently narrow cuts.     

Equivalences and the complete hierarchy of intersection graphs of paths in a tree

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex in G, such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that have an (h,s,t)-representation is denoted by [h,s,t]. It is well known that the class of chordal graphs corresponds to the class [3, 3, 1]. Moreover, it was proved by Jamison and Mulder that chordal graphs correspond to orthodox-[3, 3, 1] graphs defined below.In this paper, we investigate the class of [h,2,t] graphs, i.e., the intersection graphs of paths in a tree. The [h,2,1] graphs are also known as path graphs [F. Gavril, A recognition algorithm for the intersection graphs of paths in trees, Discrete Math. 23 (1978) 211-227] or VPT graphs [M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Math. 55 (1985) 151-159], and [h,2,2] graphs are known as the EPT graphs. We consider variations of [h,2,t] by three main parameters: h, t and whether the graph has an orthodox representation. We give the complete hierarchy of relationships between the classes of weakly chordal, chordal, [h,2,t] and orthodox-[h,2,t] graphs for varied values of h and t.     

Boxicity of Leaf Powers

The boxicity of a graph G, denoted as boxi(G), is defined as the minimum integer t such that G is an intersection graph of axis-parallel t-dimensional boxes. A graph G is a k-leaf power if there exists a tree T such that the leaves of the tree correspond to the vertices of G and two vertices in G are adjacent if and only if their corresponding leaves in T are at a distance of at most k. Leaf powers are used in the construction of phylogenetic trees in evolutionary biology and have been studied in many recent papers. We show that for a k-leaf power G, boxi(G)??? k?1. We also show the tightness of this bound by constructing a k-leaf power with boxicity equal to k?1. This result implies that there exist strongly chordal graphs with arbitrarily high boxicity which is somewhat counterintuitive.     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

Integer programming and convex analysis: Intersection cuts from outer polars

Recently a new, geometrically motivated approach was proposed [1] for integer programming, based on generating intersection cuts from some convex setS whose interior contains the linear programming optimum but no feasible integer point. Larger sets tend to produce stronger cuts, and in this paper convex analysis is used to construct sets as large as possible within the above requirements. Information is generated from all problem constraints within a unit cubeK containing The key concept is that of outer polars, viewed as maximal convex extensions of the ballB circumscribingK, relative to the problem constraints. The outer polarF ^* of the feasible setF overB is shown to be a convex set whose boundary contains all feasible vertices ofK, and whose interior contains no feasible integer point. The existence of a dual correspondence betweenF andF ^*, and the fact that polarity is inclusion-reversing, leads to a dualization of operations onF. As one possible procedure based on this approach, we construct a generalized intersection cut, that can be strengthened whenever some vertex ofF is cut off. This makes it possible to fruitfully combine intersection cuts with implicit enumeration or branch-and-bound. While valid for arbitrary integer programs, the theory developed here is relevant primarily to (pure or mixed-integer) 0–1 problems. Other topics discussed include: generalized polars, intersection cuts from related problems, connections with asymptotic theory.This paper was presented at the 7th Mathematical Programming Symposium, 1970, The Hague, The Netherlands.The research underlying this paper was partially supported by the National Science Foundation under grant GP-31699 and by the Office of Naval Research under contract N00014-67-A-0314-0007 NR 047-048.     

Minimum cut bases in undirected networks

Given an undirected, connected network G=(V,E) with weights on the edges, the cut basis problem is asking for a maximal number of linear independent cuts such that the sum of the cut weights is minimized. Surprisingly, this problem has not attained as much attention as another graph theoretic problem closely related to it, namely, the cycle basis problem. We consider two versions of the problem: the unconstrained and the fundamental cut basis problem.For the unconstrained case, where the cuts in the basis can be of an arbitrary kind, the problem can be written as a multiterminal network flow problem, and is thus solvable in strongly polynomial time. In contrast, the fundamental cut basis problem, where all cuts in the basis are obtained by deleting an edge, each from a spanning tree T, is shown to be NP-hard. In this proof, we also show that a tree which induces the minimum fundamental cycle basis is also an optimal solution for the minimum fundamental cut basis problem in unweighted graphs.We present heuristics, integer programming formulations and summarize first experiences with numerical tests.     

Pathwidth, trees, and random embeddings

We prove that, for every integer k≥1, every shortest-path metric on a graph of pathwidth k embeds into a distribution over random trees with distortion at most c=c(k), independent of the graph size. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair [12] states that for every minor-closed family of graphs F, there is a constant c(F) such that the multi-commodity max-flow/min-cut gap for every flow instance on a graph from F is at most c(F). The preceding embedding theorem is used to prove this conjecture whenever the family F does not contain all trees.