The Proof Complexity of Integer Programming

Noah Fleming (Memorial University)
https://simons.berkeley.edu/talks/noah-fleming-memorial-university-2023-04-18
Satisfiability: Theory, Practice, and Beyond

We discuss recent progress on understanding modern integer programming algorithms using proof complexity. Proof complexity provides an elegant approach for studying the complexity of algorithms for solving NP-hard problems. The sequence of operations which an algorithm performs on an input can be viewed as a proof of correctness of the computation. These proofs belong to some proof system and thus lower bounds on the
size of proofs in that system imply the intractability of that algorithm. We take this approach in order to analyze modern integer programming algorithms. We introduce the Stabbing Planes proof system, which tightly models modern integer programming algorithms. To obtain lower bounds on the complexity of Stabbing Planes proofs, we
establish a surprisingly close relationship with Cutting Planes.