## Invited Session Fri.2.H 2032

#### Friday, 13:15 - 14:45 h, Room: H 2032

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

### Integer points in polytopes I

**Chair: Michael Joswig and Günter M. Ziegler**

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

**Jesus Antonio De Loera**

Top Ehrhart coefficients of knapsack problems

**Coauthors: V. Baldoni, N. Berline, M. Koeppe, M. Vergne**

**Abstract:**

For a given sequence *{\bf a} = [α*_{1},α_{2}, … , α_{N},α_{N+1}] of *N+1* positive integers, we consider the parametric knapsack problem *α*_{1}x_{1}+α_{2} x_{2}+·s+α_{N} x_{N}+α_{N+1}x_{N+1}=t, where

right-hand side~*t* is a varying non-negative integer.

It is well-known that the number *E*_{\bf a}(t) of solutions in non-negative integers *x*_{i} is given by a quasi-polynomial function of~*t* of degree *N*. For a fixed number *k*, we give a new polynomial time algorithm to compute the highest *k+1* coefficients of the quasi-polynomial *E*_{\bf a}(t) represented as step polynomials of~*t*.

%This is joint work with V. Baldoni, N. Berline, M. Koeppe, and M. Vergne.

**Friday, 13:45 - 14:10 h, Room: H 2032, Talk 2**

**Joseph Gubeladze**

Continuous evolution of lattice polytopes

**Abstract:**

The sets of lattice points in *normal polytopes*, a.k.a. the *homogeneous Hilbert bases*, model (continuous) convex polytopes. The concept of a normal polytope does not reduce to simpler properties - known attempts include unimodular triangulation and integral Carathéodory properties. To put it in other words, normal polytopes are the monads of quantization of convex shapes. Much work went into understanding special classes of normal polytopes, motivated from combinatorial commutative algebra, toric algebraic geometry, integer programming. In this talk we define a space of *all* normal polytopes. It is generated by certain dynamics, supported by these polytopes. The corresponding evolution process of normal polytopes was used back in the late 1990s to find counterexamples to the mentioned unimodular triangulation and integral Carathéodory properties. On the one hand, this space offers a global picture of the interaction of the integer lattice with normal polytopes. On the other hand, singular points of the space - some known to exist and some conjectural - represent normal point configurations with challenging arithmetic properties.

**Friday, 14:15 - 14:40 h, Room: H 2032, Talk 3**

**Gennadiy Averkov**

Lattice-free integer polyhedra and their application in cutting-plane theory

**Coauthors: Christian Wagner, Robert Weismantel**

**Abstract:**

In this talk I will discuss the class of inclusion-maxial lattice-free integer polyhedra. The class is finite in any dimension (modulo transformations that preserve the integer lattice). This finiteness result was proved in a joint work with Christian Wagner and Robert Weismantel and also, independently, by Benjamin Nill and Günter M. Ziegler. I will also discuss consequences of the result for the cutting-plane theory of mixed-integer linear programs.