Applications of integer programming in open pit mining

© 2006 Dr. Christopher FrickeThis thesis considers the application of integer programming techniques to solve the open pit mine production scheduling problem. The objective of this research is to extend the current state-of-the-art, to reduce the computational requirements for determining optimal integer solutions, and to allow larger problem instances to be solved. This will afford mine planning practitioners increased flexibility when designing long-term mine plans, since a greater range of scenario analysis will be able to be undertaken in a short period of time. This in turn will lead to the development of schedules that are more robust to the inherent geological uncertainty present in any mine planning problem, and hence reduce the variability of realised mining production. Since the formulations considered are the most general structures possible for this application, the results presented are also applicable to, and beneficial for, related, more complex optimisation problems in mining, such as blending and stochastic mine planning problems. We derive a relationship between the state-of-the-art binary integer programming formulation for the open pit mine production scheduling problem, and a simpler integer programming structure called the precedence constrained knapsack problem. We present a new approach for determining facets of the precedence constrained knapsack polyhedron based on clique inequalities. It is shown that the clique-based approach can generate facets that cannot be found through existing techniques, which consider the lifting of knapsack cover inequalities for the precedence constrained knapsack polyhedron. In addition, we introduce a new problem, named the continuous precedence constrained knapsack problem. Investigation of this problem is motivated by the derivation of a relationship with the state-of-the-art mixed integer programming formulation for the open pit mine production scheduling problem. Valid inequalities for the continuous precedence constrained knapsack polyhedron are derived by adapting both existing and new approaches for the precedence constrained knapsack problem. The new valid inequalities derived for the precedence constrained knapsack and continuous precedence constrained knapsack problems are used to strengthen the binary and mixed integer programming formulations of the open pit mine production scheduling problem respectively. Testing of these enhanced formulations on data sets provided by our research partner demonstrates that the time and memory requirements to determine the optimal integer solutions are reduced, in many cases by a significant margin. It is also shown that these formulations are able to solve larger problem instances to optimality than was previously possible. We also develop a suite of new heuristics to quickly find good feasible integer solutions to the open pit mine production scheduling problem. The methodologies used are based upon the adaptation of existing solution approaches for the ultimate pit problem, a simpler optimisation problem in open pit mining, as well as the use of other integer programming techniques including Dantzig-Wolfe decomposition and column generation