Monday, 16:15 - 16:40 h, Room: H 2032


Oktay Günlük
Lattice-free sets, branching disjunctions, and mixed-integer programming

Coauthors: Sanjeeb Dash, Neil B. Dobbs, Tomasz J. Nowicki, Grzegorz M. Swirszcz


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.
Moreover, this number t does not depend on the data defining the polyhedral set and is bounded by a function of the dimension n only.
We use this result to give a finitely convergent 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 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.


Talk 3 of the invited session Mon.3.H 2032
"Trends in mixed integer programming I" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  The majority of financial loan companies provide the service of getting Payday Loans North Carolina for U.S. citizens. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.