Parameterized Algorithms for MILPs with Small Treedepth

Cornelius Brand, Martin Koutecký, Sebastian Ordyniak

Abstract

Solving (mixed) integer linear programs, (M)ILPs for short, is a fundamental optimization task. While hard in general, recent years have brought about vast progress for solving structurally restricted, (non-mixed) ILPs: $n$-fold, tree-fold, 2-stage stochastic and multi-stage stochastic programs admit efficient algorithms, and all of these special cases are subsumed by the class of ILPs of small treedepth. In this paper, we extend this line of work to the mixed case, by showing an algorithm solving MILP in time $f(a,d) \textrm{poly}(n)$, where $a$ is the largest coefficient of the constraint matrix, $d$ is its treedepth, and $n$ is the number of variables. This is enabled by proving bounds on the denominators of the vertices of bounded-treedepth (non-integer) linear programs. We do so by carefully analyzing the inverses of invertible submatrices of the constraint matrix. This allows us to afford scaling up the mixed program to the integer grid, and applying the known methods for integer programs. We trace the limiting boundary of our approach, showing that naturally related classes of linear programs have vertices of unbounded fractionality. Finally, we show that restricting the structure of only the integral variables in the constraint matrix does not yield tractable special cases.

Introduction: The Challenge of Mixed Integer Programming

Mixed Integer Linear Programming (MILP) is a cornerstone of mathematical optimization, essential for applications ranging from logistics to power grid management. Despite its utility, MILP is NP-hard, necessitating the search for "islands of tractability"—specific structural properties that allow for efficient solving.

Recent breakthroughs have shown that pure Integer Linear Programs (ILPs) are solvable in near-linear time when the constraint matrix has small coefficients and small treedepth. Treedepth measures the hierarchical dependency between variables. However, extending these results to MILPs—where some variables are continuous—is non-trivial. Continuous variables can take on highly fractional values with massive denominators, complicating the "discretization" techniques used for pure ILPs.

Methodology: Bounding Fractionality via Structural Decomposition

The authors propose a strategy of reduction through fractionality bounding. The core technical challenge is proving that for any MILP with a constraint matrix $A$ of treedepth $d$ and max coefficient $a$, there exists an optimal solution where continuous variables are rational numbers with denominators bounded by a function $g(a, d)$, independent of the total number of variables $n$.

Recursive block structure of the constraint matrix used in the fractionality analysis.

To achieve this, the authors analyze the structure of the constraint matrix $A$ recursively. As shown in the figure above, the matrix can be decomposed into blocks that reflect the hierarchical nature of treedepth. By examining the inverses of invertible submatrices within this structure, they demonstrate that the "fractionality" (the size of the denominators) does not explode as the problem size grows.

Once the maximum possible denominator $M$ is bounded, the MILP can be scaled by $M!$, effectively transforming continuous variables into integers on a fine grid. This reduces the MILP to a pure ILP, which can then be solved using existing state-of-the-art fixed-parameter tractable (FPT) algorithms.

Key Insights: Treedepth vs. Treewidth

A pivotal insight of this work is the distinction between treewidth and treedepth. While treewidth is a common parameter for making graph problems tractable, the authors prove it is insufficient for MILPs. They show that even with constant treewidth, the fractionality of solutions can grow exponentially with $n$. Treedepth is the "stronger" parameter required to maintain bounded fractionality.

Furthermore, the research establishes that structural restrictions must apply to the entire constraint matrix. Restricting only the integer variables while allowing continuous variables to interact arbitrarily remains NP-hard.

Results and Implications

The primary result is Theorem 1, establishing that MILP is Fixed-Parameter Tractable (FPT) when parameterized by the maximum coefficient $||A||_\infty$ and the treedepth $d$. The resulting algorithm runs in $f(a, d) \cdot \text{poly}(n)$ time.

This framework provides the first near-linear time FPT algorithms for several important classes of problems, including:

  • 2-stage stochastic MILPs
  • n-fold MILPs

By providing a computable bound $g(a, d)$ for denominators, the work offers a theoretical guarantee for discretization-based solvers.

Limitations and Future Directions

While the algorithm is theoretically "near-linear," the constant factor $f(a, d)$ is likely very large (potentially a tower of exponentials), making it a proof-of-concept rather than a tool for immediate industrial use for large $d$.

Future work may explore extending this to separable convex functions, which is currently difficult because they can lead to irrational solutions. Additionally, investigating hybrid parameters like "torso-width" might allow for more flexible variable interactions while preserving tractability.

Summary updated

Abstract

Solving (mixed) integer (linear) programs, (M)I(L)Ps for short, is a fundamental optimisation task with a wide range of applications in artificial intelligence and computer science in general. While hard in general, recent years have brought about vast progress for solving structurally restricted, (non-mixed) ILPs: n-fold, tree-fold, 2-stage stochastic and multi-stage stochastic programs admit efficient algorithms, and all of these special cases are subsumed by the class of ILPs of small treedepth. In this paper, we extend this line of work to the mixed case, by showing an algorithm solving MILP in time f(a,d)poly(n), where a is the largest coefficient of the constraint matrix, d is its treedepth, and n is the number of variables. This is enabled by proving bounds on the denominators (fractionality) of the vertices of bounded-treedepth (non-integer) linear programs. We do so by carefully analysing the inverses of invertible sub-matrices of the constraint matrix. This allows us to afford scaling up the mixed program to the integer grid, and applying the known methods for integer programs. We then trace the limiting boundary of our "bounded fractionality" approach both in terms of going beyond MILP (by allowing non-linear objectives) as well as its usefulness for generalising other important known tractable classes of ILP. On the positive side, we show that our result can be generalised from MILP to MIP with piece-wise linear separable convex objectives with integer breakpoints. On the negative side, we show that going even slightly beyond such objectives or considering other natural related tractable classes of ILP leads to unbounded fractionality. Finally, we show that restricting the structure of only the integral variables in the constraint matrix does not yield tractable special cases.
BibTeX
@inproceedings{brand2021parameterized,
  author = {Cornelius Brand and Martin Koutecký and Sebastian Ordyniak},
  title = {{Parameterized Algorithms for MILPs with Small Treedepth}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i14.17454},
}
Figure