TY - JOUR
T1 - Lane's algorithm revisited
AU - Goycoolea, Marcos
AU - Lamas, Patricio
AU - Pagnoncelli, Bernardo K.
AU - Piazza, Adriana
N1 - Publisher Copyright:
© 2020 INFORMS.
PY - 2021/5
Y1 - 2021/5
N2 - In 1964, Kenneth Lane proposed an algorithm to optimize the production schedule of a single-metal, single-processor open pit mine. For this, he proposed a policy based on varying, over time, the so-called "cutoff grade"- or grade threshold used to determine if extracted material should be ore (processed material) or waste (thrown away). Lane's algorithm had a profound impact on the mining industry. However, though it has been used in multiple commercial software systems and has traditionally been taught to every aspiring mining engineer, it is widely considered a heuristic, and little is known regarding the quality of the solutions it produces. In this paper, we formally study Lane's problem. We show that Lane's algorithm can be viewed as an approximate dynamic programming scheme and that Lane's optimality conditions can be formally derived in two different ways: by considering a variant of the problem where the future value function is linearly approximated or by deriving the optimality conditions of a continuous-time version of the problem. We further show that Lane's algorithm can naturally be extended to this continuous-time version of the problem and that when this algorithm converges, it converges to an optimal solution. Finally, through a reformulation, we show that Lane's original problem can be solved using convex mixed-integer programming. Though hypothetical counterexamples can be constructed, computational experiments prove that Lane's algorithm can produce the optimal solution in every real-world data set tested, thereby lending solid support for its practical application.
AB - In 1964, Kenneth Lane proposed an algorithm to optimize the production schedule of a single-metal, single-processor open pit mine. For this, he proposed a policy based on varying, over time, the so-called "cutoff grade"- or grade threshold used to determine if extracted material should be ore (processed material) or waste (thrown away). Lane's algorithm had a profound impact on the mining industry. However, though it has been used in multiple commercial software systems and has traditionally been taught to every aspiring mining engineer, it is widely considered a heuristic, and little is known regarding the quality of the solutions it produces. In this paper, we formally study Lane's problem. We show that Lane's algorithm can be viewed as an approximate dynamic programming scheme and that Lane's optimality conditions can be formally derived in two different ways: by considering a variant of the problem where the future value function is linearly approximated or by deriving the optimality conditions of a continuous-time version of the problem. We further show that Lane's algorithm can naturally be extended to this continuous-time version of the problem and that when this algorithm converges, it converges to an optimal solution. Finally, through a reformulation, we show that Lane's original problem can be solved using convex mixed-integer programming. Though hypothetical counterexamples can be constructed, computational experiments prove that Lane's algorithm can produce the optimal solution in every real-world data set tested, thereby lending solid support for its practical application.
KW - Cutoff grade optimization
KW - Lane's algorithm
KW - Large-scale open-pit mining
KW - Limiting economic cutoff grades
UR - http://www.scopus.com/inward/record.url?scp=85103285167&partnerID=8YFLogxK
U2 - 10.1287/mnsc.2020.3685
DO - 10.1287/mnsc.2020.3685
M3 - Article
AN - SCOPUS:85103285167
SN - 0025-1909
VL - 67
SP - 3087
EP - 3103
JO - Management Science
JF - Management Science
IS - 5
ER -