Pit Mining:
  Demo
  Application
  Instructions
  Details

Detailed Description

Open-pit mining is a surface mining operation in which blocks of earth are dug from the surface to extract the ore contained in them. During the mining process, the surface of the land is excavated, forming a deeper and deeper pit until the mining operation terminates. The final shape of this open pit is determined before the mining operation begins. To design the optimal pit--one that maximizes profit--the entire mining area is divided into three-dimensional blocks. Using geological information from drill cores, the value of the ore in each block is estimated. Additionally, the cost of mining each particular block is determined, thus we can assign a profit value to each block in the mine. The optimal pit design problem is then to maximize the total profit of the mine, while satisfying constraints on the slope of the pit walls and constraints that allow underlying blocks to be mined only after blocks on top of them.

Network Model

The pit design problem can be represented using a directed graph, G = (V,A). We create a node for each block in the mining area and assign a weight b_i which represents the profit value of mining that block. There is a directed arc from node i to node j if block i cannot be extracted before block j, which is on a layer immediately above block i. To decide which blocks to extract in order to maximize profit, we find a maximum weight set of nodes in the graph such that all successors of all nodes in the set are also included in the set. Such a set is called a maximum closure of G.

Solving with Minimum Cut Algorithm

We can show that the problem of finding a maximum closure in a graph reduces to a minimum cut problem. The integer programming formulation of the problem reveals this structure. Let x_j be a binary variable that is 1 if node j is in the closure and 0 otherwise. The integer programming formulation is thus:

Each row of the constraint matrix has exactly one 1 and one -1--a structure indicating that the matrix is totally unimodular. More specifically, this indicates that the problem is the dual of a maximum flow problem.

Picard [Pic76] demonstrated that a minimum cut algorithm on a related graph G' will solve the maximum weight closure problem. To construct the graph, we add a source and sink node, s and t, V' = V + {s,tA' consists of all of the arcs A, as well as an arc from s to each original node with positive value (b_i > 0) and an arc from each node with negative value (b_i < 0) to t. The capacity of each original arc in A is set to infinity. For each arc (s, i) we set the capacity to b_i and for arc (j, t) we set the capacity to -b_j.

Next we give a simple proof of the fact that a minimum s-t cut on the above graph will generate a source set that is a maximum weight closure. First, the source set is clearly closed since any minimum cut must be finite and thus cannot any arcs from A. Let (S,S’) represent a finite cut in the graph G’. Let V⁺ represent the set of nodes with positive b values and V^- represent the set of nodes with negative b values. The capacity of the cut, C(S,S’), is given by:

where B is fixed as the sum of all node weights. Thus, minimizing the cut capacity is equivalent to maximizing the total sum of node weights in the source set of the cut.

References