Document Type : Original Research Paper


1 School of Resources and Environmental Engineering, Wuhan University of Technology, Wuhan, Hubei, China

2 Mining, Materials and Petroleum Engineering Department, Jomo Kenyatta University of Agriculture and Technology, Nairobi, Kenya


The ultimate pit limit optimization (UPLO) serves as an important step in the mine planning process. Various approaches of maximum flow algorithms such as pseudo-flow and push-relabel have been used for pit optimization, and have given good results. The Boykov-Kolmogorov (BK) maximum flow algorithm has been used in solving the computer vision problems and has given great practical results but it has never been applied in UPLO. In this work, we formulate and use the BK maximum flow algorithm and the push-relabel maximum flow algorithm in MATLAB Boost Graph Library within the MATLAB software in order to perform UPLO in two case studies. Comparing both case studies for the BK maximum flow algorithm and push-relabel maximum flow algorithm gives the same maximum pit values but the BK maximum flow algorithm reduces the time consumed by 12% in the first case and 16% in the second case. This successful application of the BK maximum flow algorithm shows that it can also be used in UPLO.


[1]. Kennedy, B. A. (1990). Surface Mining, Second Edition. Society for Mining, Metallurgy, and Exploration.
[2]. Poniewierski, J. (2018). Pseudoflow Explained. Deswik, A discussion of Deswik Pseudoflow Pit Optimization in comparison to Whittle LG Pit Optimization
[3]. Ghebrihiwet, N. (2019). FDI technology spillovers in the mining industry: Lessons from South Africa's mining sector. Resources Policy, vol. 62,  463-471.
[4]. Chatterjee, S., Sethi, M. R., and Asad, M. W. A. (2016). Production phase and ultimate pit limit design under commodity price uncertainty. European Journal of Operational Research, vol. 248,  658-667.
[5]. Zhang, C., Pu, C., Cao, R., Jiang, T., and Huang, G. (2019). The stability and roof-support optimization of roadways passing through unfavorable geological bodies using advanced detection and monitoring methods, among others, in the Sanmenxia Bauxite Mine in China’s Henan Province. Bulletin of Engineering Geology and the Environment,  1-13.
[6]. Caccetta, L. and Hill, S. P. (2003). An application of branch and cut to open pit mine scheduling. Journal of global optimization, vol. 27,  349-365.
[7]. Gholamnejad, J. and Mojahedfar, A. (2010). Determination of the largest pit with the non-negative net profit in the open pit mines. Journal of Mining and Environment, vol. 1,  45-52.
[8]. Jamshidi, M. and Osanloo, M. (2018). UPL determination of multi-element deposits with grade uncertainty using a new block economic value calculation approach. Journal of Mining and Environment, vol. 9,  61-72.
[9]. Shishvan, M. S. and Sattarvand, J. (2012). Modeling of Accurate Variable Slope Angles in Open-Pit Mine Design Using Spline Interpolation/Modelowanie Zmiennego Kąta Nachylenia Stoku W Projektowaniu Kopalni Odkrywkowych Za Pomocą Interpolacji Funkcjami Sklejającymi (Metodą Spline’Ów). Archives of Mining Sciences, vol. 57,  921-932.
[10]. Akbari, A. D., Osanloo, M., and Shirazi, M. A. (2009). Reserve estimation of an open pit mine under price uncertainty by real option approach. Mining Science and Technology (China), vol. 19,  709-717.
[11]. Bai, X., Turczynski, G., Baxter, N., Place, D., and Sinclair-Ross, H. (2017). Pseudoflow Method for Pit Optimization.
[12]. Zhao, Y. (1992). Algorithms for optimum design and planning of open-pit mines. Doctoral Dissertation, University of Arizona.
[13]. Koenigsberg, E. (1982). The optimum contours of an open pit mine: an application of dynamic programming. in 17th Application of Computers and Operations Research in the Mineral Industry.
[14]. Johnson, T. B. (1968). Optimum open pit mine production scheduling. California Univ Berkeley Operations Research Center, California Univ Berkeley Operations Research Center.
[15]. Pana, M. and Davey. (1965). The simulation approach to open-pit design. in Proceeding of 5th International APCOM.
[16]. Korobov, S. (1974). Method for Determining Optimal Ultimate Open Pit Limits. Ecole polytechnique de Montréal.
[17]. Zhao, Y. (1992). A new optimal pit limit design algorithm. in Proc. of the 23rd APCOM,  423-434.
[18]. Khalokakaie, R., Dowd, P., and Fowell, R. (2000). Incorporation of slope design into optimal pit design algorithms. Mining Technology, vol. 109,  70-76.
[19]. Kakaie, R. (2012). A new algorithm for optimum open pit design: Floating cone method III. Journal of Mining and environment, vol. 2,  118-125.
[20]. Wright, A. (1999). Moving Cone II -A simple algorithm for optimum pit limits design. in Proceedings of the 28rd APCOM,  367-374.
[21]. Khalou, K. R. (2007). Optimum Open Pit Design with Modified Moving Cone II Methods. Journal of Faculty of Engineering (University of Tehran), vol. 41,  297-307.
[22]. Dowd, P. and Onur, A. (1992). Optimizing open pit design and sequencing. in Proceedings 23rd Application of Computer in Mineral Industry,  411-422.
[23]. Thorley, U. (2012). Open Pit Mine Planning: Analysis and system modeling of conventional and oil sands applications. Queen’s University, Kingston, Ontario, Canada.
[24]. Sayadi, A. R., Fathianpour, N., and Mousavi, A. A. (2011). Open pit optimization in 3D using a new artificial neural network. Archives of Mining Sciences, vol. 56,  389–403.
[25]. Souza, F. R., Melo, M., and Pinto, C. L. L. (2014). A proposal to find the ultimate pit using Ford Fulkerson algorithm. Rem: Revista Escola de Minas, vol. 67,  389-395.
[26]. El-Karmouty, M., El-Wageeh, M., El-Aziz, A. A., and El-Shayeb, Y. (2013). New Technique- “One Three-One Two (13-12)”-In Ultimate Pit Limit Heuristic Algorithms. in The 45th International October Conference on Mining and Metallurgy Bor Lake, Bor (Serbia),  397-400.
[27]. Marcotte, D. and Caron, J. (2013). Ultimate open pit stochastic optimization. Computers & Geosciences, vol. 51,  238-246.
[28]. Khodayari, A. A. (2013). A New Algorithm for Determining Ultimate Pit Limits Based on Network Optimization. Int. Journal of Mining & Geo-Engineering, vol. 47,  129-137.
[29]. Sasaki, K., Dindiwe, C., and Adachi, T. (2001). Optimization of open pit limit designs by newly BPITC approach and initial feasibility study using block grade data set estimated by geostatistical simulation. Journal of the Mining and Materials Processing Institute of Japan(Japan), vol. 117,  62-70.
[30]. Milani, G. (2016). A Genetic Algorithm with Zooming for the Determination of the Optimal Open Pit Mines Layout. The Open Civil Engineering Journal, vol. 10,  301-322.
[31]. Petrov, D., Vasiliev, P., Mikhelev, V., Muromtcev, V., and Batischev, D. (2017). Using parallel computing in modeling and optimization of mineral reserves extraction systems. Journal of Fundamental and Applied Sciences, vol. 9,  939-947.
[32]. Muir, D. (2007). Pseudoflow, New Life for Lerchs-Grossmann pit optimisation. presented at the Orebody Modelling and Strategic Mine Planning, AusIMM Spectrum Series.
[33]. Whittle, D., Brazil, M., Grossman, P. A., Rubinstein, J. H., and Thomas, D. A. (2018). Combined optimisation of an open-pit mine outline and the transition depth to underground mining. European Journal of Operational Research, vol. 268,  624-634.
[34]. Verma, T. and Batra, D. (2012). MaxFlow Revisited: An Empirical Comparison of Maxflow Algorithms for Dense Vision Problems. in BMVC,  1-12.
[35]. Dinic, E. A. (1970). Algorithm for solution of a problem of maximum flow in networks with power estimation. in Soviet Math. Doklady,  1277-1280.
[36]. Boykov, Y. and Kolmogorov, V. (2004). An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis & Machine Intelligence,  1124-1137.
[37]. Muir, D. (2007). Pseudoflow, new life for Lerchs-Grossmann pit optimisation. Orebody Modelling and Strategic Mine Planning, AusIMM Spectrum Series, vol. 14,
[38]. Gleich, D. (2006). MatlabBGL. Accessed via,
[39]. Siek, J., Lumsdaine, A., and Lee, L.-Q. (2002). The boost graph library: user guide and reference manual. Addison-Wesley.
[40]. Espinoza, D., Goycoolea, M., Moreno, E., and Newman, A. (2013). MineLib: a library of open pit mining problems. Annals of Operations Research, Accessed via, vol. 206, 93-114.