Performance analysis and best implementations of old and new algorithms for the open-pit mining problem

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.