## Invited Session Mon.3.H 2032

#### Monday, 15:15 - 16:45 h, Room: H 2032

**Cluster 11: Integer & mixed-integer programming** [...]

### Trends in mixed integer programming I

**Chair: Andrea Lodi and Robert Weismantel**

**Monday, 15:15 - 15:40 h, Room: H 2032, Talk 1**

**Giacomo Nannicini**

On the safety of Gomory cut generators

**Coauthors: Gérard Cornuéjols, Francois Margot**

**Abstract:**

Gomory mixed-integer cuts are one of the key components

in branch-and-cut solvers for mixed-integer linear programs. The

textbook formula for generating these cuts is not used directly in

open-source and commercial software due to the limited numerical

precision of the computations: Additional steps are performed to avoid

the generation of invalid cuts. This paper studies the impact of some

of these steps on the safety of Gomory mixed-integer cut

generators. As the generation of invalid cuts is a relatively rare

event, the experimental design for this study is particularly

important. We propose an experimental setup that allows statistically

significant comparisons of generators. We also propose a parameter

optimization algorithm and use it to find a Gomory mixed-integer cut generator that is as safe as a benchmark cut generator from a commercial solver even though it rejects much fewer cuts.

**Monday, 15:45 - 16:10 h, Room: H 2032, Talk 2**

**Utz-Uwe Haus**

Split cuts for robust and generalized mixed-integer programming

**Coauthor: Frank Pfeuffer**

**Abstract:**

Robust Mixed-Integer optimization problems are conventionally solved by

reformulation as non-robust problems. We propose a direct method to

separate split cuts for robust mixed-integer programs with polyhedral

uncertainty sets, for both worst-case as well as best-case robustness.

The method generalizes the well-known cutting plane procedure of Balas.

Computational experiments show that applying cutting planes directly is

favorable to the reformulation approach. It is thus viable to solve

robust MIP problems in a branch-and-cut framework using a Generalized

Linear Programming oracle.

**Monday, 16:15 - 16:40 h, Room: H 2032, Talk 3**

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