A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma

Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, Meirav Zehavi

Abstract

Integer Linear Programming (ILP) is a cornerstone of optimization, yet its general form remains NP-complete. For problems exhibiting a specific block structure known as $n$-fold ILP, fixed-parameter tractable (FPT) algorithms exist, though they are often characterized by high complexity and reliance on iterative augmentation via Graver bases. This paper presents a simplified, non-iterative algorithm specifically for "Combinatorial $n$-fold" ILPs—where diagonal blocks are rows of ones. By leveraging the Steinitz Lemma, the approach reduces the ILP to a shortest-path problem in a directed acyclic graph (DAG), achieving state-of-the-art theoretical performance for problems such as Lobbying and Binary Closest String.

Introduction

Integer Linear Programming (ILP) is frequently encountered in scheduling, social choice, and bioinformatics. While general ILP is computationally difficult, many real-world instances possess a structured constraint matrix. A prominent example is the $n$-fold ILP, where the constraint matrix consists of a series of repeated blocks.

Traditionally, $n$-fold ILPs are solved using the "augmentation framework." This involves finding an initial feasible solution and iteratively improving it using a Graver basis—a set of minimal vectors that allow for local improvements. However, these methods are often complex to implement and require solving continuous linear relaxations. This research explores a more direct approach for a sub-class called Combinatorial $n$-fold ILPs, characterized by diagonal blocks consisting of rows of ones, aiming for a simpler and more efficient solution path.

Methodology

The Steinitz Lemma

The core theoretical engine of the proposed algorithm is the Steinitz Lemma. This geometric result states that given a set of vectors that sum to zero, there exists a permutation of these vectors such that every prefix sum remains within a bounded distance from the origin. The authors adapt this lemma to manage the cumulative constraints of the ILP, ensuring that as variables are assigned across blocks, the solution does not "drift" beyond the feasible region.

Algorithmic Framework

The algorithm departs from iterative methods, instead using a sequence-ordering approach divided into four primary stages:

  1. Balancing: A greedy "imbalance-based" strategy is employed to distribute variables across blocks, minimizing the initial discrepancy between local and global constraints.
  2. Vector Reordering: A generalized version of the Steinitz Lemma is applied to the variable assignments to ensure that partial sums of the constraints remain bounded.
  3. Graph Construction: The problem is mapped onto a weighted Directed Acyclic Graph (DAG). In this graph, vertices represent the states of partial sums, edges represent the selection of specific columns (variables) within a block, and edge weights correspond to the objective function costs.
  4. Shortest Path Computation: The optimal ILP solution is found by identifying the shortest path in the DAG using standard algorithms like Breadth-First Search (BFS).

Key Insights

Direct vs. Iterative Solvers

By bypassing Graver bases and LP relaxations, the algorithm is significantly more straightforward than previous $n$-fold solvers. It treats the optimization as a single-pass pathfinding problem rather than an iterative refinement process.

Parameterization by $q$

The research identifies the sum of the right-hand side of local constraints ($q$) as a critical parameter. The algorithm's linear dependence on $q$ allows it to outperform general-purpose solvers in scenarios where $q$ is relatively small.

Handling Inequalities

The framework provides a robust method for incorporating slack variables. This allows the algorithm to handle $\le$ and $\ge$ constraints without significantly increasing the state space of the DAG, maintaining the efficiency of the core equality-based solver.

Results and Complexity

The algorithm yields significant theoretical speedups for several classic problems:

  • Lobbying: The algorithm achieves a running time of $2^{O(m^2)} \cdot w^{O(1)}$, a substantial improvement over the previous best of $m^{O(m^2)}$.
  • Binary Closest String: The achieved running time of $2^{O(k^2)} \cdot L^{O(1)}$ matches the hypothesized lower bound, suggesting this approach is essentially optimal for this parameterization.
  • General Complexity: For a matrix with $n$ blocks, $t$ columns per block, and maximum entry $\Delta$, the algorithm runs in $O(nt \cdot (n\Delta(n + 1 + 4r))^r \cdot q)$.

Discussion and Limitations

While the algorithm provides a simpler and faster path for Combinatorial $n$-fold ILPs, it is currently restricted to cases where diagonal blocks are rows of ones. Extending this "simple" Steinitz-based approach to general $n$-fold structures remains an open question. Additionally, because the complexity is tied to the parameter $q$, the algorithm is not fully FPT if $q$ grows exponentially relative to the input size. Future research may focus on refining the bounds of the $b$ vector (the right-hand side of the equations) to further tighten the complexity results.

Summary updated

BibTeX
@inproceedings{gupta2025simple,
  author = {Sushmita Gupta and Pallavi Jain and Sanjay Seetharaman and Meirav Zehavi},
  title = {{A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma}},
  booktitle = {IPEC},
  year = {2025},
  doi = {10.4230/lipics.ipec.2025.14},
}
Figure