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

• 成果类型: Article
• 署名作者: Dash, Sanjeeb; Dobbs, Neil B.; Guenluek, Oktay; Nowicki, Tomasz J.; Swirszcz, Grzegorz M.
• 署名单位: International Business Machines (IBM); IBM USA; University of Helsinki
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0654-z
• 发表日期: 2014
• 页码: 483-508
• 关键词: nonsymmetric convex-bodies; variables; plane

摘要

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 -dimensional lattice-free sets, we prove that for every integer there exists a positive integer such that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with integer variables is a -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 , for which all facets of polyhedral mixed-integer sets with integer variables can be generated as -branch split cuts, grows exponentially with . In particular, when , we observe that not all facet-defining inequalities are 6-branch split cuts.