Gordon Thomas and Andrew Esmaili
Technical Product Manager and Product Analyst, Micromine
Abstract
Since the publication of Lerchs and Grossmann’s seminal paper, “Optimum Design of Open Pit Mines” [1], in 1965, considerable effort has been focused towards the development of a comparable algorithm for the design of underground mines. This paper discusses the reasons for this, explores why the Lerchs-Grossmann algorithm and the newer pseudoflow variants are not directly suited to the task, and outlines the capabilities and deficiencies of some of the heuristics that have been proposed.
The availability of powerful mathematical programming solvers has now made it possible to generate stope designs that are optimal in the same sense as those produced for open pits by the Lerchs-Grossmann algorithm. Using a selection of examples analysed with MICROMINE’s new Stope Optimiser, the paper proceeds to compare the performance of the heuristics with that of the solver, both in terms of the qualities of the solutions produced and the computational resources required to produce them. It concludes with a discussion of the comparative advantages of each approach and the potential outcomes from future research and development.
Background
Ultimate Pit Determination for Open-Pit Mine Design
In the long term planning and design of open-pit mines, the goal of ultimate pit determination is to determine the pit outline that yields the highest profit for a given set of slope angles. Typically, this analysis is performed on a discretized model of the mine – a three dimensional block model in which each block has been assigned a value that represents the value of the material contained within the block after it has been extracted, processed and sold. Thomas [3], and many other authors, have reviewed the methods and assumptions for determining the ultimate pit outline.
Effectively, most algorithms for determining the ultimate shape of an open-pit mine operate by extracting a set of overlapping “cones” of blocks from a three dimensional block model of the deposit. For each block in the model, an extraction cone is defined to specify the blocks that must be removed in order to access that block. The dimensions of each extraction cone are determined by the depth of the block to which it applies, and the maximum slope angles permitted at that location.
The qualities of the solutions produced by the various algorithms are governed by their abilities to deal with the challenges of allowing for the effects of multiple overlapping cones without double counting or omissions.
The requirement for only a single, predefined set of blocks to be removed for each block, combined with the freedom to enforce these dependencies recursively without fear of encountering cycles of mutual dependence between blocks, simplifies the complexity of the algorithms required. It is possible to apply the appropriate dependencies recursively to any “accessible” block (i.e. one that can be reached from the surface without violating the slope restrictions) within the model and be guaranteed of generating a feasible pit. Repeating this process from other suitable blocks will generate more feasible pits. Since there is no requirement for these feasible pits not to overlap, and the intersection of multiple feasible pits will always be a feasible pit itself, the role of the optimising algorithm is reduced to determining the maximum possible value from all feasible pits that can be generated from suitable source blocks.
Today, the algorithms most commonly employed in commercial software packages for this purpose are the Lerchs-Grossmann 3D Graph Theory algorithm [1], the Pseudoflow algorithm (Hochbaum [6]), and variations thereof. These algorithms can produce solutions to the problem that are provably optimal (“rigorous”), subject to any stated simplifying assumptions.
Recent innovations address the cyclic nature of mine design and scheduling using mathematical programming solvers to derive the design and the schedule concurrently.
Stope Optimisation for Underground Mine Design
Also using a three dimensional block model of the deposit, the goal of stope optimisation is to determine the optimum configuration of stopes that will yield the highest profit for a given set of stope sizes and shapes.
However, it was not until the mid 1990’s that papers on determining the optimum design of underground mines (Alford [2], Thomas and Earl [4]) began to appear. Most of the published stope optimisation algorithms have been “heuristics”, in that that they lack mathematical proof of their optimality and may be capable of finding only approximate solutions. Many have limitations that are readily identified (Sandanayake [9], Nhleko et al [10]), and none are claimed to produce optimum solutions for the sizes of problems that are typically encountered in mine planning.
Alford et al [7] alludes to several new formulations of the stope optimisation problem, with proven optimality, that have been applied successfully in research. However, the scarcity of subsequent published references to this work suggests that it may now be protected by commercial agreements.
In contrast to ultimate pit determination, because the set of blocks to be removed for each block in a potential stope can also include adjacent blocks in any direction (not simply restricted to above – and vice versa), attempts to apply dependencies recursively in the same manner will quickly degenerate to the extraction of all blocks to the boundaries of the model in the directions to which the dependencies are directed. Although it is still possible to generate feasible stopes around each block from a single set of dependencies, the algorithm must determine, in addition to the optimum set of source blocks, the optimum positioning of the stope(s) around each block. Depending on the requirements, it may also be required to ensure that the generated stopes do not overlap and to minimise sterilisation from pillaring.
The important differences between ultimate pit determination and stope optimisation are summarised in Table 1.
Table 1. Ultimate Pit Determination vs Stope Optimisation
Consequently, in the forms in which they are usually implemented for pit optimisation, neither the Lerchs-Grossmann 3D Graph Theory algorithm, nor the newer pseudoflow variants, are directly suitable for stope optimisation.
Benefits of Rigorous Solutions
Heuristics may suffer from one or more of the following deficiencies:
- It may be difficult to quantify how close the solution lies to the mathematical optimum.
- The quality of the solution may be dependent on the structure of the problem and/or the configuration of the data presented.
- Decisions made in early processing may affect the choices available to later decisions, thereby compromising the ability to satisfy subsequent constraints. If some form of self-correction or ability to explore alternative decision paths is not incorporated, this may result in significant deviations from the mathematical optimum and, in extreme cases, may lead the heuristic to deem the problem to be infeasible.
Each heuristic may be impacted by different facets of the problem in different ways.
When performing sensitivity analyses to assess the impacts of changes to design parameters, such as slope restrictions, stope dimensions or grade cutoffs, these characteristics of heuristics are highly undesirable because it is not possible to ascertain whether any variations between scenarios have resulted from the changes in the design parameters or from deficiencies in the heuristic employed. Rigorous algorithms do not suffer from these problems and, given sufficient processing time, can always be relied upon to produce mathematically optimum solutions for different sets of design parameters. As a result, any variations between scenarios can be attributed solely to changes in those parameters.
The success of Whittle Programming’s Three-D and Four-D software products was founded on the mathematical proof provided by Lerchs and Grossmann [1] for their algorithm, and these products have set the standard for bankable feasibility study and sensitivity analysis tools for open-pit mine planning for the past 30 years.
Heuristics for Stope Optimisation
Heuristics that have been published and/or commercialised for determining optimum stope outlines from a three dimensional block model include those listed in Table 2.
Table 2. 3D Stope Optimisation Heuristics by Year
Alford [2] describes the Floating Stope algorithm and includes a discussion of its limitations. Thomas and Earl [4] summarises the capabilities of their algorithm and illustrates potential applications, and Alford et al [7] provides additional detail on its operation. Ataee-Pour [5] describes the Maximum Value Neighbourhood Method, which appears to be based on concepts similar to those of the “inner” envelope from the Floating Stope algorithm. These algorithms generate sets of stope outlines that may overlap as required.
The later algorithms from Topal and Sens [8] and Sandanayake [9] include the restriction that the generated stopes must not overlap. Including this restriction, or any requirement for pillars between the generated stopes, requires the algorithms to be cognizant of the potential for early decisions to compromise the options available for subsequent decisions. Sandanayake [9] addresses this by exploring more of the solution space; however, success is subject to the effects of combinatorial explosion.
Additional detail on the workings and limitations of these heuristic algorithms can be found in Sandanayake [9] and Nhleko et al [10].
Mathematical Programming
Mathematical programming problems involve the optimisation of an objective function that depends on a set of decision variables, which may be bounded and/or constrained, and fixed parameters.
Within this context, the term “mathematical programming solver” (“solver”) refers to computer software that can optimise supported generic objective functions using any type of mathematical programming. Wellknown commercial mathematical programming solvers include CPLEX, Gurobi, LINDO and MATLAB.
With the significant, and ongoing, enhancements to the performance and capabilities of solvers over the course of the last 20 years, combined with commensurate increases in the processing power of desktop computers, it is now feasible to apply these tools to problems of the size and nature that are typically encountered in mine planning.
New Mathematical Programming Models for Stope Optimisation
MICROMINE has successfully implemented new mathematical programming models for stope optimisation. These models have been formulated for and tested with different types of solvers and can generate three dimensional stope outlines from a block model that are provably optimal for the specified design parameters.
Stope Design Parameters. The following stope design parameters are supported by the new models for multiple regions in the block model:
-
- Sizes and orientations of axes for minimum stope;
- Whether multiple minimum stopes may be overlapped to form larger shapes;
- Maximum axial growth of minimum stope;
- Size of pillars required between stopes;
- Centreline strings, planes or digital terrain models to which stopes must be anchored;
- Regions to/from which stopes should be confined/excluded; and
- All relevant economic parameters used in pit optimisation.
Results Produced. Outputs from the new Stope Optimiser include:
-
- Stope wireframes and/or coordinates of blocks comprising the optimum solution;
- Nested groupings of stopes to assist in staging and development planning; and
- Full suite of reports to facilitate postprocessing and analysis of all input parameters, block processing outcomes and generated stopes.
Applications. Using appropriate combinations of design parameters in conjunction with suitable economic parameters, it is possible to analyse a variety of scenarios and mining methods, including:
-
- Identifying regions within a resource that can be mined profitably using sublevel open stoping, cut and fill stoping, shrinkage stoping, bighole stoping, vertical crater retreat, room and pillar mining, sublevel caving or block caving;
- Optimum sizing and staging of underground mining operations using standard pit optimisation methodology and discounted cash flow analysis;
- Determining the optimum outer envelope for profitable mining subject to a minimum mining volume;
- Determining the optimum digline for an open-pit bench subject to a minimum mining width;
- Planning locations of underground access drives; and
- Identifying ore and waste envelopes for use in ring design.
Verification of Results
One of the challenges in developing any new algorithm is to establish and verify the quality of its solutions. Although solutions generated by solvers are provably optimal, it is still necessary to verify that the formulations of the models presented satisfy any applicable constraints and produce the expected results. At the very least, this means that it should not be possible to generate superior results using other methods.
The verification work included the development of several new heuristics for stope optimisation to test the solution performance of the mathematical programming model. Conversely, it also provided the opportunity to assess the performance of the heuristics.
Sample Problems
To facilitate independent analysis by future researchers, the new mathematical programming model and heuristics were tested on data sets from MineLib [11].
Summaries of the selected data sets, with the names of the fields from which the values for optimisation were sourced, appear in Table 3. To assist with identification of the value field, the values for the block with ID=0 are included. Representative quantities of negative values were ensured by applying adjustments to optimisation values for all blocks as required.
Table 3. Sample Problems for Stope Optimisation Testing
To facilitate comparison of the results with those from the best heuristics, stopes were permitted to be positioned and overlapped as required within the model, and there was no requirement for pillaring. The following stope sizes were tested:
- 3 x 2 x 4 blocks
- 5 x 4 x 6 blocks
- 6 x 9 x 4 blocks
The results are summarised in Table 4. The value of the best solution produced by the solver is reported in “Best Solver Value”.
As an integral part of its operation, the solver determines and maintains an upper limit for the total value of an extraction that could satisfy the design parameters. This is reported in “Solver Bound”. The qualities of the solutions produced by the solver (“Solution Quality – Solver”) and the best of the heuristics (“Solution Quality – Best Heuristic”) are expressed as a percentage of this bound, with a value of 100% indicating that the solver was able to verify that it had found the optimum solution. Some solver runs were terminated prematurely in the interests of expediency.
Table 4. Stope Optimisation Results for Sample Problems
Table 5 contains images of the 5 x 4 x 6 and 6 x 9 x 4 stope wireframes generated for SM2 overlaid on the profitable blocks. The images confirm that the stopes span the profitable blocks as required, with the 5 x 4 x 6 stopes able to do this more selectively than the 6 x 9 x 4 stopes as a result of the way that those blocks are distributed. This is reflected in the lower total value.
Table 5. Stope Optimisation Results for SM2 (Sample Problem #2)
Observations and Conclusions
As expected, the optimum values for each model decreased as the number of blocks in the minimum stope increased. This is due to the increased likelihood of encountering waste blocks in larger stopes, thereby making those stopes less valuable and less likely to be included and reducing the combined total values.
If the stopes are permitted to overlap and there is no requirement for pillaring, the best heuristics have been capable of producing values that are close to the mathematical optimum for all examples tested.
As deposit variability or the number of blocks in the minimum stope increases, it becomes more difficult for the solver to determine an accurate bound for the total value of the extraction, which increases the time required to find the optimum. However, in all examples tested, this has not affected the relative solution performance of the best heuristics, which require less processing time, significantly.
As the complexity of the problem increases through requirements for non-overlapping stopes, or pillars between the stopes, it becomes more difficult to obtain near optimal solutions from heuristics within reasonable time frames. With solver solutions now available for use as benchmarks, future work will be directed towards addressing these challenges and reducing solution times further.
The new mathematical programming models accept many common stope design parameters and generate stope layouts that are provably optimal. Combined with support for multiple elements and processing methods, dilution, recovery and revenue and cost adjustment factors, the software provides a seamless transition for practitioners of pit optimisation into the world of stope optimisation.
References
- Lerchs, H., Grossmann, L.: Optimum Design of Open-Pit Mines. In: Transactions, Canadian Institute of Mining and Metallurgy, Vol. LXVIII, pp. 17-24 (1965).
- Alford, C., Optimization in Underground Mine Design. In: Proceedings APCOM XXV 1995 Applications of Computers and Operations Research in the Mineral Industries, pp 213-218. The Australian Institute of Mining and Metallurgy, Brisbane, Australia (1995).
- Thomas, G.S., Pit Optimisation and Mine Production Scheduling – The Way Ahead. In: Ramani, R.V., (ed.) Proceedings APCOM XXVI 1996 Applications of Computers and Operations Research in the Mineral Industry, pp 221-228. Society for Mining, Metallurgy and Exploration. Pennsylvania State University, USA (1996).
- Thomas, G.S., Earl, A.: The Application of Second Generation Stope Optimisation Tools in Underground Cut-Off Grade Analysis. In: Strategic Mine Planning Third Biennial Conference, Whittle Programming Pty Ltd, Perth, Western Australia (1997).
- Ataee-Pour, M.: A Heuristic Algorithm to Optimise Stope Boundaries. PhD Dissertation. Faculty of Engineering, University of Wollongong, Australia (2000).
- Hochbaum, D.S.: A New-Old Algorithm for Minimum-cut and Maximum-flow in Closure Graphs, 30th Anniversary Special Paper in: NETWORKS, Vol 37(4), pp 171-193 (2001)
- Alford, C., Brazil, M., Lee, D.: Optimisation in Underground Mining. In: Handbook of Operations Research in Natural Resources, Vol. 99, pp. 561-577. Springer US (2007).
- Topal, E., Sens, J.: A new algorithm for stope boundary optimization. Journal of Coal Science and Engineering, Vol. 16, No. 2, pp 113-119 (2010).
- Sandanyake, D.S.S.: Stope boundary optimisation in underground mining based on a heuristic approach. PhD Dissertation. Curtin University, WA School of Mines (2014)
- Nhleko, A., Tholana, T., Neingo, P.: A review of underground stope boundary optimization algorithms. In: Resources Policy. https://doi.org/10.1016/j.resourcpol.2017.12.004
- Espinoza, D., Goycoolea, M., Moreno, E., Newman, A.: MineLib: A Library of Open Pit Mining Problems. In: Annals of Operations Research, Vol. 206, Issue 1, pp 93–114 (July 2013). Also: http://mansci-web.uai.cl/minelib, last accessed 2019/05/14.
- Alford Mining Systems: Mineable Shape Optimiser, http://alfordminingsystems.com/?page_id=74, last accessed 2019/06/07.
