(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs

2025/05/28 by Christoph Hunkenschröder, Hunkenschröder, Christoph, Martin Koutecký +5 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2505.22212

openalex publication_date 2025/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: min \f(x) | Ax = b, l ≤ x ≤ u, x ∈ ℤⁿ\. The number of variables n is a variable part of the input, and we consider the regime where the constraint matrix A has small coefficients ‖A‖_∞ and small primal or dual treedepth td_P(A) or td_D(A), respectively. Equivalently, we consider block-structured matrices, in particular n-fold, tree-fold, 2-stage and multi-stage matrices. We ask about the possibility of near-linear time algorithms in the general case of (non-linear) separable convex functions. The techniques of previous works for the linear case are inherently limited to it; in fact, no strongly-polynomial algorithm may exist due to a simple unconditional information-theoretic lower bound of n log ‖u-l‖_∞, where l, u are the vectors of lower and upper bounds. Our first result is that with parameters td_P(A) and ‖A‖_∞, this lower bound can be matched (up to dependency on the parameters). Second, with parameters td_D(A) and ‖A‖_∞, the situation is more involved, and we design an algorithm with time complexity g(td_D(A), ‖A‖_∞) n log n log ‖u-l‖_∞ where g is some computable function. We conjecture that a stronger lower bound is possible in this regime, and our algorithm is in fact optimal. Our algorithms combine ideas from scaling, proximity, and sensitivity of integer programs, together with a new dynamic data structure.

Citations

• A parameterized linear formulation of the integer hull
• Tight Lower Bounds for Block-Structured Integer Programs
• Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow
• Parameterized algorithms for block-structured integer programs with large entries
• Fast Algorithms for Separable Linear Programs
• Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
• Collapsing the Tower -- On the Complexity of Multistage Stochastic IPs
• Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity
• A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
• The Double Exponential Runtime is Tight for 2-Stage Stochastic ILPs
• Multitype Integer Monoid Optimization and Applications
• An Algorithmic Theory of Integer Programming
• About the Complexity of Two-Stage Stochastic IPs
• Strong mixed-integer programming formulations for trained neural networks
• Strong mixed-integer programming formulations for trained neural networks
• Tight complexity lower bounds for integer linear programming with few constraints
• Near-Linear Time Algorithm for n-fold ILPs via Color Coding
• Faster Algorithms for Integer Programs with Block Structure
• Best Subset Selection via a Modern Optimization Lens
• A Faster Parameterized Algorithm for Treedepth
• Finiteness theorems in stochastic integer programming

Cited by

• Parameterized Critical Node Cut Revisited

Related

• An Algorithmic Theory of Integer Programming
• Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time
• Optimizing Low Dimensional Functions over the Integers
• Minimizing a low-dimensional convex function over a high-dimensional cube
• On the Optimality of Pseudo-polynomial Algorithms for Integer Programming