## Invited Session Thu.1.H 2033

#### Thursday, 10:30 - 12:00 h, Room: H 2033

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

### New developments in integer programming

**Chair: Andreas S. Schulz**

**Thursday, 10:30 - 10:55 h, Room: H 2033, Talk 1**

**Daniel Dadush**

Convex minimization over the integers

**Abstract:**

In the seminal works of Lenstra (MOR `83) and Kannan (MOR `87), it was shown that any *n* variable Integer Linear Program (ILP) can be solved in time *2*^{O(n)} n^{2.5n} (with polynomial dependence on the remaining parameters). In this work, we give a *2*^{O(n)} n^{n} time algorithm to minimize a convex function over the integer points in any *n* dimensional convex body, thereby improving the computational complexity of the Integer Programming Problem. The algorithm yields the first exact algorithm for Convex IP and the current fastest algorithm for ILP. For our techniques, we rely on new insights in the geometry of numbers as well as new algorithms for lattice problems.

**Thursday, 11:00 - 11:25 h, Room: H 2033, Talk 2**

**Guus Regts**

Polyhedra with the integer Carathéodory property

**Coauthor: Dion C. Gijswijt**

**Abstract:**

A polyhedron *P* has the Integer Carathéodory Property if the following holds. For any positive integer *k* and any integer vector *w ∈ kP*, there exist affinely independent integer vectors *x*_{1}, … ,x_{t} ∈ P and positive integers *n*_{1}, … ,n_{t} such that *n*_{1}+ … +n_{t}=k and *w=n*_{1}x_{1}+ … +n_{t}x_{t}.

It was shown by Bruns et. al (W. Bruns, J. Gubeladze, M. Henk, A. Martin, R. Weismantel, A counter example to an integer analogue of Carathéodory's theorem, J. Reine Angew. Math., 510 (1999), pp. 179-185) that the Integer Carathéodory Property is strictly stronger than the integer decomposition property.

In this talk I will show that if *P* is a (poly)matroid base polytope or if *P* is defined by a totally unimodular matrix, then *P* has the Integer Carathéodory Property. For the matroid base polytope this answers a question by Cunningham from 1984.

**Thursday, 11:30 - 11:55 h, Room: H 2033, Talk 3**

**Juliane Dunkel**

A refined Gomory-Chvatal closure for polytopes in the unit cube

**Coauthor: Andreas S. Schulz**

**Abstract:**

We introduce a natural strengthening of Gomory-Chv{á}tal cutting planes for the important class of 0/1-integer programming problems and study the properties of the elementary closure that arises from the new class of cuts. Most notably, we prove that the new closure is polyhedral, we characterize the family of all facet-defining inequalities, and we compare it to elementary closures associated with other cutting-plane procedures.