Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack

Standard mixed-integer programming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give a family of n-node graphs for which every polynomial-size MIP formulation requires \( \varOmega (n/\log ^2 n) \) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack problems. In both cases, this improves the previously known bounds of \( \varOmega (\sqrt{n}/\log n) \) by Cevallos, Weltge  & Zenklusen (SODA 2018). To this end, we show that there exists a family of n-node graphs whose stable set polytopes satisfy the following: any \((1+\nicefrac {\varepsilon }{n})\) -approximate extended formulation for these polytopes, for some constant \( \varepsilon > 0\) , has size \(2^{\varOmega (n/\log n)}\) . Our proof extends and simplifies the information-theoretic methods due to Göös, Jain  & Watson (FOCS 2016, SIAM J. Comput. 2018) who showed the same result for the case of exact extended formulations (i.e. \(\varepsilon = 0\) ).