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


For a given sequence {\bf a} = [α12, … , αNN+1] of N+1 positive integers, we consider the parametric knapsack problem α1x12 x2+·s+αN xNN+1xN+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 xi 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


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


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.


  loans online . What makes Viagra Strips better than other forms of this medicine is its easiness of usage.