Strong IP formulations need large coefficients
Christopher Hojny · Discrete Optimization · 2021
The development of practically well-behaved integer programming formulations is an important aspect of solving linear optimization problems over a set X⊆{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 show that strong integer formulations of X⊆{0,1}n may require exponentially many inequalities while linearly many inequalities may suffice in weak formulations.