Skip to main content
Log in

A framework for adaptive open-pit mining planning under geological uncertainty

  • Research Article
  • Published:
Optimization and Engineering Aims and scope Submit manuscript

Abstract

Mine planning optimization aims at maximizing the profit obtained from extracting valuable ore. Beyond its theoretical complexity—the open-pit mining problem with capacity constraints reduces to a knapsack problem with precedence constraints, which is NP-hard—practical instances of the problem usually involve a large to very large number of decision variables, typically of the order of millions for large mines. Additionally, any comprehensive approach to mine planning ought to consider the underlying geostatistical uncertainty as only limited information obtained from drill hole samples of the mineral is initially available. In this regard, as blocks are extracted sequentially, information about the ore grades of blocks yet to be extracted changes based on the blocks that have already been mined. Thus, the problem lies in the class of multi-period large scale stochastic optimization problems with decision-dependent information uncertainty. Such problems are exceedingly hard to solve, so approximations are required. This paper presents an adaptive optimization scheme for multi-period production scheduling in open-pit mining under geological uncertainty that allows us to solve practical instances of the problem. Our approach is based on a rolling-horizon adaptive optimization framework that learns from new information that becomes available as blocks are mined. By considering the evolution of geostatistical uncertainty, the proposed optimization framework produces an operational policy that reduces the risk of the production schedule. Our numerical tests with mines of moderate sizes show that our rolling horizon adaptive policy gives consistently better results than a non-adaptive stochastic optimization formulation, for a range of realistic problem instances.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. This is reasonable for most deposits but not all. For example, diamond pipes have radial symmetry and are richer in the center and poorer on the outside. Similarly the impermeable dome on top of most oil reservoirs is curved so the depth to its surface cannot be treated as second order stationary because the mean depth varies.

  2. Following Stewart (1976), a function \(f:{\mathbb {R}}\mapsto {\mathbb {R}}\) is positive definite if f is even (i.e. \(f(x)=f(-x)\)) and, for any \(x_1,\ldots ,x_n \in {\mathbb {R}}\), the matrix \(A_{n\times n}\) defined as \(A_{ij}=f(x_i-x_j)\) is positive semidefinite. From a practical point of view, kriging (see Sect. 2.2) gives the minimum variance unbiased linear estimator, and if the spatial covariance function is not positive definite in the appropriate dimension space, negative kriging estimation variances can occur. See Armstrong and Jabin (1981) for some examples.

  3. Other simulation methods have been developed, e.g., sequential simulations, see Gómez-Hernández and Journel (1993), Caers (2000) and Soares (2001), and multi-point simulations, see Mustapha and Dimitrakopoulos (2010) and de Carvalho et al. (2019).

  4. Let \(\varPhi\) denote the cumulative standard normal distribution, and let Z(x) denote the grade. Let F be the cumulative distribution of the grades. Then we define the Gaussian equivalent as follows: \(f(z) = \varPhi ^{-1}(F(z))\) (which is well-defined because F is an increasing function by construction). Consequently \(P(f(Z)\le z) = P(Z\le F^{-1}\varPhi (z)) = \varPhi (z)\), so \(Y(x) \equiv f(Z(x))\) is normally distributed. This can be defined “graphically” from the experimental histogram, or it can be expressed in terms of Hermite polynomials. See pp. 380–381 Chiles and Delfiner (2009), notably Figure 6.1 for details.

  5. Economic value from processing might include discount factors, operational costs, commodity prices, mineral ore grades, etc. per cluster or block. For clarity of exposition we assume economic values are time-homogeneous up to a discount factor.

