Skip to main content
SpringerLink
Log in

An Application of Branch and Cut to Open Pit Mine Scheduling

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

The economic viability of the modern day mine is highly dependent upon careful planning and management. Declining trends in average ore grades, increasing mining costs and environmental considerations will ensure that this situation will remain in the foreseeable future. The operation and management of a large open pit mine having a life of several years is an enormous and complex task. Though a number of optimization techniques have been successfully applied to resolve some important problems, the problem of determining an optimal production schedule over the life of the deposit is still very much unresolved. In this paper we will critically examine the techniques that are being used in the mining industry for production scheduling indicating their limitations. In addition, we present a mixed integer linear programming model for the scheduling problems along with a Branch and Cut solution strategy. Computational results for practical sized problems are discussed.

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

Similar content being viewed by others

References

  1. Achuthan, N.R., Caccetta, L. and Hill, S.P. (1995), A New Subtour Elimination Constraint for the Vehicle Routing Problem, European Journal of Operations Research 91, 573-586.

    Google Scholar 

  2. Achuthan, N.R., Caccetta, L. and Hill, S.P. (1998), Capacitated Vehicle Routing Problem: Some New Cutting Planes, Asian-Pacific Journal of Operational Research 15, 109-123.

    Google Scholar 

  3. Applegate, R., Bixby, R., Chvatal, V. and Cook, W. (1995), Finding Cuts in the TSP (A Preliminary Report), DIMACS Technical Report, pp. 95-105.

  4. Augerat, P., Belengeur, J.M., Benavent, E., Corberan, A., Naddef, N. and Rinaldi, G. (1995) Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem, Research Report 949-M, Universite Joseph Fourier, Grenoble, France,.

    Google Scholar 

  5. Autoscheduler, Runge Mining Pty Ltd. (Australia). Web: http//www.runge.com/xpac.

  6. Francois-Bongarcon, D.M. and Guibal, D. (1984), Parametization of Optimal Designs of an Open Pit Beginning of a New Phase of Research, Trans. SME, AIME 274, 1801-1805.

    Google Scholar 

  7. Caccetta, L. and Giannini, L.M. (1986), Optimization Techniques for the Open Pit Limit Problem, Proc. Australas. Inst. Min. Metall. 291, 57-63.

    Google Scholar 

  8. Caccetta, L. and Giannini, L.M. (1988), An Application of Discrete Mathematics in the Design of an Open Pit Mine, Discrete Applied Mathematics 21, 1-19.

    Google Scholar 

  9. Caccetta, L. and Giannini, L.M. (1990), Application of Operations Research Techniques in Open Pit Mining, in Byong-Hun Ahn (Ed.), Asian-Pacific Operations Research: APORS’88, Elsevier Science Publishers BV, pp. 707-724.

  10. Caccetta, L., Giannini, L.M. and Kelsey, P. (1994), On the Implementation of Exact Optimization Techniques for Open Pit Design, Asia-Pacific Journal of Operations Research 11, 155-170.

    Google Scholar 

  11. Caccetta, L., Giannini, L.M. and Kelsey, P. (1998), Application of Optimization Techniques in Open Pit Mining, Proceedings of the Fourth International Conference on Optimization Techniques and Applications (ICOTA’98) (L. Caccetta et al. Editors.), Vol. 1, pp. 414-422. (Curtin University of Technology: Perth, Australia).

    Google Scholar 

  12. Caccetta, L. and Hill, S.P. (2001), Branch and Cut Methods for Network Optimization, Mathematical and Computer Modelling 33, 517-532.

    Google Scholar 

  13. Caccetta, L. and Hill, S.P. (2001), A Branch and Cut Method for the Degree Constrained Minimum Spanning Tree Problem, Networks 37, 74-83.

    Google Scholar 

  14. Caccetta, L., Kelsey, P. and Giannini, L.M. (1998), Open Pit Mine Production Scheduling, in A.J. Basu, N. Stockton and D. Spottiswood (Eds.), Computer Applications in the Minerals Industries International Symposium (3rd Regional APCOM), Austral. Inst. Min. Metall. Publication Series 5, 65-72.

  15. Coléou, T. (1988), Technical Parameterization for Open Pit Design and Mine Planning, in: Proc. 21st APCOM Symposium of the Society of Mining Engineers (AIME) pp. 485-494.

  16. CPLEX 6.0 User Manual, ILOG Inc., CPLEX Division, 889 Alder Avenue, Suite 200, Incline Village, NV 89451, U.S.A.

  17. Dagdelen, K. and Johnson, T.B. (1986), Optimum Open Pit Mine Production Scheduling by Lagrangian Parameterization, in: Proc. 19th APCOM Symposium of the Society of Mining Engineers (AIME) pp. 127-142.

  18. Denby, B. and Schofield, D. (1995), The Use of Genetic Algorithms in Underground Mine Scheduling, in: Proc. 25th APCOM Symposium of the Society of Mining Engineers (AIME, New York), pp. 389-394.

    Google Scholar 

  19. Denby, B., Schofield, D. and Bradford, S. (1991), Neural Network Applications in Mining Engineering, Department of Mineral Resources Engineering Magazine, University of Nottingham, pp. 13-23.

  20. Earthworks, NPV Scheduler, Web: http://www.earthworks.com.au.

  21. Gershon, M. (1982), A Linear Programming Approach to Mine Scheduling Optimization, in: Proc. 17th APCOM Symposium of the Society of Mining Engineers (AIME), pp. 483-493.

  22. Gershon, M. (1983), Mine Scheduling Optimization with Mixed Integer Programming, Mining Engineering 35, 351-354.

    Google Scholar 

  23. Gershon, M. (1987), Heuristic Approaches for Mine Planning and Production Scheduling, Int. Journal of Mining and Geological Engineering 5, 1-13.

    Google Scholar 

  24. Gignac, L. (1975), Computerized Ore Evaluation and Open Pit Design, in: Proc. 36th Annual Mining Symposium of the Society of Mining Engineers (AIME), pp. 45-53.

  25. Hoffman, K.L. and Padberg, M.W. (1993), Solving Airline Crew Scheduling Problems by Branch and Cut, Management Science 39, 657-682.

    Google Scholar 

  26. Kim, Y.C. (1979), Open-Pit Limits Analysis: Technical Overview, in: A. Weiss (Ed.), Computer Methods for the 80’s (AIME, New York), pp. 297–303.

    Google Scholar 

  27. Kim, Y.C. (1979), Production Scheduling: Technical Overview, in: A. Weiss, (Ed.), Computer Methods for the 80’s (AIME, New York) pp. 610–614.

    Google Scholar 

  28. Lerchs, H. and Grossmann, I.F. (1965), Optimum Design of Open Pit Mines, Canad. Inst. Mining Bull. 58, 47-54.

    Google Scholar 

  29. Matheron, G. (1975), Le Parametrage des Contours Optimaux, Technical Report No. 403, Centre de Geostatistiques, Fontainebleau, France.

    Google Scholar 

  30. Matheron, G. (1975), Le Parametrage Technique des Reseues, Technical Report No. 453, Centre de Geostatistiques, Fontainebleau, France.

    Google Scholar 

  31. MineMax, Combinatorics Pty Ltd, Unit 4b, R&D Centre, 1 Sarich Way, Bentley, Western Australia, 6102.

  32. Padberg, M. and Rinaldi, G. (1991), A Branch and Cut Algorithm for the Resolution of Large Scale Travelling Salesman Problems, SIAM Review 33(1), 60-100.

    Google Scholar 

  33. Picard, J.C. (1976), Maximum Closure of a Graph and Applications to Combinatorial Problems, Management Sc. 22, 1268–1272.

    Google Scholar 

  34. Thomas, G. (1996), Optimization of Mine Production Scheduling - the State of the Art, in Proceedings IIR Dollar Driven Planning Conference.

  35. Thomas, G. Pit Optimization and Mine Production Scheduling - The Way Ahead, in: Proceed. 26th APCOM Symposium of the Society of Mining Engineers (AIME) (1976), pp. 221-228.

  36. Tolwinski, B. and Underwood, R. (1996), A Scheduling Algorithm for Open Pit Mines, IMA Journal of Mathematics Applied in Business and Industry 7, 247-270.

    Google Scholar 

  37. Whittle, J. (1993), Four-D User Manual, Whittle Programming Pty Ltd., Melbourne, Australia.

    Google Scholar 

  38. Whittle, J. (1998), Four-X User Manual, Whittle Programming Pty Ltd., Melbourne, Australia.

    Google Scholar 

  39. Whittle, J. (1990), Open Pit Optimization, Surface Mining (2nd Edition), AMIE pp. 470-475.

  40. Yamatomi, J., Mogi, G., Akaike, A. and Yamaguchi, U. (1995), Selection Extraction Dynamic Cone Algorithm for Three-Dimensional Open Pit Designs, in: Proceed. 25th APCOM Symposium of the Society of Mining Engineers (AIME) pp. 267–274.

Download references

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Curtin University of Technology, GPO Box U1987, PERTH, Western Australia, 6845 (E-mail

    Louis Caccetta & Stephen P. Hill

Authors
  1. Louis Caccetta
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stephen P. Hill
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Caccetta, L., Hill, S.P. An Application of Branch and Cut to Open Pit Mine Scheduling. Journal of Global Optimization 27, 349–365 (2003). https://doi.org/10.1023/A:1024835022186

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1024835022186

Search

Navigation