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 our previous post​​​​​​​ we reviewed of the Lerch-Grossmann method and introduced the mathematical concepts behind pseudoflow. Today, we are introducing the Maximum Flow Method as an alternative to generating an optimal pit.

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

Maximum Flow Method—An Alternative to Generating an Optimal Pit

Research has proven that searching directly for the maximum closure is not the most efficient method of finding it. A more efficient method has been proven that involves solving a variant version of a graph, i.e., flow graph or flow network. For ease of understanding, an example of a flow graph would be a network of pipes for sending water from one city to another. A flow graph contains two additional special nodes, the source node (where the flow starts) and the sink node (where the flow finishes). Also, each arc, like a pipe, has a capacity property and allows a flow, up to the capacity limit, to pass through. The flow and capacity along an arc must be positive. The nodes represent a joining of pipes, so the amount of flow into a node must equal the total flow out of the node, which is called the flow balance criteria. In this network, searching for a flow distribution with maximum total flows that move into the sink node (or equally go out of the source node) is termed the maximum flow problem. It has been proved that the maximum flow problem is equivalent to the maximum closure problem [2].

• To get a flow graph, we need to make a few changes to the graph in Figure 2:
• Add two special nodes: source node and sink node
• For all the existing arcs (blue), assign infinite capacities
• Add links from source to all positive nodes, with the capacities equal to the weight of the nodes
• Add links from negative nodes to sink, with the capacities equal to the absolute weight value of the nodes
• Remove the weights on nodes

The converted flow graph is shown in Figure 4-1. We also give an example of arbitrarily assigned flows that satisfy the flow balance, shown in Figure 4-2.

The relation between the flow and mining concepts is not as straightforward as the relation between a closure and a pit. One way to describe this is to consider the ore as the water stored in a source city that as much as possible needs to be sent to a destination city through a pipe network. The source station connects all the ore blocks, and the destination connects all the wastes. In the network, the economic value of a block is not reflected on a node, but is measured by the capacity of the pipe (arc) that connects it with the source or the destination city. Since the pipes representing block dependency have unlimited capacity, the bottlenecks of the networks are the pipes connected to the source or destination. Three types of pipes can be identified: “waste-to-destination”, “source-to-ore”, and “block-to-block”. The flow assignment in each type of pipe can be interpreted in different mining senses, respectively:

1) Pushing flow from a “waste node” to a destination is similar to using the underlying ore value to pay for the waste block. When a flow saturates a pipe that links to the destination (flow amount equals the capacity), it means that the corresponding waste block can be paid off by its underlying ores, for example, the node “f”, “g” and “h” in Figure 4-2. Otherwise, if a “waste-to-destination pipe” is not saturated, then the waste block is not paid off by the ores, such as node “a”, “i”, “j” and “e” in Figure 4-2. The flow balance criteria imply that the flow that goes into a “waste node” cannot exceed its out-pipe capacity (absolute block value), thus guaranteeing that the waste block is not paid for multiple times.

2) Pushing flows from a source into an “ore node” means passing the ore value down, within the capacity limits, to pay for the necessary wastes. If a “source-to-ore” pipe is not saturated while at the same time the flow is balanced and no more can be pushed downstream, such as pipe “s-b” in Figure 4-2, this means that the ore is sufficient to pay off the overlying wastes and has residual value left. Otherwise, if an ore block is not high enough to pay for the linked wastes, then the pipe connected to the source would be saturated, such as pipe “s-d” in Figure 4-2.

3) The unlimited capacity pipes that link block-to-block guide the flow to the related “waste nodes”, and allow the ore value passing through freely to pay for all the overlying wastes.

When the maximum flow is found, it ensures that all the ores have been utilized to pay for the necessary wastes. As an opposite example, in Figure 4-2, the node “c” is not considered to be passing any flow through. So the total flow is 4 and has not reached the maximum flow of 5 (shown in the following section), therefore additional distribution is needed to reach the maximum flow.

Assume that a maximum flow solution is found as shown in Figure 5-1, by any possible method, say pseudoflow. To get the optimal pit, we still need to convert the maximum flow solution to a maximum closure. To do this, we first break the saturated arcs (blue dashed arcs in Figure 5-2). This separates the sink node from the waste blocks that can be paid off by the underlying ore blocks (such as blocks “f”, “g”, “h” and “i”), and also cuts the paths from the source node to the ore blocks that cannot afford the overlying wastes values (such as block “d”). Then we search all the nodes that can be reached by the source node, as shown in Figure 5-2. Those nodes (except the source) are the maximum closure set. The reason for doing this relates to the “max-flow min-cut theorem” [7] and the proof of equivalency of maximum flow and maximum closure in the research paper [2].

▶ In our next post​​​​​​​, we will examine the maximum flow problem and introduce the pseudoflow engine in Whittle, comparing the pseudoflow vs LG. method

​​​​​​​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 ​​​​​​​