References

  • Alonso-Ayuso A, Carvallo F, Escudero LF, Guignard M, Pi J, Puranmalka R, Weintraub A (2014) Medium range optimization of copper extraction planning under uncertainty in future copper prices. Eur J Oper Res 233(3):711–726

    Article  Google Scholar 

  • Armstrong M, Jabin R (1981) Variogram models must be positive-definite. J Int Assoc Math Geol 13(5):455–459

    Article  Google Scholar 

  • Bassamboo A, Randhawa RS, Mieghem JAV (2012) A little flexibility is all you need: on the asymptotic value of flexible capacity in parallel queuing systems. Oper Res 60(6):1423–1435

    Article  MathSciNet  Google Scholar 

  • Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust optimization. Princeton University Press, Princeton

    Book  Google Scholar 

  • Boland N, Dumitrescu I, Froyland G (2008) A multistage stochastic programming approach to open pit mine production scheduling with uncertain geology. Optimization Online

  • Caers J (2000) Direct sequential indicator simulation. Geostats 1:39–48

    Google Scholar 

  • Chiles J-P, Delfiner P (2009) Geostatistics: modeling spatial uncertainty, vol 497. Wiley, New York

    MATH  Google Scholar 

  • Chod J, Rudi N, Van Mieghem JA (2010) Operational flexibility and financial hedging: complements or substitutes? Manag Sci 56(6):1030–1045

    Article  Google Scholar 

  • de Carvalho JP, Dimitrakopoulos R, Minniakhmetov I (2019) High-order block support spatial simulation method and its application at a gold deposit. Math Geosci 51(6):793–810

    Article  MathSciNet  Google Scholar 

  • De Lara M, Morales N, Beeker N (2017) Adaptive strategies for the open-pit mine optimal scheduling problem. https://arxiv.org/pdf/1706.08264.pdf

  • Del Castillo MF, Dimitrakopoulos R (2019) Dynamically optimizing the strategic plan of mining complexes under supply uncertainty. Resour Policy 60:83–93

    Article  Google Scholar 

  • Dimitrakopoulos R, Ramazan S (2004) Uncertainty based production scheduling in open pit mining. SME Trans 316:106–112

    Google Scholar 

  • Dowd PA, Dare-Bryan PC (2018) Planning, designing and optimising production using geostatistical simulation. In: Dimitrakopoulos R (eds) Advances in applied strategic mine planning. Springer, Cham. https://doi.org/10.1007/978-3-319-69320-0_26

    Chapter  Google Scholar 

  • Emery X, Lantuéjoul C (2006) Tbsim: a computer program for conditional simulation of three-dimensional gaussian random fields via the turning bands method. Comput Geosci 32(10):1615–1628

    Article  Google Scholar 

  • Escudero LF, Garín MA, Unzueta A (2017) Scenario cluster lagrangean decomposition for risk averse in multistage stochastic optimization. Comput Oper Res 85:154–171

    Article  MathSciNet  Google Scholar 

  • Escudero LF, Garín MA, Monge JF, Unzueta A (2020) Some matheuristic algorithms for multistage stochastic optimization models with endogenous uncertainty and risk management. Eur J Oper Res 285(3):988–1001

    Article  MathSciNet  Google Scholar 

  • Frazier PI (2018) Bayesian optimization. In: Recent advances in optimization and modeling of contemporary problems. INFORMS, pp 255–278

  • Gershon M (1987) Heuristic approaches for mine planning and production scheduling. Geotech Geol Eng 5(1):1–13

    Google Scholar 

  • Goel V, Grossmann IE (2006) A class of stochastic programs with decision dependent uncertainty. Math Program 108(2–3):355–394

    Article  MathSciNet  Google Scholar 

  • Gómez-Hernández JJ, Journel AG (1993) Joint sequential simulation of multigaussian fields. In: Geostatistics Troia’92. Springer, Berlin, pp 85–94

  • Goria S (2004) Evaluation d’un projet minier: approche bayésienne et options réelles. PhD thesis, Paris, ENMP

  • Hellemo L, Barton PI, Tomasgard A (2018) Decision-dependent probabilities in stochastic programs with recourse. CMS 15(3–4):369–395

    Article  MathSciNet  Google Scholar 

  • Homem-de-Mello T, Bayraksan G (2014) Monte Carlo sampling-based methods for stochastic optimization. Surv Oper Res Manag Sci 19:56–85

    MathSciNet  Google Scholar 

  • Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J Optim 12(2):479–502

    Article  MathSciNet  Google Scholar 

  • Klingman D, Phillips N (1988) Integer programming for optimal phosphate-mining strategies. J Oper Res Soc 39:805–810

    Article  Google Scholar 

  • Krige DG (1951) A statistical approach to some basic mine valuation problems on the witwatersrand. J South Afr Inst Min Metall 52(6):119–139

    Google Scholar 

  • Lagos G, Espinoza D, Moreno E, Amaya J (2011) Robust planning for an open-pit mining problem under ore-grade uncertainty. Electron Notes Discrete Math 37:15–20

    Article  MathSciNet  Google Scholar 

  • Lantuéjoul C (2013) Geostatistical simulation: models and algorithms. Springer, Berlin

    MATH  Google Scholar 

  • Leite A, Dimitrakopoulos R (2007) Stochastic optimisation model for open pit mine planning: application and risk analysis at copper deposit. Min Technol 116(3):109–118

    Article  Google Scholar 

  • Lerchs H, Grossmann IF (1965) Optimum design of open pit mines. Trans Can Inst Min Metall 68:17–24

    Google Scholar 

  • Lund PD, Lindgren J, Mikkola J, Salpakari J (2015) Review of energy system flexibility measures to enable high levels of variable renewable electricity. Renew Sustain Energy Rev 45:785–807

    Article  Google Scholar 

  • Matheron G (1973) The intrinsic random functions and their applications. Adv Appl Probab 5(3):439–468

    Article  MathSciNet  Google Scholar 

  • Menabde M, Froyland G, Stone P, Yeates GA (2018) Mining schedule optimisation for conditionally simulated orebodies. In: Dimitrakopoulos R (eds) Advances in applied strategic mine planning. Springer, Cham. https://doi.org/10.1007/978-3-319-69320-0_8

    Chapter  Google Scholar 

  • Moreno E, Emery X, Goycoolea M, Morales N, Nelis G (2017) A two-stage stochastic model for open pit mine planning under geological uncertainty. In: Proceedings of the APCOM

  • Muñoz G, Espinoza D, Goycoolea M, Moreno E, Queyranne M, Letelier OR (2018) A study of the Bienstock–Zuckerberg algorithm: applications in mining and resource constrained project scheduling. Comput Optim Appl 69(2):501–534

    Article  MathSciNet  Google Scholar 

  • Mustapha H, Dimitrakopoulos R (2010) High-order stochastic simulation of complex spatially distributed natural phenomena. Math Geosci 42(5):457–485

    Article  MathSciNet  Google Scholar 

  • Newman AM, Rubio E, Caro R, Weintraub A, Eurek K (2010) A review of operations research in mine planning. Interfaces 40(3):222–245

    Article  Google Scholar 

  • Nicholas G, Coward S, Armstrong M, Galli A (2006) Integrated mine evaluation–implications for mine management. In: Proceedings international mine management conference. Citeseer, pp 69–79

  • Oliver DS, Chen Y (2011) Recent progress on reservoir history matching: a review. Comput Geosci 15(1):185–221

    Article  Google Scholar 

  • Oliver DS, Reynolds AC, Liu N (2008) Inverse theory for petroleum reservoir characterization and history matching. Cambridge University Press, Cambridge

    Book  Google Scholar 

  • Powell WB, Ryzhov IO (2012) Optimal learning, vol 841. Wiley, New York

    Book  Google Scholar 

  • Ramazan S, Dimitrakopoulos R (2013) Production scheduling with uncertain supply: a new solution to the open pit mining problem. Optim Eng 14(2):361–380

    Article  Google Scholar 

  • Ravenscroft P (1992) Risk analysis for mine scheduling by conditional simulation. Transactions of the Institution of Mining and Metallurgy. Section A. Mining Industry 101

  • Rimélé A, Dimitrakopoulos R, Gamache M (2020) A dynamic stochastic programming approach for open-pit mine planning with geological and commodity price uncertainty. Resour Policy 65:101570

    Article  Google Scholar 

  • Rivera O, Espinoza D, Goycoolea M, Moreno E, Munoz G (2019) Production scheduling for strategic open pit mine planning: a mixed integer programming approach. Oper Res. https://doi.org/10.1287/opre.2019.1965

    Article  MATH  Google Scholar 

  • Shapiro A (2006) On complexity of multistage stochastic programs. Oper Res Lett 34:1–8

    Article  MathSciNet  Google Scholar 

  • Shapiro A, Dentcheva D, Ruszczyński A (2009) Lectures on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia

    Book  Google Scholar 

  • Smith C (1978) The use of mixed integer programming in planning the depletion of an alluvial diamond deposit. Operations Research Society of South Africa, September 28–29

  • Soares A (2001) Direct sequential simulation and cosimulation. Math Geol 33(8):911–926

    Article  Google Scholar 

  • Stewart J (1976) Positive definite functions and generalizations, an historical survey. Rocky Mt J Math 6(3):409–434

    Article  MathSciNet  Google Scholar 

  • Zou J, Ahmed S, Sun XA (2019) Stochastic dual dynamic integer programming. Math Program 175(1):461–502

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors thank Xavier Emery (University of Chile) and Eduardo Moreno (Universidad Adolfo Ibañez) for their invaluable help regarding the geostatistics simulations and the optimization models, respectively. They also thank two anonymous referees for their comments. This research was partially supported by the supercomputing infrastructure of the NLHPC (ECM-02).

