Next generation extended formulations

• Applicant: Professor Dr. Stefan Weltge
• Subject Area: Mathematics
• Term: from 2020 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 451026932

• Final Report Year: 2024

Final Report Abstract

Extended formulations are commonly used to formulate discrete optimization problems as linear or mixed-integer programs in a compact way. The goal of this project was to extend its theory from different perspectives and to develop new applications. Our main results are the following. • We construct a family of lattices whose Voronoi cells do not admit (linear or semidefinite) polynomial-size extended formulations. We complement our findings by showing that Voronoi cells of root lattices, a rich family of lattices containing many extremal examples, have polynomial-size extended formulations. Compact representations of Voronoi cells of lattices can be exploited in algorithms for problems such as the closest vector problem. • We construct n-node graphs for which any polynomial-size mixed-integer programming formulation of the stable set problem requires Ω(n/ log2 n) integer variables. Our bound is essentially optimal in the sense that textbook integer programming formulations use O(n) integer variables. The previously best lower bound was Ω( √n/ log n). Our findings imply an analogous result for the knapsack problem. • We give polynomial-size extended formulations for the feedback vertex set problem whose integrality gap is at most 2. On the one hand, this matches the fact that the problem admits combinatorial and primal-dual based 2-approximations. However, no polynomially solvable LP relaxation for the feedback vertex set problem with integrality gap 2 has been known before. As part of this project, our discussions have also led to further results related to the theory of integer programming: • We construct n-dimensional lattice-free simplices with lattice width 2n−o(n), which yields a new lower bound on the flatness constant. The previously best lower bound was 1.138n. The flatness constant is the best-possible bound according to the flatness theorem, and its value determines the running time of several algorithms for integer programming. • We give a polynomial-time algorithm for solving integer programs whose coefficient matrix has at most two nonzeros per row and all subdeterminants bounded by a constant. In particular, we derive a polynomial-time algorithm for the stable set problem on the family of graphs with bounded odd cycle packing number. For the latter problem, only a PTAS has been known before our work. Our main result supports the actively discussed conjecture that integer programs with bounded subdeterminants can be solved in polynomial time.

Publications

• Integer programs with bounded subdeterminants and two nonzeros per row. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 13-24. IEEE.
  Fiorini, Samuel; Joret, Gwenael; Weltge, Stefan & Yuditsky, Yelena
  
• Lattice-Free Simplices with Lattice Width 2d − o(d). Lecture Notes in Computer Science, 375-386. Springer International Publishing.
  Mayrhofer, Lukas; Schade, Jamico & Weltge, Stefan
  
• Lifts for Voronoi Cells of Lattices. Discrete & Computational Geometry, 70(3), 845-865.
  Schymura, Matthias; Seidel, Ina & Weltge, Stefan
  
• Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack. Lecture Notes in Computer Science, 379-392. Springer Nature Switzerland.
  Schade, Jamico; Sinha, Makrand & Weltge, Stefan
  
• Integer programs with bounded subdeterminants and two nonzeros per row. Journal of the ACM, 72(1), 1-50.
  Fiorini, Samuel; Joret, Gwenaël; Weltge, Stefan & Yuditsky, Yelena
  
• Polyhedral aspects of feedback vertex set and pseudoforest deletion set. Mathematical Programming, 214(1-2), 153-200.
  Chandrasekaran, Karthekeyan; Chekuri, Chandra; Fiorini, Samuel; Kulkarni, Shubhang & Weltge, Stefan