On Circuit Diameter Bounds via Circuit Imbalances

Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh

This paper, recently updated in June 2024, makes significant strides in the field of polyhedral geometry and linear programming (LP). It provides new, tighter bounds on the circuit diameter of polyhedra and introduces an efficient algorithm for solving LPs using circuit augmentations.

TL;DR

The authors prove a new upper bound on the circuit diameter of polyhedra that depends only logarithmically on the "circuit imbalance" ($\kappa_A$) of the constraint matrix. They also present a modified minimum-ratio circuit-canceling algorithm that, unlike previous versions, is guaranteed to solve LPs in a strongly polynomial number of steps relative to this imbalance measure.

What Problem Does This Paper Address?

In the world of linear programming, we often visualize the feasible region as a polyhedron. A central question in combinatorial geometry is the Hirsch Conjecture, which suggested that the "diameter" of such a polyhedron (the maximum number of edges needed to get from one vertex to another) is relatively small. While the original conjecture was disproved, the "Polynomial Hirsch Conjecture"—the idea that the diameter is polynomial in the number of facets and dimensions—remains one of the biggest open problems in the field.

Circuit diameter is a natural relaxation of this concept. Instead of being restricted to moving along the edges of the polyhedron, a "circuit walk" allows movement along any circuit direction (elementary vectors of the constraint matrix's kernel). This paper tackles the challenge of bounding this diameter and finding efficient ways to navigate these paths algorithmically, especially when the constraint matrix $A$ has "unbalanced" entries.

Methods

The authors employ several key theoretical and algorithmic tools:

  1. Conformal Circuit Decomposition: This is a way of breaking down any direction into a set of "sign-compatible" circuits. The authors use this to develop a "shoot-towards-the-optimum" scheme for bounding the diameter.
  2. Circuit Imbalance Measure ($\kappa_A$): This parameter measures the maximum ratio between the magnitudes of non-zero entries in any circuit of the matrix $A$. It’s a sophisticated way to quantify how "complex" or "skewed" the geometry of the polyhedron is.
  3. Minimum-Ratio Circuit Canceling: This is a classic rule for choosing which direction to move in during an optimization process. Historically, this rule wasn't guaranteed to terminate in finite time for general LPs.
  4. The "Support-Circuit" Step: The authors introduce a crucial modification to the standard algorithm. By occasionally performing a step that removes circuits from the "support" (the set of non-zero variables) of the current solution, they force the algorithm to converge efficiently.

Datasets

As a theoretical paper in discrete optimization and geometry, no empirical datasets or benchmarks were used. The results are proven mathematically for all possible polyhedra and constraint matrices within the defined classes.

Key Insights and Ideas

  • Logarithmic Breakthrough: Previous bounds on circuit diameter often had a linear or polynomial dependence on the matrix structure (like the maximum subdeterminant). This paper shows that the dependence is actually logarithmic ($\log \kappa_A$). This means that even if the matrix is highly "unbalanced," the circuit diameter doesn't explode.
  • Finiteness through Sparsification: The "aha moment" for the algorithm is the realization that standard circuit-canceling fails because it can get stuck in infinite loops of tiny improvements. By adding the Support-Circuit step to zero out coordinates, the authors effectively "simplify" the problem as it progresses, ensuring a strongly polynomial termination.
  • Proximity as a Tool: The authors use "proximity results"—mathematical guarantees that if a solution is "close enough" to the optimum in a certain sense, some variables must be zero in the final optimal solution. This allows the algorithm to "fix" variables and reduce the problem's dimensionality over time.

Key Results

  • New Diameter Bound: For a polyhedron in standard form $\{x : Ax = b, x \ge 0\}$, the circuit diameter is bounded by $O(m \min\{m, n - m\} \log(m + \kappa_A) + n \log n)$.
  • Strongly Polynomial Cases: If the entries of the matrix $A$ have a bit-length that is polynomial in $n$, this bound becomes strongly polynomial.
  • Efficient Optimization: The proposed algorithm solves a general LP in $O(mn^2 \log(n + \kappa_A))$ augmentation steps. This is a significant improvement for LPs where $\kappa_A$ is manageable.
  • Generalization: The authors show how these results, initially derived for standard equality form, can be extended to capacitated LPs ($0 \le x \le u$) and LPs in general form ($Ax = b, Bx \le d$).

Limitations and Future Work

  • Dependence on $\kappa_A$: While the logarithmic dependence is a major improvement, the bound still depends on the matrix entries. The ultimate goal—a bound purely in terms of $n$ and $m$ (the true Polynomial Hirsch Conjecture for circuits)—remains elusive.
  • Oracle Complexity: The algorithm assumes the existence of a "Ratio-Circuit" oracle. While finding such a circuit is simpler than solving the full LP, it is still a non-trivial computational task in practice.
  • Computing $\kappa_A$: The value of $\kappa_A$ itself is NP-hard to compute exactly. The authors bypass this using a "guessing" procedure, but a more direct way to relate these bounds to easily computable matrix properties would be valuable.

Summary updated

BibTeX
@inproceedings{dadush2022circuit,
  author = {Daniel Dadush and Zhuan Khye Koh and Bento Natura and László A. Végh},
  title = {{On Circuit Diameter Bounds via Circuit Imbalances}},
  booktitle = {IPCO},
  year = {2022},
  doi = {10.1007/978-3-031-06901-7\_11},
}
Figure