Discover a faster method for pit optimization with the pseudoflow method in this 4 part series.
In our previous post we introduced the Maximum Flow Method as an alternative to generating an optimal pit. Today, we will examine the maximum flow problem and introduce the pseudoflow engine in Whittle, comparing the pseudoflow vs LG. method.
Authors: Victor Xiaoyu Bai, George Turczynski, Nathaniel Baxter, @HS , @SR, @DP
Maximum Flow Problem and Pseudoflow Algorithm
In the description above, we introduced how to model a pit optimization problem with the graph concept, specifically using maximum closure and maximum flow representations. We also noted that LG is a method to solve the maximum closure problem. The remaining question is, what is the procedure to find a maximum flow solution? In general, the procedure is to iteratively change the flows along the paths until the maximum flow is found. There are many maximum flow algorithms, and each algorithm uses different ways to distribute the flow with varying efficiency. The pseudoflow algorithm has been demonstrated to be one of the most efficient methods to date with respect to the time used to solve a defined problem set.
Understanding the procedure of pseudoflow and the reason for its outstanding efficiency needs very specialized mathematical knowledge. This document is not designed to be an exhaustive explanation of the pseudoflow algorithm, and more details are available in reference [4].
Pseudoflow Engine in GEOVIA Whittle
GEOVIA Whittle is powered by a new implementation of the pseudoflow algorithm with an optimized data structure. The new engine significantly speeds up the pit generation process compared to our traditional LG engine. A computation comparison of pseudoflow vs. LG is discussed below.
COMPUTATION COMPARISON AND APPLICATION CONCERNS TESTING DATA AND PARAMETERS
To demonstrate the computation speed of the Whittle pseudoflow engine, a series of testing block models were used (see Table 1 and Figure 6). The 45 degree slope angle is adopted for all cases. The number of arcs created for this slope setting is listed in Table 1. Note that with Whittle, the actual number of blocks and arcs used in the optimization is called active blocks and active arcs. (Active blocks represent the blocks that contain parcels, and all the precedent blocks need to be removed to access the blocks with parcels). Tests were done for two scenarios: one scenario uses one revenue factor (RF) to generate one pit shell; the other uses nine RFs to create nine pit shells. The creation of multiple pit shells is basically a repetition using the pseudoflow/LG across multiple RFs.
Testing Results
The computation time for the datasets and parameters are plotted in Figures 7 and 8, and listed in Table 2. Note that the collected computation time reflects the overall process of pit optimization with Whittle, including reading and writing data, as well as pseudoflow/LG process. The pseudoflow engine is faster than LG in all cases. The boost of speed is more significant as the block model becomes larger, especially for the 21.3 million block case, with the time reduced from 15 hours to 12 minutes using pseudoflow. Also, when creating nine pit shells, the speed gain from pseudoflow for creating each single pit shell accumulates and shows an even more remarkable overall improvement.
▶ In our next post we will examine factors impacting the speed of optimization, answer the precision question and memory requirements before concluding. Stay tuned!
Access all technical articles:
References
[1] H. Lerchs and I. F. Grossmann, “Optimum design of open-pit mines,” Transactions CIM, vol. LXVIII, pp. 17–24, 1965.
[2] J. C. Picard, “Maximal closure of a graph and applications to combinatorial problems,” Management Science, vol. 22, no. 11, pp. 1268–1272, 1976.
[3] A. V. Goldberg and R. E. Tarjan, “A new approach to the maximum-flow problem,” Journal of the Association for Computing Machinery, vol. 35, no. 4, pp. 921–940, Oct. 1988.
[4] D. S. Hochbaum, “The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem,” Operations Research, vol. 56, no. 4, pp. 992–1009, Aug. 2008.
[5] B. G. Chandran and D. S. Hochbaum, “A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem,” Operations Research, vol. 57, no. 2, pp. 358–376, Jan. 2009.
[6] D. C. W. Muir, “Pseudoflow, New Life for Lerchs-Grossmann Pit Optimisation,” in Orebody Modelling and Strategic Mine Planning Conference, Perth, Australia, 2004, vol. 14, pp. 97–104.
[7] C. H. Papadimitriou and K. Steiglitz, “The Max-Flow, Min-Cut Theorem,” in Combinatorial Optimization: Algorithms and Complexity, Unabridged edition., Mineola, N.Y: Dover Publications, 1998, pp. 120–128.
GEOVIA Whittle pit optimization best practice
