**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**

**Abstract:**

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"** [...]