A Brief History of Parameterized Algorithms for Block-Structured Integer Programs

Our focus is on how a stream of research spanning over two decade has blossomed into a unified theory including significant time complexity improvements, generalizations to wider classes, and complementary lower bound results. Besides the results discussed in this paper, we have also shown how this theory can be used to obtain efficient algorithms for problems in scheduling, stringology, graph theory, and computational social choice [69, 70, 74, 36, 44, 68, 67, 72, 71].

The purpose of this section is to introduce two important classes of block-structured IPs, and briefly explain the motivation and history of their study. A matrix $A^{(n)}$ is $n$-fold with blocks $A_1,A_2$ if it has the form

for $A_1\in {\mathbb{Z}}^{r\times t}$ and $A_2\in {\mathbb{Z}}^{s\times t}$. To be precise, the above may be called a “uniform” $n$-fold matrix, as opposed to a “generalized” $n$-fold matrix in which the blocks may differ. We choose to deal with the uniform case here because:

1. (a)

   it simplifies exposition,

2. (b)

   the key proof ideas usually extend to the generalized case,

3. (c)

   the uniform case is usually without loss of generality, because the generalized case can be embedded in it by suitable encoding tricks (though incurring some inefficiencies).

On the other hand, the general case is more appropriate when dealing with applications.

A 2-stage matrix $B^{(n)}$ is the transpose of an $n$-fold matrix, i.e.,

We will also consider generalizations of both classes, so called tree-fold and multi-stage stochastic IPs, whose matrices have a recursive structure. For example, a tree-fold matrix has the form (1), except each block $A_2$ is itself a tree-fold matrix; see Figure 1.

$N$-fold IP was introduced under this name by De Loera et al. [26] in 2008, but programs of this form have appeared in the literature much earlier. Consider the transportation problem, which asks for an optimal routing from several sources to several destinations. It has been defined by Hitchcock [54] in 1941 and independently studied by Kantorovich [63] in 1942, and Dantzig [23] studied it in 1951 in the context of the applicability of the simplex method. The transportation problem may be seen as a table problem where we are given $m$ row-sums and $n$ column-sums and the task is to fill in non-negative integers into the table so as to satisfy the given row- and column-sums. A natural generalization to higher-dimensional tables, called multiway tables, has been studied already in 1947 by Motzkin [80]. It also has applications in privacy in databases and confidential data disclosure of statistical tables, see a survey by Fienberg and Rinaldo [37] and the references therein.

Specifically, the three-way table problem is to decide if there exists a non-negative integer $l\times m\times n$ table satisfying given line-sums, and to find the table if there is one. Deciding the existence of such a table is $\mathrm{𝖭𝖯}$-complete already for $l=3$ [27]. Moreover, every bounded integer program can be isomorphically represented in polynomial time for some $m$ and $n$ as some $3\times m\times n$ table problem [28]. The complexity with $l,m$ parameters and $n$ variable thus became an interesting problem. Let the input line-sums be given by vectors $𝐮\in {\mathbb{Z}}^{ml},𝐯\in {\mathbb{Z}}^{nl}$ and $𝐰\in {\mathbb{Z}}^{nm}$. Observe that the problem can be formulated as an IP with variables $x_{j,k}^i$ for $i\in [n]$, $j\in [m]$ and $k\in [l]$, objective function $f\equiv 0$, and the following constraints:

Let $I_k$ be the $k\times k$, $k\in \mathbb{N}$, identity matrix, and ${\mathrm{𝟏}}_k$ the all-ones vector of dimension $k\in \mathbb{N}$. Then the above, written in matrix form, becomes $A𝐱=𝐛,𝐱\ge \mathrm{𝟎}$ with $𝐛=(𝐮,{𝐯}^1,{𝐰}^1,{𝐯}^2,{𝐰}^2,\mathrm{\dots },{𝐯}^n,{𝐰}^n)$, and with

Here, $J$ has $m$ diagonal blocks ${\mathrm{𝟏}}_l$ and $A$ has $n$ diagonal blocks $J$. Thus, $A$ can be viewed either as an $n$-fold matrix, or as a tree-fold matrix with 3 levels.

