Everyone is welcome to attend the public lecture of Christopher Hojny (TU Darmstadt) withe the title 'Strong IP Formulations Need Large Coefficients'.
Abstract:
The development of practically well-behaving integer programming formulations is an important aspect of solving linear optimization
problems over a set of binary points. In practice, one is often interested in strong integer formulations with additional properties,
e.g., bounded coefficients to avoid numerical instabilities.
To measure the strength of an integer formulation, I introduce the concept of 1/lambda-relaxations. 1/lambda-relaxations generalize
classical integer formulations to refinements of the integer lattice by a factor of 1/lambda. After pointing out how 1/lambda-relaxations arise naturally for the stable set problem, I present a lower bound on the size of coefficients in any 1/lambda-relaxation of a binary set. Using this bound, I show, among others, that strong integer formulations of the stable set problem need, in general, coefficients that grow linearly in the size of the underlying graph. For knapsack problems, I demonstrate that exponentially large coefficients may be necessary in any strong integer formulation. Thus, strong integer formulations need large coefficients in general.
