The Lerchs Grossman Algorithm from a Dual Simplex Viewpoint

In 1965 Helmut Lerchs and lngo 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 of ore and waste." They modeled 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 explain how a dual simplex algorithm can be used 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 how it can be simplified.