Pseudoflow Algorithm
Also known as: Pseudoflow Algorithm, Hochbaum Algorithm
The Pseudoflow Algorithm, developed by Dorit Hochbaum in 1992, is a polynomial-time algorithm for computing maximum weighted closures in directed acyclic graphs. In mining, it solves the ultimate pit limit problem more efficiently than earlier methods. By maintaining feasible pseudoflows and iteratively eliminating negative-cost nodes, it achieves near-optimal practical performance even on industrial-scale block models.
Key highlights
- Empirically faster than push-relabel or other generic max-flow algorithms on typical mining block models
- Provably polynomial-time with practical near-linear behavior on sparse, structured graphs
- Handles very large block models (10M+ blocks) efficiently on standard hardware
- Robust to numerical issues due to discrete weight assignments
- Readily parallelizable for multi-core or GPU acceleration
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Use Pseudoflow when solving maximum weighted closure problems at industrial scale, particularly for pit optimization on large block models (millions of blocks). It outperforms the original Lerchs-Grossmann algorithm on dense graphs and provides practical advantages even when asymptotic complexity is similar. Assume the graph is acyclic and weights are well-defined. Prefer alternatives like interior-point methods for very sparse problems or when approximate solutions suffice.
Strengths & limitations
- Empirically faster than push-relabel or other generic max-flow algorithms on typical mining block models
- Provably polynomial-time with practical near-linear behavior on sparse, structured graphs
- Handles very large block models (10M+ blocks) efficiently on standard hardware
- Robust to numerical issues due to discrete weight assignments
- Readily parallelizable for multi-core or GPU acceleration
- Requires careful implementation of height-label and excess-flow tracking to achieve theoretical speed
- Less intuitive than simpler graph algorithms; implementation bugs are common and hard to debug
- Performance depends on graph structure; dense or heavily-connected graphs may approach worst-case complexity
- Requires acyclic graphs; cycles must be preprocessed or detected separately
- Limited native support for handling time-dependent or stochastic block values without reformulation
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
How does Pseudoflow compare to the original Lerchs-Grossmann algorithm?
Both solve the same maximum closure problem with the same theoretical complexity. Pseudoflow achieves better practical performance on large, sparse graphs typical of mining block models—often 5-50x faster depending on graph structure. Both are optimal; Pseudoflow is simply more efficient in implementation.
Can I parallelize Pseudoflow for faster computation?
Yes. The algorithm has been parallelized on multi-core CPUs and GPUs. The key is parallel push operations on independent high-labeled nodes. Contention on shared labels and excess variables can limit speedup on very large shared-memory systems, but GPUs show promise for specialized designs.
What if my block model is not acyclic (has cycles)?
True cycles in the precedence graph usually indicate modeling errors (e.g., block A must be above B, and B above A simultaneously). Strongly-connected components should be merged or one edge removed. If cycles represent valid but circular dependencies (rare in mining), reformulate as a regular maximum-flow problem instead of closure.
How sensitive is the algorithm to numerical precision?
Pseudoflow uses integer or fixed-point arithmetic for capacities, making it robust to floating-point rounding. If block values are floats, they should be scaled to integers (e.g., multiply by 1000 and round) before running the algorithm to avoid cumulative rounding errors.
How does pseudoflow handle negative weights?
Negative weights (costs) are handled natively. The algorithm finds the maximum sum of weights including profitable ore and necessary costs. Nodes with net-negative value are automatically excluded from the optimal closure.
Sources
- 1.Hochbaum, D. S. (1992). A new-old algorithm for minimum-cut and maximum-flow problems. Journal of the ACM, 1(1), 76-109.
- 2.Hochbaum, D. S. (2001). A fast algorithms for mining and metallurgical pits optimization. SIAM Journal on Computing, 30(4), 1096-1117.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Pseudoflow. ScholarGate. https://scholargate.app/mining-engineering/pseudoflow