Are you looking for a faster method for pit optimization? We've got you covered with this new GEOVIA Whittle series introducing the pseudoflow method. In this post we are making a review of the Lerch-Grossmann method and introduce the mathematical concepts behind pseudoflow.

Authors: Victor Xiaoyu Bai, George Turczynski, Nathaniel Baxter, @HS ​​​​​​​, @SR, @DP

INTRODUCTION

GEOVIA Whittle has implemented a new pit optimization engine based on the pseudoflow algorithm. This pseudoflow algorithm creates the same optimal pits achieved using the traditional Lerchs-Grossmann algorithm (LG), but with far more time efficiency. The LG method of pit optimization has been the industry standard and it is understood that strategic mine planners will be reluctant to trust a new method. To address their concerns, this paper explains the mathematical concepts on which pseudoflow has been built and how this has been implemented to solve mining problems. A comparative study with LG is detailed, showing the improved performance of pit optimization using pseudoflow.

FROM LERCHS-GROSSMANN TO PSEUDOFLOW: A SHORT REVIEW

The general pit optimization procedure works based on two inputs: block values and pit slopes, where the slopes introduce constraints on removal precedence of the blocks. The output of optimization is essentially a selection of blocks representing pits of valid slopes that yield maximum profit. Investigations for solving the pit optimization problem using a computer algorithm started in the 1960s. The Lerchs-Grossmann algorithm [1] was published in 1965 and was one of the earliest methods to produce the optimal pit. In the 1980s, the first industrial package with the LG algorithm was implemented in Whittle Three-D. The LG method has become the industry standard for pit optimization and also part of the university syllabus for mining engineers. The main issue with the LG method is the significant amount of time that is required to determine the optimal pit as the block models and pits increase in size and scale.

After the publication of LG, finding the optimal pit was no longer a challenging task. In academia, significant effort has been focused on searching for more efficient pit optimization algorithms. Many promising alternatives have been delivered. In 1976, Picard proved that the pit optimization problem could be solved with more efficient maximum flow algorithms [2]. In 1988, Goldberg and Tarjan developed a highly efficient maximum flow algorithm called the Push-Relabel method [3]. Notably, in 2008, Hochbaum published a pseudoflow algorithm [4], which was demonstrated to be more efficient than the LG and other prevalent maximum flow algorithms, such as the PushRelabel method [5], [6]. GEOVIA has recognized the power of the pseudoflow algorithm and has developed a unique version for GEOVIA Whittle.

MATHEMATICAL CONCEPTS BEHIND PSEUDOFLOW

Understanding how the pseudoflow algorithm works requires a deep knowledge of mathematics and computer science. It involves two layers of questions:

1) How to model pit optimization with mathematical concepts, such as “set” and “graph”

2) How the algorithm solves the mathematical (graph) problems

Understanding the first question requires an introduction to some “graph” concepts. The second question is a specialized question in operational research and will not be covered in this paper. More detailed explanations of these questions can be found in reference papers [4] and [6]. The following section addresses the first question.

Graph Concepts and Pit Optimization

The pit optimization process typically uses a block model with fixed block values as an input. The pit slopes requirement and mining sequence can be expressed by the dependencies among blocks.

For example, in Figure 1-1, a simple 2D block model consists of 10 blocks indexed from “a” to “j” (the value is marked on the top-right corner of a block). To maintain 45 degree slopes, a typical block dependency is like that shown in Figure 1-2, i.e., to mine block “c”, the blocks “g”, “h”, and “i” must be removed first. The optimization problem is to find a set of blocks that respects the block dependency constraints and gives the highest total block value.

This problem is commonly represented by a mathematical concept called a “graph”. A graph is a conceptual structure consisting of nodes and arcs. In the pit optimization case, a node represents a block, and an arc between two nodes represents the dependency relation of two blocks for the excavation sequence and slope constraint. A node can carry a weight value, to represent the value of the block. Figure 2 shows a graph representation of the pit optimization problem in Figure 1. We will use this example to demonstrate how to use the graph-based method to get the optimal pit. The concept is general and can be extended to more complex cases. Even for creating pits with a large 3D block model, the same process applies, but with an increased dimension and number of nodes and arcs.

Maximum Closure and Optimal Pit

The precise definition of a pit with valid slopes is termed a “closed set” or “closure”. It refers to a set of nodes that have no arcs out of the set. For example, in Figure 3, the set {b, f, g, h} is a closed set and {d, h, i, j} is another closed set; but set {b, c} is not closed, because “b” has available arcs to “f”, “g”, “h”; and “c” has an available arc to “g”, “h”, “i”. A closed set of blocks is free to be removed and does not depend on the removal of other blocks. So, finding an optimal pit is the process of finding a closure with maximum total value.

▶ In our next post​​​​​​​, we will present the Maximum flow method as an alternative to generating an optimal pt. 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 ​​​​​​​best practice ​​​​​​​pit optimization ​​​​​​​