Integer programming algorithm with exponent linear in dimension
Integer Programing: An Algorithm with Exponent Linear in the Dimension
Data Structures and Algorithms
Summary
Integer programming is about finding the best whole-number solutions to problems with certain rules. Before, the best methods for some problems grew very fast in complexity as the problem dimension increased. The authors found a new algorithm where this complexity grows only linearly with the dimension, which is a big improvement. This means solving certain integer programs could become much more efficient when the dimension is large.
What this means in practice
- •For operations researchers: Optimize large integer-based resource allocation problems more efficiently when problem dimension is high.
- •For supply chain planners: Improve computation speed for integer programs that model complex logistics with many constraints and variables.
A theory result. No direct application yet.
Authors
Lin Chen, Yuchen Mao, Guochuan Zhang
Abstract
We study integer programs in standard form $\min\{\mathbf{c}^{\mathsf{T}}\mathbf{x}:A\mathbf{x}=\mathbf{b},\ \mathbf{l}\leq\mathbf{x}\leq\mathbf{u},\ \mathbf{x}\in\mathbb{Z}^n\}$, where $A\in\mathbb{Z}^{d\times n}$ and all entries of $\mathbf{b},\mathbf{c},\mathbf{l},\mathbf{u}$ are integers. Let $N$ be an upper bound on the absolute values of the entries of $A$. We give a deterministic algorithm running in time \[ \operatorname{poly}(L_{\rm in})+ f(d)\,N^{O(d)}\bigl(1+\log(c_{\max}+1)\bigr)^{O(1)}, \] where $c_{\max}$ bounds the absolute values of the costs and $L_{\rm in}$ is the input length. Prior to our work, the best known running time was $N^{O(d^2)}$ [Eisenbrand \& Weismantel'20], and it has been a fundamental open problem whether the exponent $O(d^2)$ can be improved to one linear in $d$. We answer this question affirmatively.