About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Mathematical Programming
Paper
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.