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.


  personal loans online . One of the main advantages of Sovaldi is that it can be used by patients belonging to all 4 genotypes. Buy Sovaldi is a very strong drug, and as all of them, it has a number of side effects that can be caused.