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 $$ \varOmega (n/\log ^2 n) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:msup> <mml:mo>log</mml:mo> <mml:mn>2</mml:mn> </mml:msup> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> <mml:mo>/</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> by Cevallos et al. (in Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms (SODA), SIAM, 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})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mfrac> <mml:mi>ε</mml:mi> <mml:mi>n</mml:mi> </mml:mfrac> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximate extended formulation for these polytopes, for some constant $$ \varepsilon &gt; 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> , has size $$2^{\varOmega (n/\log n)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> . Our proof extends and simplifies the information-theoretic methods due to Göös et al. (SIAM J Comput 47(1):241–269, 2018) who showed the same result for the case of exact extended formulations (i.e. $$\varepsilon = 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> <mml:mo>=</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> ).