A different implicit appearance of the $n$-fold structure is in the famous³³3Over 3,000 and 1,800 citations, respectively, according to Google Scholar, as of October 2025. 1961 and 1963 papers by Gilmore and Gomory [45, 46] on solving the Cutting Stock problem. Their work has been essential in regards to fundamental notions like column generation, cutting planes, and the Configuration LP whose depiction from the 1963 paper [46] appears in Figure 2. It is clear that the presented matrix is $n$-fold, and we will return to it in Section 3. In fact, the significance of the $n$-fold structure in packing and scheduling problems seems to have been lost until a brief mention in the paper introducing $n$-fold IP [26], and has only been taken up in earnest [68, 60, 69, 14, 50, 65, 15] in the wake of the paper of Knop and Koutecký from 2018 [67]. Let us now briefly describe this connection.

The problem of uniformly related machines makespan minimization, denoted $Q||C_{\max }$ in the standard notation, is the following. We are given $m$ machines, each with speed $s_i>0$, and $n$ jobs, where the $j$-th job has processing time $p_j\in \mathbb{N}$ and processing it on machine $i$ takes time $p_j/s_i$. The task is to assign jobs to machines such that the time when the last job finishes (the makespan) is minimal, i.e., if $M_i$ is the set of jobs assigned to machine $i$ and ${\bigcup }_i{M}_i$ contains all jobs, the task is to minimize ${\max }_{i\in [m]}{\sum }_{j\in M_i}{p}_j/s_i$. The decision version of the problem asks whether there is a schedule of makespan $C_{\max }\in ℝ$. We consider the scenario when $p_{\max }={\max }_j{p}_j$ is bounded by a parameter and the input is represented succinctly by multiplicities $n_1,\mathrm{\dots },n_{p_{\max }}$ of jobs of each length, i.e., $n_{\mathrm{\ell }}$ is the number of jobs with $p_j=\mathrm{\ell }$. Letting $x_j^i$ be a variable representing the number of jobs of length $j$ assigned to machine $i$, Knop and Koutecký [67] give the following $n$-fold formulation:

Constraints (3) ensure that each job is scheduled on some machine, and constraints (4) ensure that each machine finishes before time $C_{\max }$. This corresponds to an $n$-fold formulation with $A_1=I_{p_{\max }}$ and $A_2=(1,2,\mathrm{\dots },p_{\max })$ and with ${\Vert A^{(n)}\Vert }_{\mathrm{\infty }}=p_{\max }$.

Another scheduling problem is finding a schedule minimizing the sum of weighted completion times $\sum w_j{C}_j$. Knop and Koutecký [67] show an $n$-fold formulation for this problem as well, in particular one which has a separable quadratic objective. In the context of scheduling, what sets methods based on $n$-fold IP apart is that they allow the handling of many “types” of machines (such as where machines have different speeds) and also “non-linear” objectives (such as the quadratic objective in the formulation for $\sum w_j{C}_j$).

Another field where $n$-fold IP has had an impact is computational social choice. The problem of Bribery asks for a cheapest manipulation of voters which lets a particular candidate win an election. An $\mathrm{𝖥𝖯𝖳}$ algorithm was known for Bribery parameterized by the number of candidates which relied on Lenstra’s algorithm. However, this approach has two downsides: a time complexity which is doubly-exponential in the parameter, and the fact that voters have to be “uniform” and cannot have distinct cost functions. Knop et al. [72] resolved this problem using $n$-fold IP by showing a single-exponential algorithm for many Bribery-type problems, even in the case when each voter has a different cost function.

Lastly, the Dantzig-Wolfe decomposition [24] is an fundamental algorithm for solving linear programs with an $n$-fold structure which decomposes the problem into a master problem and a series of subproblems corresponding to the individual blocks. While this approach is primarily studied in the context of continuous optimization, it can be fruitfully generalized to integer programming as well [98].

The motivation for the study of $2$-stage stochastic matrices comes from decision making under uncertainty. Here, one is asked to make a partial decision in a “first stage”, and after realization of some random data, one has to complete their decision in a “second stage”. The goal is minimizing the “direct” cost of the first-stage decision plus the expected cost of the second-stage decision. Random data are often modeled by a finite set of $n$ scenarios, each with a given probability. Assume that the scenarios are represented by integer vectors ${𝐛}^1,\mathrm{\dots },{𝐛}^n\in {\mathbb{Z}}^t$, their probabilities by $p_1,\mathrm{\dots },p_n\in (0,1]$, the first-stage decision is encoded by a variable vector ${𝐱}^0\in {\mathbb{Z}}^r$, and the second-stage decision for scenario $j\in [n]$ is encoded by a variable vector ${𝐱}^j\in {\mathbb{Z}}^s$. Setting $𝐱:=({𝐱}^0,{𝐱}^1,\mathrm{\dots },{𝐱}^n)$ and $𝐛:=({𝐛}^1,\mathrm{\dots },{𝐛}^n)$ then makes it possible to write this problem as

