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.