Mining Problem


 Pit Mining:

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 bi 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 xj 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 (bi > 0) and an arc from each node with negative value (bi < 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 bi and for arc (j, t) we set the capacity to -bj.

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.


[DO92] P.A. Dowd and A.H. Onur, "Optimising Open Pit Design and
Sequencing," Proc. 23rd International APCOM Symposium,
(1992), 411-422.

[FF57] L.R. Ford, Jr. and D.R. Fulkerson, "A Simple Algorithm for
Finding Maximal Network Flows and an Application to the
Hitchcock Problem," Canad. J. Math., 9 (1957), 210-218.

[H96] D. S. Hochbaum "A new-old algorithm for minimum cut in closure graphs,"

manuscript June (1996).

[HC96] D. S. Hochbaum and A. Chen "Performance analysis and best

implementations of old and new algorithms for the Open - Pit Mining
Problem", (with A. Chen) manuscript, May (1996).

[HC92] P. Huttagosol and R. Cameron, "A Computer Design of

Ultimate Pit Limit by Using Transportation Algorithm," Proc.
23rd International APCOM Symposium, (1992), 443-460.

[JS71] T.B. Johnson and W.R. Sharp, "A Three-Dimensional Dynamic

Programming Method for Optimal Ultimate Open Pit Design,"
U.S. Bureau of Mines, Report of Investigation 7553, (1971).

[Kob74] S. Koborov, "Method for Determining Optimal Open Pit

Limits," Rapport Technique ED 74-R-4, Dept. of Mineral
Engineering, Ecole Polytechnique de Montreal, Canada, Feb. 1974.

[Koe82] E. Koenigsberg, "The Optimum Contours of an Open Pit Mine:

An Application of Dynamic Programming," Proc. 17th
International APCOM Symposium, (1982), 274-287.

[LG64] H. Lerchs, I.F. Grossmann, "Optimum Design of Open-Pit

Mines," Transactions, C.I.M., Vol. LXVIII (1965) 17-24.

[Pic76] J.C. Picard, "Maximal Closure of a Graph and Applications to

Combinatorial Problems," Management Science, 22 (1976),

[RP77] R.H. Robinson and N.B. Prenn, "An Open Pit Design Model,"

Proc. 15th International APCOM Symposium, (1977), 1-9.

[ZK92] Y. Zhao and Y.C. Kim, "A New Optimum Pit Limit Design

Algorithm," Proc. 23rd International APCOM Symposium,
(1992), 423-434.

[ Open Pit Mining | Instructions | Details | See a Demo | Try It! ]


Copyright 1997 Professor Dorit Hochbaum