Funding

This research has been supported by grant Programa de Investigación Asociativa (PIA) ACT1407, Chile. Guido Lagos also acknowledges the financial support of FONDECYT Grant 3180767, Chile. Tito Homem-de-Mello and Tomás Lagos acknowledge the support of FONDECYT Grant 1171145, Chile. Denis Saure acknowledges the support of FONDECYT Grant 1181513.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Tito Homem-de-Mello.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix: Benders’ algorithm

Appendix: Benders’ algorithm

First we present the formulation to which we apply the Benders’ decomposition approach. We consider the following model:

$$\begin{aligned} \max&\quad -w^{\intercal } \theta + \frac{1}{S} \sum _{s=1}^S D(\theta ,s) \end{aligned}$$
(9)
$$\begin{aligned} \text {s.t. }&\quad \sum _{t \in T} \theta _{i,t} \le 1 \quad \forall \ i \le m \end{aligned}$$
(10)
$$\begin{aligned}&\quad \theta _{i,t} \le \sum _{s \le t} \theta _{j,s} \quad \forall \ (i,j) \in P, \quad t \in T \end{aligned}$$
(11)
$$\begin{aligned}&\quad \sum _{i \le m} \theta _{i,t} \, k_i^{ex} \le K^{ex} \quad \forall \ t \in T \end{aligned}$$
(12)
$$\begin{aligned}&\quad \theta _{i,t} \in \{0,1\} \quad \forall \ i \le m, \quad t \in T, \end{aligned}$$
(13)

