Skip to main content
SpringerLink
Log in

Implementing a parametric maximum flow algorithm for optimal open pit mine design under uncertain supply and demand

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

Conventional open pit mine optimization models for designing mining phases and ultimate pit limit do not consider expected variations and uncertainty in metal content available in a mineral deposit (supply) and commodity prices (market demand). Unlike the conventional approach, a stochastic framework relies on multiple realizations of the input data so as to account for uncertainty in metal content and financial parameters, reflecting potential supply and demand. This paper presents a new method that jointly considers uncertainty in metal content and commodity prices, and incorporates time-dependent discounted values of mining blocks when designing optimal production phases and ultimate pit limit, while honouring production capacity constraints. The structure of a graph representing the stochastic framework is proposed, and it is solved with a parametric maximum flow algorithm. Lagragnian relaxation and the subgradient method are integrated in the proposed approach to facilitate producing practical designs. An application at a copper deposit in Canada demonstrates the practical aspects of the approach and quality of solutions over conventional methods, as well as the effectiveness of the proposed stochastic approach in solving mine planning and design problems.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8

Similar content being viewed by others

References

  • Ahuja RK and Orlin JB (1989). A fast and simple algorithm for the maximum flow problem. Operations Research 37 (5): 748–759.

    Article  Google Scholar 

  • Akaike A and Dagdelen K (1999). A strategic production scheduling method for an open pit mine. Proceedings of the 28th International Symposium on Application of Computers and Operations Research in the Mineral Industry, Colorado School of Mines: Golden, Colorado, pp 729–738.

  • Asad MWA (2007). Optimum cutoff grade policy for open pit mining operations through net present value algorithm considering metal price and cost escalation. Engineering Computations 24 (7): 723–736.

    Article  Google Scholar 

  • Bascetin A and Nieto A (2007). Determination of optimal cut-off grade policy to optimize NPV using a new approach with optimization factor. Journal of the South African Institute of Mining and Metallurgy 107 (2): 87–94.

    Google Scholar 

  • Boucher A (2009). Sub-pixel mapping of coarse satellite remote sensing images with stochastic simulations from training images. Mathematical Geosciences 41 (3): 265–290.

    Article  Google Scholar 

  • Bower U, Geis A and Winkler A (2007). Commodity price fluctuations and their impact on monetary and fiscal policies in Western and Central Africa. European Central Bank, Occasional Paper Series, No. 60.

  • Caccetta L and Hill S (2003). An application of branch and cut to open pit mine scheduling. Journal of Global Optimization 27 (2–3): 349–365.

    Article  Google Scholar 

  • Chandran BG and Hochbaum DS (2009). A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem. Operations Research 57 (2): 358–376.

    Article  Google Scholar 

  • Chen MH (2010). Understanding world metals prices—Returns, volatility and diversification. Resources Policy 35 (3): 127–140.

    Article  Google Scholar 

  • Coleou T (1989). Technical parameterization of reserves for open pit design and mine planning. Proceedings of the 21st International Symposium on Application of Computers and Operations Research in the Mineral Industry, Las Vegas, Nevada, pp 485–494.

  • Denby B, Schofield D and Surme T (1998). Genetic algorithms for flexible scheduling of open pit operations. Proceedings of the 27thSymposium on Application of Computers and Operations Research in the Mineral Industry, Royal School of Mines: London, UK, pp 605–616.

  • Dimitrakopoulos R (2011). Stochastic optimization for strategic mine planning: A decade of developments. Journal of Mining Science 47 (2): 138–150.

    Article  Google Scholar 

  • Dimitrakopoulos R and Abdel Sabour SA (2007). Evaluating mine plans under uncertainty: Can the real options make a difference? Resources Policy 32 (3): 116–125.

    Article  Google Scholar 

  • Dowd PA (1994). Risk assessment in reserve estimation and open-pit planning. Transactions of the Institute of Mining and Metallurgy 103: 148–154.

    Google Scholar 

  • Faaland B, Kim K and Schmitt T (1990). A new algorithm for computing the maximal closure of a graph. Management Science 36 (3): 315–331.

    Article  Google Scholar 

  • Francois-Bongarcon D and Guibal D (1984). Parameterization of optimal designs of an open pit—Beginning of a new phase of research. Transactions of Society of Mining Engineers of AIME 274: 1801–1805.

    Google Scholar 

  • Gallo G, Grigoriadis MD and Tarjan RE (1989). A fast parametric maximum flow algorithm and applications. SIAM Journal of Computing 18 (1): 30–55.

    Article  Google Scholar 

  • Godoy M and Dimitrakopoulos R (2011). A risk quantification framework for strategic mine planning: Method and application. Journal of Mining Science 47 (2): 235–246.

    Article  Google Scholar 

  • Goldberg AV and Tarjan RE (1988). A new approach to the maximum flow problem. Journal of the Association for Computing Machinery 35 (4): 921–940.

    Article  Google Scholar 

  • Hochbaum DS (2001). A new-old algorithm for minimum-cut and maximum-flow in closure graphs. Networks 37 (4): 171–193.

    Article  Google Scholar 

  • Hochbaum DS (2003). Efficient algorithms for the inverse spanning tree problem. Operations Research 51 (5): 785–797.

    Article  Google Scholar 

  • Hochbaum DS (2004). Selection, provisioning, shared fixed costs, maximum closure, and implications on algorithmic methods today. Management Science 50 (6): 709–723.

    Article  Google Scholar 

  • Hochbaum DS (2008). The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Operations Research 56 (4): 992–1009.

    Article  Google Scholar 

  • Hochbaum DS and Chen A (2000). Performance analysis and best implementations of old and new algorithms for the open-pit mining problem. Operations Research 48 (6): 894–914.

    Article  Google Scholar 

  • Horta A and Amilcar S (2010). Direct sequential co-simulation with joint probability distributions. Mathematical Geosciences 42 (3): 269–292.

    Article  Google Scholar 

  • Hustrulid W and Kuchta M (2006). Open Pit Mine Planning and Design. 2nd edn. Taylor and Francis/Balkema: The Netherlands.

    Google Scholar 

  • Johnson TB (1968). Optimum open pit mine production scheduling. PhD Thesis, Department of IEOR, University of California, Berkeley, CA.

  • King B (2011). Optimal mining practice in strategic planning. Journal of Mining Science 47 (2): 247–253.

    Article  Google Scholar 

  • Lane K (1964). Choosing the optimum cutoff grade. Colorado School of Mines Quarterly 59 (4): 811–829.

    Google Scholar 

  • Lane K (1988). The Economic Definition of Ore, Cutoff Grade in Theory and Practice. Mining Journal Books: London.

    Google Scholar 

  • Leite A (2008). Stochastic optimization approaches to open pit mine planning: Applications for and the value of stochastic approaches. MEng Thesis, Mining and Materials Engineering, McGill University, Canada.

  • Lerchs H and Grossmann IF (1965). Optimum design of open pit mines. Transactions CIM 58: 17–24.

    Google Scholar 

  • Meagher C, Abdel Sabour SA and Dimitrakopoulos R (2009). Pushback design of open pit mines under geological and market uncertainties. Proceedings of the International Symposium on Orebody Modeling and Strategic Mine Planning: Old and New Dimensions in Changing World, pp 297–304.

  • Picard JC (1976). Maximal closure of a graph and applications to combinatorial problems. Management Science 22 (11): 1268–1272.

    Article  Google Scholar 

  • Ramazan S (2007). The new fundamental tree algorithm for production scheduling of open pit mines. European Journal of Operational Research 177 (2): 1153–1166.

    Article  Google Scholar 

  • Ramazan S and Dimitrakopoulos R (2012). Production scheduling with uncertain supply: A new solution to the open pit mining problem. Optimization and Engineering, DOI: 10.1007/s11081-012-9186-2.

  • Schwartz ES (1997). The stochastic behavior of commodity prices—Implications for valuation and hedging. Journal of Finance 52 (3): 923–973.

    Article  Google Scholar 

  • Tachefine B and Soumis F (1997). Maximal closure on a graph with resource constraints. Computers and Operations Research 24 (10): 981–990.

    Article  Google Scholar 

  • Wang Q and Sevim H (1993). An alternative to parameterization in finding a series of maximum-metal pits for production planning. Proceedings of the 24thInternational Symposium on Application of Computers and Operations Research in the Mineral Industry, Canadian Institute of Mining and Metallurgy and Ecole Polytechnique, Montreal: Quebec, Canada, pp 168–175.

  • Whittle J (1988). Beyond optimization in open pit design. Proceedings of the Canadian Conference on Computer Applications in the Mineral Industries, Quebec: Canada (Balkema, Rotterdam), pp 331–337.

  • Whittle J (1999). A decade of open pit mine planning and optimization—The craft of turning algorithms into packages. Proceedings of the 28thInternational Symposium on Application of Computers and Operations Research in the Mineral Industry, Colorado School of Mines: Golden, Colorado, pp 15–24.

Download references

Acknowledgements

The work in this paper was funded from NSERC CDR Grant 335696 and BHP Billiton, NSERC Discovery grant 239019, and the members of the COSMO Stochastic Mine Planning Laboratory: AngloGold Ashanti, Barrick, BHP Billiton, De Beers, Newmont, and Vale. Thanks are in order to Brian Baird, Peter Stone, Darren Dyck, and Gavin Yates of BHP Billiton for their support, collaboration, and technical comments.

Author information

Authors and Affiliations

  1. COSMO Stochastic Mine Planning Laboratory, McGill University, Canada

    M W A Asad & R Dimitrakopoulos

Authors
  1. M W A Asad
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R Dimitrakopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M W A Asad.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Asad, M., Dimitrakopoulos, R. Implementing a parametric maximum flow algorithm for optimal open pit mine design under uncertain supply and demand. J Oper Res Soc 64, 185–197 (2013). https://doi.org/10.1057/jors.2012.26

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2012.26

Keywords

Search

Navigation