TY - GEN
T1 - Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
AU - Schade, Jamico
AU - Sinha, Makrand
AU - Weltge, Stefan
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024
Y1 - 2024
N2 - 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 Ω(n/log2n) 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 Ω(n/logn) 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+εn)-approximate extended formulation for these polytopes, for some constant ε>0, has size 2Ω(n/logn). 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. ε=0).
AB - 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 Ω(n/log2n) 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 Ω(n/logn) 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+εn)-approximate extended formulation for these polytopes, for some constant ε>0, has size 2Ω(n/logn). 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. ε=0).
KW - extended formulations
KW - knapsack problem
KW - mixed-integer programming
KW - stable set problem
UR - http://www.scopus.com/inward/record.url?scp=85195146882&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-59835-7_28
DO - 10.1007/978-3-031-59835-7_28
M3 - Conference contribution
AN - SCOPUS:85195146882
SN - 9783031598340
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 379
EP - 392
BT - Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings
A2 - Vygen, Jens
A2 - Byrka, Jarosław
PB - Springer Science and Business Media Deutschland GmbH
T2 - 25th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2024
Y2 - 3 July 2024 through 5 July 2024
ER -