maximum flow

Nowadays due to the existence of the economic and geological uncertainties and the increasing use of scenario-based project evaluation in the design of open-pit mines, it is necessary to find an exact algorithm that can determine the ultimate pit limit in a short period of time. Determining the ultimate pit limit is an important optimization problem that is solved to define what will be eventually extracted from the ground, and directly impacts the mining costs, revenue, choosing mining equipment, and approximation of surface infrastructures outside the pit. This problem is solved in order to maximize the non-discounted profit under the precedence relation (access) constraints. In this paper, the Highest-Level Push-Relabel (HI-PR) implementation of the push–relabel algorithm is discussed and applied in order to solve the ultimate pit limit optimization problem. HI-PR uses the highest-label selection rule, global update, and gap heuristics to reduce the computations. The proposed algorithm is implemented to solve the ultimate pit limit for the nine real-life benchmark case study publicly available on the Minelib website. The results obtained show that the HI-PR algorithm can reach the optimum solution in a less computational time than the currently implemented algorithms. For the largest dataset, which includes 112687 blocks and 3,035,483 constraints, the average solution time in 100 runs of the algorithm is 4 s, while IBM CPLEX, as an exact solver, could not find any feasible solution in 24 hours. This speeding-up capability can significantly improve the current challenges in the real-time mine planning and reconciliation, where fast and reliable solutions are required.

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.