Parameterized Algorithms for MILPs with Small Treedepth

Cornelius Brand, Martin Koutecký, Sebastian Ordyniak

Abstract

This paper addresses a significant gap in optimization theory by demonstrating that Mixed Integer Linear Programming (MILP) is fixed-parameter tractable (FPT) when the constraint matrix exhibits small coefficients and a bounded structural parameter known as "treedepth." By proving that these specific structures have bounded "fractionality," the authors provide a method to transform complex mixed-variable problems into pure integer ones. This reduction allows for the application of high-performance FPT algorithms originally designed for Integer Linear Programming (ILP), expanding the reach of parameterized complexity in mathematical optimization.

Introduction

Mixed Integer Linear Programming (MILP) is a fundamental tool in modern optimization, essential for applications ranging from logistics and flight scheduling to artificial intelligence planning. Unlike pure Linear Programming (LP), which is solvable in polynomial time, or Integer Linear Programming (ILP), which is NP-hard, MILP combines both discrete and continuous variables.

Recent advancements in parameterized complexity have shown that ILPs become significantly easier to solve if their constraint matrices possess a "tree-like" structure, specifically measured by small treedepth. However, the extension of these results to the mixed-variable case was previously hindered by the issue of "fractionality." In MILPs, optimal solutions for continuous variables can involve complex fractions with extremely large denominators. If these denominators grow uncontrollably, standard algorithmic techniques for integer problems fail.

Methods: From MILP to ILP

The authors' primary contribution is a formal reduction of the MILP problem to the pure integer case. This was achieved through a rigorous analysis of solution fractionality.

  1. Fractionality Analysis: The core technical achievement is Theorem 2, which proves that if a matrix has a treedepth $d$ and a maximum coefficient $a$, the denominators of the vertices of the associated polytope are bounded by a function of $a$ and $d$. This was accomplished by analyzing the inverses of sub-matrices through the lens of treedepth decomposition.
  2. Scaling to the Grid: By establishing a bound on the denominators, the authors could scale the entire MILP instance by the least common multiple of these potential denominators. This process effectively "snaps" the continuous variables onto a fine-tuned integer grid, transforming the MILP into a pure ILP without losing the optimal solution.
  3. Algorithmic Application: Once transformed, the problem can be solved using existing high-performance FPT algorithms designed for ILPs with small treedepth.
A visualization of a treedepth decomposition, illustrating the hierarchical structure used to analyze variable dependencies and bound fractionality.

Key Insights: The Uniqueness of Treedepth

A striking finding of this research is that treedepth is uniquely suited for this reduction. While other popular structural measures like treewidth or clique-width are useful for pure integer problems, they do not guarantee bounded fractionality in the mixed case. In these instances, denominators can still grow arbitrarily large, preventing a simple reduction to the integer grid.

Furthermore, the authors highlight that the interaction between integer and continuous variables must be restricted. If the interaction is arbitrary, the problem remains NP-hard even for simple structures. The research also extends these results beyond linear objectives to Mixed Integer Programs (MIP) with piece-wise linear separable convex objectives, which are common in real-world cost modeling.

Key Results and Complexity Bounds

  • Theorem 1 (FPT for MILP): MILP is Fixed-Parameter Tractable (FPT) when parameterized by the largest coefficient ($||A||_\infty$) and the treedepth ($d$). As the number of variables $n$ grows, the solving time increases only polynomially, provided the structural parameters remain small.
  • Optimal Bounds: The paper provides a concrete bound for the largest denominator: $(||A||_\infty)^{d!} (d!)^{d!/2}$. While this double-exponential bound is large, the authors prove it is nearly optimal; significant improvements are mathematically impossible.
  • Negative Results: The study demonstrates that for other classes, such as 4-block $n$-fold matrices, the bounded fractionality approach is fundamentally inapplicable because denominators can grow exponentially with the number of variables.

Conclusion and Future Work

While the double-exponential dependency on treedepth suggests that the "constant" factor in running time may be large for deep trees, this work provides a critical theoretical foundation for solving structured MILPs. Future research directions include exploring complexity when both primal and dual treedepth are bounded, investigating XP algorithms for 4-block $n$-fold MILPs, and determining the exact threshold of interaction between integer and continuous variables that maintains 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