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


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 2O(n) n2.5n (with polynomial dependence on the remaining parameters). In this work, we give a 2O(n) nn 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


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 x1, … ,xt ∈ P and positive integers n1, … ,nt such that n1+ … +nt=k and w=n1x1+ … +ntxt.
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


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.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.