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

Autor: Sanjeeb Dash, Oktay Günlük, Neil Dobbs, Grzegorz Świrszcz, Tomasz Nowicki
Rok vydání: 2013
Předmět:
Zdroj: Mathematical Programming. 145:483-508
ISSN: 1436-4646
0025-5610
DOI: 10.1007/s10107-013-0654-z
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: