Introduction
A central question in the geometry of polyhedra and the theory of linear programming (LP) is the relationship between the combinatorial structure of a feasible region and the efficiency of algorithms traversing it. Published in Mathematical Programming (2024), this work provides significant advancements in bounding the "circuit diameter" of polyhedra. By utilizing the "circuit imbalance" parameter ($\kappa_A$), the authors establish the tightest bounds to date and introduce a faster class of augmentation algorithms.
The Combinatorial vs. Circuit Diameter Problem
In LP, feasible regions are represented as polyhedra. The combinatorial diameter—the maximum shortest path between any two vertices moving along edges—is a fundamental metric. While the Hirsch conjecture (1957) suggested a linear bound, its 2012 refutation shifted focus toward the circuit diameter.
The circuit diameter is a relaxation allowing movement along "circuits"—the most basic directions defined by the constraint matrix $A$—rather than just edges. Finding a polynomial bound for circuit diameter remains a major challenge. Previous bounds often relied on the bit-complexity of inputs or resulted in exponential values. This paper addresses this by seeking bounds dependent solely on the structural properties of $A$.
Methodology and Key Parameters
The authors leverage several geometric and algorithmic innovations:
- Circuit Imbalance ($\kappa_A$): This parameter measures the maximum ratio between the absolute values of any two non-zero entries in the elementary vectors (circuits) of matrix $A$. For totally unimodular matrices (e.g., in network flows), $\kappa_A = 1$.
- Conformal Circuit Decompositions: Any direction within the polyhedron can be decomposed into a sum of sign-compatible circuits. This allows for a strategy of selecting the most improving circuit at each step to approach an optimum.
- Modified Minimum-Ratio Rule: To ensure convergence in circuit augmentation algorithms, the authors introduce a "Support-Circuit" subroutine. This periodically removes redundant circuits from the current solution's support, overcoming the limitations of standard minimum-ratio rules.
- Proximity Arguments: Using Hoffman-type results, the authors prove that variables falling below a certain threshold relative to a dual solution must be zero in the final optimum, allowing for dimensionality reduction during the search.
Key Results
The paper's primary contributions are both theoretical and algorithmic:
-
Improved Circuit Diameter Bound: For a system defined by $\{x \in \mathbb{R}^n : Ax = b, 0 \le x \le u\}$, the circuit diameter is bounded by: $$O(m \min\{m, n - m\} \log(m + \kappa_A) + n \log n)$$ This bound is independent of the right-hand side vector $b$, making it applicable even to polyhedra defined by irrational numbers.
-
Algorithmic Complexity: The proposed modified circuit augmentation algorithm solves an LP in: $$O(mn^2 \log(n + \kappa_A)) \text{ steps.}$$ This represents a "strongly polynomial" bound relative to the circuit imbalance, significantly improving upon previous linear or polynomial dependencies on $\kappa_A$.
Discussion and Future Directions
While this work significantly clarifies the circuit diameter, the combinatorial diameter remains an open problem. A bound of poly($n, \log \kappa_A$) for combinatorial diameter is a key future goal. Additionally, while the "Ratio-Circuit" oracle used in the algorithm is implementable, further research into more efficient practical implementations is needed. As a theoretical result, the practical performance of these algorithms compared to established Simplex or Interior Point methods is yet to be empirically determined, though the logarithmic dependence on $\kappa_A$ suggests high potential for efficiency in complex constraint systems.
Summary updated