Abstract
Integer linear programming is a powerful tool to tackle major combinatorial optimization problems. We study various theoretical aspects of integer programming:
Integer programming in fixed dimension. Although in general integer linear programming is NP-hard, there is a polynomial algorithm to solve integer programs with a fixed number of variables (Lenstra’s algorithm). The faster algorithm so far was proposed by F. Eisenbrand. We also study parametric integer programming in fixed dimension, where the right-hand side of the constraint system A x ≤ b is a parameter and allowed to vary.
Cutting planes. Cutting planes is a crucial ingredient of any integer programming algorithm used in practice, and yet, a very challenging topic from the complexity point view. Thus, it was shown that optimizing over the elementary Chvátal closure of a polyhedron is NP-hard, but can be done efficiently if the dimension is fixed.
Integer programming gaps. By the integer programming gap we mean the maximum difference between the optimum of an integer program and the corresponding linear programming relaxation over a predefined family of integer programs. Hence, there is a connexion to the parametric integer programming.
Members
Selected publications
A. Bockmayr, F. Eisenbrand, Cutting planes and the elementary closure in fixed dimension, Mathematics of Operations Research, 26(2):304–312, 2001. [DOI]
F. Eisenbrand, On the membership problem for the elementary closure of a polyhedron, Combinatorica, 19(2):297–300, 1999. [DOI]
F. Eisenbrand, Fast integer programming in fixed dimension, in Algorithms – ESA 2003, vol. 2832 of Lecture Notes in Computer Science, pp. 196–207, 2003. [DOI]
F. Eisenbrand, S. Laue, A linear algorithm for integer programming in the plane, Mathematical Programming 102(2):249–259, 2005. [DOI]
F. Eisenbrand, G. Shmonin, Parametric integer programming in fixed dimension, Mathematics of Operations Research 33(4):839–850, 2008. [DOI]
F. Eisenbrand, G. Shmonin, Carathéodory bounds for integer cones, Operations Research Letters 34(5):564-568, 2006. [DOI]