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

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…