Integer programming solved with polyhedral limits on outputs
Integer Programming with Polyhedral Constraints on the Image
Data Structures and Algorithms
Summary
Integer programming helps in making the best decisions when choices must be whole numbers and follow certain rules. This work extends integer programming by adding limits on what the outputs can look like, specifically when they must fit inside a certain shape called a polyhedron. The authors provide a new randomized algorithm that runs efficiently, matching or improving previous methods. Their results also solve a known open problem and clarify when certain solving times are necessary.
What this means in practice
- •For operations researchers: Design efficient algorithms for integer programs where outputs must satisfy complex linear constraints, improving resource allocation models.
- •For cryptography engineers: Use fixed-parameter algorithms for subset sum variations in cryptographic protocol design and analysis.
A theory result. No direct application yet.
Authors
Anubhav Dhar, Tim Randolph, Karol Węgrzycki
Abstract
We generalize integer programming to the setting in which the image $A \mathbf{x}$ is restricted to an explicitly given rational polyhedron $P$. That is, we solve $\min\{\mathbf{c}^{\mathsf T}\mathbf{x}:A\mathbf{x}\in P, \mathbf{x}\in\mathbb{Z}_{\geq 0}^n\}$, where $A\in\mathbb{Z}^{d\times n}$ and $P$ is an explicitly given rational polyhedron. We present a randomized algorithm running in time $(dΔ)^{O(d)}\operatorname{poly}(L)$ in this regime, where $Δ:= \|A\|_\infty$ and $L$ is the binary input length. This running time matches that of the best-known parameterized algorithms for integer programming, due to Eisenbrand and Weismantel and to Jansen and Rohwedder, and improves on the $O(d^2)$ exponent achieved by Dadush, Léonard, Rohwedder, and Verschae in a more general setting. This result enables several applications, including exact algorithms for integer programming and unbounded knapsack in which the consumed resources $A\mathbf{x}$ must satisfy arbitrary additional linear constraints. We also obtain a randomized fixed-parameter algorithm for Unbounded Subset Sum parameterized by the doubling constant, resolving an open problem of Randolph and Węgrzycki. For integer programs with $m$ constraints and bounded row doubling, we obtain an $f(C,m)n^{O(m)}\operatorname{poly}(L)$-time algorithm and show that the dependence on $m$ in the exponent of $n$ is necessary under $\mathsf{W[1]}\ne\mathsf{FPT}$.