Name
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s10107-013-0654-z | Mathematical Programming: Series A and B |
Keywords | Field | DocType |
90c11,90c60 | Integer,Discrete mathematics,Mathematical optimization,Combinatorics,Lattice (order),Existential quantification,Convex hull,Integer programming,Mathematics | Journal |
Volume | Issue | ISSN |
145 | 1-2 | 1436-4646 |
Citations | PageRank | References |
2 | 0.38 | 16 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sanjeeb Dash | 1 | 448 | 32.93 |
| Neil B. Dobbs | 2 | 2 | 0.38 |
| Oktay GüNlüK | 3 | 502 | 41.29 |
| Tomasz Nowicki | 4 | 45 | 3.61 |
| Grzegorz Swirszcz | 5 | 61 | 8.62 |