2025/01/04 by Friedrich Eisenbrand, Thomas Rothvoß, Eisenbrand, Friedrich +1 · 1 citation
Engineering · Mathematics · #Advanced Control Systems Optimization #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Robotic Mechanisms and Dynamics
paper · pdf · doi:10.48550/arxiv.2501.02347
openalex publication_date 2025/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let A ∈ ℤm × n be an integer matrix with components bounded by Δ in absolute value. Cook et al.~(1986) have shown that there exists a universal matrix B ∈ ℤm' × n with the following property: For each b ∈ ℤm, there exists t ∈ ℤm' such that the integer hull of the polyhedron P = \ x ∈ ℝn \colon Ax ≤ b\ is described by PI = \ x ∈ ℝn \colon Bx ≤ t\. Our main result is that t is an affine function of b as long as b is from a fixed equivalence class of the lattice D ⋅ ℤm. Here D ∈ ℕ is a number that depends on n and Δ only. Furthermore, D as well as the matrix B can be computed in time depending on Δ and n only. An application of this result is the solution of an open problem posed by Cslovjecsek et al.~(SODA 2024) concerning the complexity of 2-stage-stochastic integer programming problems. The main tool of our proof is the classical theory of Chvátal-Gomory cutting planes and the elementary closure of rational polyhedra.