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

Abstract

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 $\Omega (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 $\Omega (\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+\epsilon /n)$-approximate extended formulation for these polytopes, for some constant $\epsilon >0$, has size $2^{\Omega (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. $\epsilon =0$).

Full paper of IPCO 2024 version