Hierarchical Benders Decomposition for Open-Pit Mine Block Sequencing

Thomas W. M. Vossen (), R. Kevin Wood () and Alexandra M. Newman ()
Additional contact information
Thomas W. M. Vossen: Leeds School of Business, University of Colorado at Boulder, Boulder, Colorado 80309
R. Kevin Wood: Operations Research Department, Naval Postgraduate School, Monterey, California 93943
Alexandra M. Newman: Department of Mechanical Engineering, Colorado School of Mines, Golden, Colorado 80401

Operations Research, 2016, vol. 64, issue 4, 771-793

Abstract: The open-pit mine block sequencing problem (OPBS) models a deposit of ore and surrounding material near the Earth’s surface as a three-dimensional grid of blocks. A solution in discretized time identifies a profit-maximizing extraction (mining) schedule for the blocks. Our model variant, a mixed-integer program (MIP), presumes a predetermined destination for each extracted block, namely, processing plant or waste dump. The MIP incorporates standard constructs but also adds not-so-standard lower bounds on resource consumption in each time period and allows fractional block extraction in a novel fashion while still enforcing pit-wall slope restrictions. A new extension of nested Benders decomposition, “hierarchical” Benders decomposition (HBD), solves the MIP’s linear-programming relaxation. HBD exploits time-aggregated variables and can recursively decompose a model into a master problem and two subproblems rather than the usual single subproblem. A specialized branch-and-bound heuristic then produces high-quality, mixed-integer solutions. Medium-sized problems (e.g., 25,000 blocks and 20 time periods) solve to near optimality in minutes. To the best of our knowledge, these computational results are the best known for instances of OPBS that enforce lower bounds on resource consumption.

Keywords: industries; mining; production scheduling; deterministic; sequencing; integer programming; Benders decomposition; heuristic (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1516 (application/pdf)

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:inm:oropre:v:64:y:2016:i:4:p:771-793

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().