Performance Analysis and Best Implementations of Old and New Algorithms for the Open-Pit Mining Problem

Dorit S. Hochbaum () and Anna Chen
Additional contact information
Dorit S. Hochbaum: Department of IE&OR and Haas School of Business, University of California, Berkeley, California 94720
Anna Chen: Department of IE&OR, University of California, Berkeley, California 94720

Operations Research, 2000, vol. 48, issue 6, 894-914

Abstract: The open-pit mining problem is to determine the contours of a mine, based on economic data and engineering feasibility requirements, to yield maximum possible net income. This practical problem needs to be solved for very large data sets. In practice, moreover, it is necessary to test multiple scenarios, taking into account a variety of realizations of geological predictions and forecasts of ore value.The industry is experiencing computational difficulties in solving the problem. Yet, the problem is known to be equivalent to the minimum cut or maximum flow problem. For the maximum flow problem there are a number of very efficient algorithms that have been developed over the last decade. On the other hand, the algorithm that is most commonly used by the mining industry has been devised by Lerchs and Grossmann (LG). This algorithm is used in most commercial software packages for open-pit mining.This paper describes a detailed study of the LG algorithm as compared to the maximum flow “push-relabel” algorithm. We propose here an efficient implementation of the push-relabel algorithm adapted to the features of the open-pit mining problem. We study issues such as the properties of the mine and ore distribution and how they affect the running time of the algorithm. We also study some features that improve the performance of the LG algorithm. The proposed implementations offer significant improvements compared to existing algorithms and make the related sensitivity analysis problem practically solvable.

Keywords: Industries/mining/metals: planning for mining operations; Networks/graphs; applications: application of minimum cut to mining; Networks/graphs; flow algorithms: implementing the preflow and another minimum cut algorithm (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (29)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.6.894.12392 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:48:y:2000:i:6:p:894-914

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().