4-block integer programs solved efficiently with new fixed parameter method
4-Block Integer Programming is in FPT
Computational Complexity
Summary
Integer programming helps solve many decision-making problems but is usually very hard to do quickly. The authors studied a specific type called 4-block integer programming and showed it can be solved efficiently when focusing on certain parameters. They created an algorithm that deals not only with simple goals but also with more complex problems involving convex functions. This work answers a major open question and extends previous methods to more general cases, getting very close to the best possible running time.
What this means in practice
- •For operations research teams: Optimize complex scheduling and resource allocation problems with 4-block structured constraints efficiently using the new fixed-parameter algorithm.
- •For logistics planners: Improve route and shipment planning models that fit into the 4-block integer programming framework by applying the new algorithm for faster solutions.
A theory result. No direct application yet.
Authors
Martin Koutecký, Alexandra Lassota, Koen Ligthart
Abstract
Integer programming is a fundamental and important NP-hard problem. This motivated extensive efforts in studying several tractable subclasses. One of the top unresolved complexity questions is the parameterized complexity of 4-block IPs, a natural class characterized by having a diagonal matrix with small blocks after deleting few rows and columns. Over the years, significant progress has been made in improving algorithms for 4-block IPs, but the question whether such IPs can be solved in FPT time, parameterized by the block dimensions and largest matrix coefficient, has remained open. This question is repeatedly highlighted, most recently by Koutecký [IPEC 2025] and by Eisenbrand and Rothvoss [SODA 2026]. We resolve this question in the positive by providing an FPT time algorithm that solves general 4-block integer program. Our algorithm can optimize non-linear, separable convex objective functions, and can be extended to broader classes of constraint matrices (such as tree-fold or multi-stage) and allows appending few ``global'' columns to it, and it allows coefficients unbounded by the parameters in those columns. It is known that tractability cannot be extended further in any of those directions. The runtime also nearly matches the known doubly exponential running time lower bound. The key structural property that we establish is that a function $f\colon\mathbb Z^n\to\mathbb R$ that is integer midpoint convex, i.e., $f(x)\le\tfrac12f(x-p)+\tfrac12f(x+p)$ for all $x,p\in\mathbb Z^n$, can be extended to a convex function on the set $2d\mathbb Z^n\cap L$ if $L$ is a linear subspace of dimension $d$. This closes the gap in a recent work by Ligthart [arXiv 2606.30330, 2026], which allows us to extend the previous algorithm that solves 4-block integer programs with a single global variable to 4-block integer programs that have a parameterized number of global variables.