Lattice-free sets, branching disjunctions, and mixed-integer programming
Sanjeeb Dash, Neil Dobbs, Tomasz Nowicki, Grzegorz Świrszcz · 2012
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 withn integer variables is a t-branch split cut for some positive integer t. Moreover, this number t does not depend on the data defining the polyhedral set and is bounded by a function of the dimension n only. We use this result to give a finitely convergent 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 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.