Lattice-Free Sets, Branching Disjunctions, and Mixed-Integer Programming

In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and structured disjunctive cuts, especially the t-branch split cuts introduced by Li and Richard (2008). By analyzing n-dimensional lattice-free sets, we prove that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with n integer variables is a t-branch split cut for some positive integer t which is a function of n, and not of the data defining the polyhedral set. We use this result to give a finitely convergent, pure cutting-plane algorithm to solve mixed-integer programs. We also show that the minimum value t, for which all facets of n-dimensional polyhedral mixed-integer sets can be expressed as t-branch split cuts, grows exponentially with n. In particular, when n = 3, we observe that not all facet-defining inequalities are 6-branch split cuts. We analyze the cases when n = 2 and n = 3 in detail, and show that an explicit classification of maximal lattice-free sets is not necessary to express facet-defining inequalities as branching disjunctions with a small number of atoms.