Tailored Lagrangian Relaxation for the open pit block sequencing problem

A common strategic and tactical decision in open pit mining is to determine the sequence of extraction for notional three-dimensional production blocks so as to maximize the net present value of the extracted orebody while adhering to precedence and resource constraints. This problem is commonly formulated as an integer program with a binary variable representing if and when a block is extracted. In practical applications, the number of blocks can be large and the time horizon can be long, and therefore, instances of this NP-hard precedence-constrained knapsack problem can be difficult to solve using an exact approach. The problem is even more challenging to solve when it includes explicit minimum resource constraints. We employ three methodologies to reduce solution times: (i) we eliminate variables which must assume a value of 0 in the optimal solution; (ii) we use heuristics to generate an initial integer feasible solution for use by the branch-and-bound algorithm; and (iii) we employ Lagrangian relaxation, using information obtained while generating the initial solution to select a dualization scheme for the resource constraints. The combination of these techniques allows us to determine near-optimal solutions more quickly than solving the monolith, i.e., the original problem. We demonstrate our techniques to solve instances containing 25,000 blocks and 10 time periods, and 10,000 blocks and 15 time periods, to near-optimality. Copyright Springer Science+Business Media New York 2014