Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming

Abstract

In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (Discret Optim 5:724-734, 2008). By analyzing n -dimensional lattice-free sets, we prove that for every integer n there exists a positive integer t such 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. We use this result to give a finite cutting-plane algorithm to solve mixed-integer programs. We also show that the minimum value t, for which all facets of polyhedral mixed-integer sets with n integer variables can be generated 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. © 2013 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.