with $A_1\in {\mathbb{Z}}^{t\times r}$, $A_2\in {\mathbb{Z}}^{t\times s}$, and $𝐥,𝐮\in {\mathbb{Z}}^{r+ns}$ some lower and upper bounds. Problem (5) is called $2$-stage stochastic IP and finds many applications [7, 61, 88].

Similarly to the Dantzig-Wolfe decomposition method for problems with an $n$-fold structure, a decompositional method for problems with a $2$-stage structure has been introduced by Benders [5] in 1962. Where Dantzig-Wolfe introduces new columns in each iteration (leading to “column generation”), Benders introduces new rows (leading to “row generation”). A generalization to the (mixed) integer case has been also studied [94].

Integer programs with block structure have also been the subject of at least two habilitations, that of Martin [79] and Nowak [83], which contain many other relevant references.

We will now review the developments regarding parameterized complexity of block-structured IPs until 2018. Whenever we talk about $\mathrm{𝖥𝖯𝖳}$ algorithms here, the parameter is the largest coefficient in absolute value ${\Vert A\Vert }_{\mathrm{\infty }}$, and the sizes of the blocks composing the block-structured matrix at hand. The key notion behind most of the results reviewed here is the Graver basis of the matrix $A$, $𝒢(A)$, which is the set of non-zero integer vectors $𝐠$ satisfying $A𝐠=\mathrm{𝟎}$ that cannot be decomposed into two non-zero integer vectors with the same sign-pattern (i.e., belonging to the same orthant) satisfying the same equation. These Graver basis elements are thus called indecomposable, irreducible, or conformal-minimal. The Graver basis allows a simple iterative augmentation procedure: given a feasible solution $𝐱$, either $𝐱+𝐠$ for some $𝐠\in 𝒢(A)$ is feasible and improves the objective function, or $𝐱$ is already optimal.

We now discuss three areas where the main developments took place.

Denote by $⟨A,f,𝐛,𝐥,𝐮⟩$ the binary encoding length of an IP instance. (We define the encoding length of $f$ to be the length of $f_{\mathrm{gap}}$, which is the difference between the maximum and minimum values of $f$ on the domain.) The function $f$ is given by an oracle. A glaring question left open by Ganian and Ordyniak [42] is that of the complexity of IP parameterized by ${\Vert A\Vert }_{\mathrm{\infty }}$ and ${\mathrm{td}}_P(A)$ or ${\mathrm{td}}_D(A)$. In [73], we have fully settled this with the following result:

Note that for this algorithm to be fast it suffices if at least one of ${\mathrm{td}}_P(A)$ and ${\mathrm{td}}_D(A)$ is small. Also, all the presented results hold for IP whose constraints are given in the inequality form $A𝐱\le 𝐛$: introducing slack variables leads to IP in standard form with a constraint matrix $A_I:=(AI)$, with $\min \{{\mathrm{td}}_P(A_I),{\mathrm{td}}_D(A_I)\}\le \min \{{\mathrm{td}}_P(A)+1,{\mathrm{td}}_D(A)\}$.

Theorem 1 is qualitatively optimal in the following sense. Already for ${\Vert A\Vert }_{\mathrm{\infty }}=1$ or $d=1$ ILP is $\mathrm{𝖭𝖯}$-hard: by the natural reduction from SAT in the former case, and similarly by the natural modeling of Knapsack in the latter. Moreover, the two arguably most important tractable classes of IP are formed by instances whose constraint matrix is either totally unimodular or has small number $n$ of columns, yet our results are incomparable with either: the class of totally unimodular matrices might have large $d$, but has ${\Vert A\Vert }_{\mathrm{\infty }}=1$, and the matrices considered here have variable $n$.

