Mining Problem 
RIOT HOME
Pit Mining:

Detailed DescriptionOpenpit 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 pitone that maximizes profitthe entire mining area is divided into threedimensional 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 ModelThe 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 AlgorithmWe 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 1a 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 st 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[DO92] P.A. Dowd and A.H. Onur, "Optimising Open Pit Design and
[H96] D. S. Hochbaum "A newold algorithm for minimum cut in closure graphs," [HC96] D. S. Hochbaum and A. Chen "Performance analysis and best [HC92] P. Huttagosol and R. Cameron, "A Computer Design of [JS71] T.B. Johnson and W.R. Sharp, "A ThreeDimensional Dynamic [Kob74] S. Koborov, "Method for Determining Optimal Open Pit [Koe82] E. Koenigsberg, "The Optimum Contours of an Open Pit Mine: [LG64] H. Lerchs, I.F. Grossmann, "Optimum Design of OpenPit [Pic76] J.C. Picard, "Maximal Closure of a Graph and Applications to [RP77] R.H. Robinson and N.B. Prenn, "An Open Pit Design Model," [ZK92] Y. Zhao and Y.C. Kim, "A New Optimum Pit Limit Design
Copyright 1997 Professor Dorit Hochbaum 