Lane's Algorithm Revisited

• 成果类型: Article
• 署名作者: Goycoolea, Marcos; Lamas, Patriclo; Pagnoncelli, Bernardo K.; Piazza, Adriana
• 署名单位: Universidad Adolfo Ibanez; Universidad de Chile
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2020.3685
• 发表日期: 2021
• 页码: 3087-3103
• 关键词: cutoff grade optimization; Lane's algorithm; large-scale open-pit mining; limiting economic cutoff grades

摘要

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 counter examples 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.