Performance analysis and best implementations of old and new algorithms for the Open - Pit Mining Problem
Abstract
The open-pit mining problem is to determine the contours of a mine,
based on economic data and engineering feasibility requirements
in order 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) [LG64]. 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 [GT88]. 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 as compared to existing
algorithms and make the related sensitivity analysis problem
practically solvable.
Download Information
Click on the following title to view and download the paper in PostScript format.
- Performance analysis and best implementations of old and new algorithms for the Open - Pit Mining Problem (40 pages, 584 KB)
,
- Dorit S. Hochbaum and Anna Chen. To appear in Operations Research .
dorit@hochbaum.ieor.berkeley.edu
7/30/98