Furthermore, treedepth cannot be replaced with the more permissive notion of treewidth, since IP is $\mathrm{𝖭𝖯}$-hard already when $\min \{{\mathrm{tw}}_P(A),{\mathrm{tw}}_D(A)\}=2$ and $a=2$ [33]. Second, the parameterization cannot be relaxed by removing the parameter ${\Vert A\Vert }_{\mathrm{\infty }}$: IP is para-$\mathrm{𝖭𝖯}$-hard parameterized by ${\mathrm{td}}_P(A)$ [30, Thm 21] and strongly $𝖶[\mathrm{𝟣}]$-hard parameterized by ${\mathrm{td}}_D(A)$ [72, Thm 5] alone. Third, the requirement that $f$ is separable convex cannot be relaxed since IP with a non-separable convex or a separable concave function are $\mathrm{𝖭𝖯}$-hard even for small values of our parameters [33]. Let us now sketch our approach towards proving Theorem 1.

A fundamental question regarding problems involving large numbers is whether there exists an algorithm whose number of arithmetic operations does not depend on the length of the numbers involved; recall that if this number is polynomial, this is a strongly polynomial algorithm [93]. For example, the ellipsoid method or the interior-point method which solve LP take time which does depend on the encoding length, and the existence of a strongly polynomial algorithm for LP remains a major open problem. Until 2018, the only strongly polynomial ILP algorithms existed for totally unimodular ILP [56], bimodular ILP [3], so-called binet ILP [2], and $n$-fold ILP with constant block dimensions [25]. All remaining results, such as Lenstra’s famous algorithm or the $\mathrm{𝖥𝖯𝖳}$ algorithm for $n$-fold IP of Hemmecke et al. [52], are not strongly polynomial.

A second contribution of [73] besides Theorem 1 is the development of an algorithmic framework among others suitable for obtaining strongly polynomial algorithms, and as a consequence of Theorem 1 we show a strongly polynomial algorithm for ILP in the same parameter regime:

The proof of Theorem 2 proceeds in four steps:

1. LP relaxation:

the LP relaxation can be solved in time $\mathrm{poly}(n\cdot ⟨A⟩)$ by Tardos’ algorithm [93], obtaining a fractional optimum ${𝐱}^{\ast }$.

2. Proximity:

the integer optimum ${𝐳}^{\ast }$ which we seek is at an ${\mathrm{\ell }}_{\mathrm{\infty }}$-distance at most $𝒪(g_{\mathrm{\infty }}(A)\cdot n)$ from ${𝐱}^{\ast }$, thus we may reduce the lower and upper bounds $𝐥,𝐮$ to some ${𝐥}^{\prime },{𝐮}^{\prime }$ which are bounded by $𝒪(g_{\mathrm{\infty }}(A)\cdot n)$, and subsequently also reduce the right hand side $𝐛$ to some ${𝐛}^{\prime }$ which is bounded by $g_{\mathrm{\infty }}(A)\mathrm{poly}(n)$.

3. Objective reduction:

since we now know that the integer optimum ${𝐳}^{\ast }$ lies in a “small” box $[{𝐥}^{\prime },{𝐮}^{\prime }]$, we can apply the coefficient reduction technique of Frank and Tardos [40] to obtain an equivalent objective ${𝐰}^{\prime }$ with $\log {\Vert {𝐰}^{\prime }\Vert }_{\mathrm{\infty }}=\mathrm{poly}(g_{\mathrm{\infty }}(A)\cdot n)$.

4. Convergence:

because the length of all numbers on input is now polynomial in $n$, the algorithm of Theorem 1 runs in strongly polynomial time.

A nice and somewhat surprising property of this approach is that, since $f$ is given by a comparison oracle and since step 3 reduces it to an equivalent function, this step is actually irrelevant and we may proceed to step 4 directly. Thus, the algorithm boils down to solving the LP relaxation, reducing the lower and upper bounds and right hand side in a straightforward manner, and running the algorithm of Theorem 1. The fact that step 3 is unnecessary is in fact substantial, because while the algorithm of [40] is polynomial, the degree of this polynomial is quite large and would dominate the complexity of the algorithm overall. We have expanded on these ideas in [32] by showing that if the equivalent objective need not be computed, then stronger bounds on ${\Vert {𝐰}^{\prime }\Vert }_{\mathrm{\infty }}$ can be obtained, leading to better bounds on the algorithm itself. Furthermore, we have shown reducibility upper bounds on not just linear but also separable convex functions, and also almost matching lower bounds.

