A mathematical programming viewpoint for solving the ultimate pit problem

In 1965 Helmut Lerchs and Ingo Grossmann presented to the mining community an algorithm to find the optimum design for an open pit mine. In their words, ‘the objective is to design the contour of a pit so as to maximize the difference between total mine value of the ore extracted and the total extraction cost of ore and waste’. They modelled the problem in graph theoretic terms and showed that an optimal solution of the ultimate pit problem is equivalent to finding the maximum closure of their graph based model. In this paper, we develop a network flow algorithm based on the dual to solve the same problem. We show how this algorithm is closely related to Lerchs and Grossmann's and how the steps in their algorithm can be viewed in mathematical programming terms. This analysis adds insight to the algorithm of Lerchs and Grossmann and shows where it can be made more efficient. As in the case of Lerchs and Grossmann, our algorithm allows us to use very efficient data structures based on graphs that represent the data and constraints.