Strong IP Formulations Need Large Coefficients

The development of practically well-behaving integer programming formulations is an important aspect of solving linear optimization problems over a set $X \subseteq \{0,1\}^n$. In practice, one is often interested in strong integer formulations with additional properties, e.g., bounded coefficients to avoid numerical instabilities. This article presents a lower bound on the size of coefficients in any strong integer formulation of $X$ and demonstrates that certain integer sets $X$ require exponentially large coefficients in any strong integer formulation. We also characterize the minimum size of an integer formulation of $X \subseteq \{0,1\}^n$ with bounded coefficients.

Article

Download

View Strong IP Formulations Need Large Coefficients