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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$ \varOmega (n/\log ^2 n) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">/</mo> <msup> <mo>log</mo> <mn>2</mn> </msup> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$ \varOmega (\sqrt{n}/\log n) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Ω</mi> <mo stretchy="false">(</mo> <msqrt> <mi>n</mi> </msqrt> <mo stretchy="false">/</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$(1+\nicefrac {\varepsilon }{n})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mfrac bevelled="true"> <mi>ε</mi> <mi>n</mi> </mfrac> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-approximate extended formulation for these polytopes, for some constant <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$ \varepsilon > 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, has size <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$2^{\varOmega (n/\log n)}$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mi>Ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">/</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </msup> </math></EquationSource> </InlineEquation>. 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. <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\varepsilon = 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>).

Lower bounds on the complexity of mixed-integer programs for stable set and knapsack

期刊论文
出版模式：

开放获取
发表日期：

2025年5月19日

查看全文

Jamico Schade,
Makrand Sinha,
Stefan Weltge

摘要

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) $ $Ω (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) $ $Ω (\sqrt{n} / log n)$ 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})$ $(1 + \frac{ε}{n})$ -approximate extended formulation for these polytopes, for some constant $ \varepsilon > 0$ $ε > 0$ , has size $2^{\varOmega (n/\log n)}$ $2^{Ω (n / log n)}$ . 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$ $ε = 0$ ).