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

• 成果类型: Article; Early Access
• 署名作者: Schade, Jamico; Sinha, Makrand; Weltge, Stefan
• 署名单位: Technical University of Munich; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02234-z
• 发表日期: 2025
• 关键词: edge-disjoint paths; extension complexity

摘要

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(root 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+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 Goos et al. (SIAM J Comput 47(1):241-269, 2018) who showed the same result for the case of exact extended formulations (i.e. epsilon=0).