where \(D(\theta ,s)\) is a sub-problem optimal value. If \(D(\theta ,s)\) has a solution, it is a function of \(\theta\) and the scenario s. Moreover let the function Q return the value for processing extraction \(\theta\) under scenario s, i.e. the formulation for the sub-problem of \(Q(\theta ,s)\) is the following:

$$\begin{aligned} \max&\quad \sum _{t \in T} \sum _{b \in B} \rho ^t v_{b}^s \, y_{b,t} \end{aligned}$$
(14)
$$\begin{aligned} \text {s.t. }&\quad y_{b,t} \le \theta _{i,t} \quad \forall \ b \in B_i, \quad i \le m, \quad t \in T \end{aligned}$$
(15)
$$\begin{aligned}&\quad \sum _{b \le n} y_{b,t} \,k_b^{pr} \le K^{pr} \quad \forall \ t \in T \end{aligned}$$
(16)
$$\begin{aligned}&\quad 0 \le y_{b,t} \le 1 \quad \forall \ b\le n, \quad t \in T. \end{aligned}$$
(17)

Note that restriction (15) above can be replaced by \(y_{b,t} \le 1\) for all \(b \in B_i\) such that \(\theta _{i,t}\) are non-zero variables, and remove all variables \(y_{bt}\) such that \(\theta _{i,t}=0\) and \(b\in B_i\). Clearly \(Q(\theta ,s)\) is a continuous Knapsack problem, and it can be solved in \(O(S|B|\log {}|B|)\), by sorting the block price/weight ratio values and setting the degree of the cut when either the capacity is met or the prices are negative. In order to proceed with the decomposition approach, one must incorporate the dual of problem (14)–(17) into the master problem (9)–(13). The dual, \(D(\theta ,s),\) of \(Q(\theta ,s)\) is given by

$$\begin{aligned} \min&\quad \sum _{t \in T,\ s=1,\ldots ,S} (K^{pr} \mu _t + \sum _{i \le m,\, b \in B_i} \theta _{i,t} \lambda _{b,t} ) \end{aligned}$$
(18)
$$\begin{aligned} \text {s.t. }&\quad \lambda _{b,t} + \mu _t k_b^{pr} \ge \rho ^t v_{b}^{s} \quad \forall i \le m, \;b \in B_i, \;t \in T,\; s = 1, \ldots ,S \end{aligned}$$
(19)
$$\begin{aligned}&\mu _t \ge 0 \quad \forall t \in T, \; s =1, \ldots ,S. \end{aligned}$$
(20)

Since \(D(\theta ,s)\) is a minimization problem that gives an upper bound to \(Q(\theta , s)\), one can solve the original problem (9)–(13) with the (equivalent) formulation:

$$\begin{aligned} \max&\quad -w^{\intercal } \theta + \frac{1}{S} \sum _{s=1}^S z_s \end{aligned}$$
(21)
$$\begin{aligned} \text {s.t. }&\quad \sum _{t \in T} \theta _{i,t} \le 1 \quad \forall \ i \le m \end{aligned}$$
(22)
$$\begin{aligned}&\quad \theta _{i,t} \le \sum _{s \le t} \theta _{j,s} \quad \forall \ (i,j) \in P, \quad t \in T \end{aligned}$$
(23)
$$\begin{aligned}&\quad \sum _{i \le m} \theta _{i,t} \, k_i^{ex} \le K^{ex} \quad \forall \ t \in T \end{aligned}$$
(24)
$$\begin{aligned}&\quad z_s \le D(\theta ,s) \quad \forall s =1, \ldots ,S \end{aligned}$$
(25)
$$\begin{aligned}&\quad \theta _{i,t} \in \{0,1\} \quad \forall i \le m,\; t \in T. \end{aligned}$$
(26)

Note that the above formulation does not include restrictions of the type \(0 \le D(\theta ,s)\), because the dual formulation is naturally non-negative. To establish this fact, note that \(y^s=0\) is always a feasible solution of primal problem \(Q(\theta ,s)\), thus by weak duality we get the desired result.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lagos, T., Armstrong, M., Homem-de-Mello, T. et al. A framework for adaptive open-pit mining planning under geological uncertainty. Optim Eng 23, 111–146 (2022). https://doi.org/10.1007/s11081-020-09557-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11081-020-09557-0

Keywords

Navigation