The main contribution of [31] over [73] is that it presents a streamlined and self-contained version of the proof of Theorem 1. With the benefit of hindsight, we have replaced Graver-best augmentation with a cheaper so-called halfling augmentation, and we have derived all results (norm bounds, local search programs) directly in the most general setting of bounded treedepth. The whole paper is only 16 pages long including references, and is currently perhaps the best entry point into the area for any newcomer, including graduate and even undergraduate students. Still, we are (slowly) working on developing lecture notes, which will be even more approachable.

The main result of [10] is the following:

By the techniques of Theorem 2, the algorithm of Theorem 4 can be made strongly $\mathrm{𝖥𝖯𝖳}$.

Lenstra’s algorithm [75] can also be extended, e.g. using [49, Theorem 6.7.9], to the setting of arbitrary convex objective functions, and, by the same arguments as with the step from ILP to MILP, it can be shown that MIP, which is the problem

with $f$ convex is also $\mathrm{𝖥𝖯𝖳}$ parameterized by $z$. Giving attention to objective functions beyond linear is well justified: Bertsimas et al. note in their spectacular work [6] on the notorious subset selection problem in statistical learning that, over the past decades, algorithmic and hardware advances have elevated convex (and therefore, non-linear) mixed-integer optimization to a comparable level of relevance in applications. Given the encouraging results of [10], one may ask whether the $\mathrm{𝖥𝖯𝖳}$ algorithm of Theorem 1 can be extended to the mixed-integer, separable convex case. The a priori intuition leans positive: in 1990, Hochbaum and Shanthikumar [56] have published an influential paper titled “Convex separable optimization is not much harder than linear optimization” which shows that this is true in the case of IP with a totally unimodular $A$. Similarly, Chubanov’s algorithm [16] reduces continuous separable convex optimization to a polynomial number of linear optimization problems.

In [9], we go directly against this intuition, in fact, we show that the mixed integer separable convex case exhibits unexpected behavior both when compared to the fully integer cases, and to the linear cases. We begin with the regime of few rows and small coefficients:

This improves the current state-of-the-art, double-exponential bound for MIP with few rows and small coefficients to single-exponential, even when the target function is non-linear. Until now, the best way to solve a MIP with few rows and small coefficients would be to remove duplicate columns from $A$ in a preprocessing step, and then use Lenstra’s algorithm [75].

The structural result behind Theorem 5 is an upper bound on the elements of the mixed Graver basis of $A$. We show this bound using a “packing lemma”, powered by an old result from additive combinatorics [84] recently highlighted by Paat et al. [85]. Using this bound we show that, for any continuous or integer optimum, there is a mixed-integer optimum which may require several mixed-integer Graver steps to get to, but only one of those steps will be non-zero in the integer part. Thus, an integer or continuous optimum is always “almost correct” in the integer part. Once the integer part is correctly assigned, we get a purely continuous residual problem, which is polynomial-time solvable.

Set $𝕏={\mathbb{Z}}^z\times {ℝ}^q$. Consider the problem where we allow the bounds $𝐥,𝐮\in 𝕏$ and right-hand side $𝐛\in {ℝ}^m$ to be fractional:

Already deciding feasibility of this variant is $\mathrm{𝖭𝖯}$-hard for totally unimodular matrices [17]. In a way, MILP${}_{\text{frac}}$ can be seen as a special case of MIP (even with integer $𝐛,𝐥,𝐮$), because a separable convex objective $f$ can be used to model non-integer lower bounds and right-hand sides. For the case of 2-stage constraints, we give an $\mathrm{𝖷𝖯}$ algorithm:

This result turns out to be likely optimal, as we show that MIP with integral data is $𝖶[\mathrm{𝟣}]$-hard when $A$ is a 2-stage matrix with blocks of size bounded by a parameter and ${\Vert A\Vert }_{\mathrm{\infty }}=1$ already for linear objective functions. Moreover, we show that Theorem 6 cannot be extended to the related case of $n$-fold constraint structure: MILP${}_{\text{frac}}$ with integral bounds but fractional right hand sides is $\mathrm{𝖭𝖯}$-hard when $A$ is an $n$-fold matrix with blocks of constant dimensions and ${\Vert A\Vert }_{\mathrm{\infty }}=1$.