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.

By: Sanjeeb Dash, Neil B. Dobbs, Oktay Günlük, Tomasz J. Nowicki, Grzegorz M. Swirszcz

Published in: RC25212 in 2011


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .