On the Existence of Compact Epsilon-Approximated Formulations for Knapsack in the Original Space
We show that there exists a family of Knapsack polytopes such that for each P in the family and each epsilon>0, any epsilon-approximated formulation of P in the original space R^n requires a number of inequalities that is super-polynomial in n. This answers a question by Bienstock and McClosky (2012). …