Hierarchical Benders decomposition for open-pit mine block sequencing

Loading...
Thumbnail Image
Authors
Vossen, Thomas W.M.
Wood, R. Kevin
Newman, Alexandra M.
Subjects
Industries
Mining
Production scheduling
Deterministic
Sequencing
Integer programming
Benders decomposition
Heuristic
Advisors
Date of Issue
2016
Date
Publisher
Informs
Language
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.
Type
Article
Description
The article of record as published may be found at http://dx.doi.org/10.1287/opre.2016.1516
Series/Report No
Department
Operations Research (OR)
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
23 p.
Citation
T.W.M. Vossen, R.K. Wood, A.M. Newman, "Hierarchical Benders decomposition for open-pit mine block sequencing," Operations research, v.64, no.4 (July-August 2016), pp. 771-793.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections