Tailored Lagrangian Relaxation for the open pit block sequencing problem

W. Lambert () and A. Newman ()

Annals of Operations Research, 2014, vol. 222, issue 1, 419-438

Abstract: 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

Keywords: Mining; Production scheduling; Integer programming (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-012-1287-y (text/html)
Access to full text is restricted to subscribers.

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:spr:annopr:v:222:y:2014:i:1:p:419-438:10.1007/s10479-012-1287-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-012-1287-y

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().