Stephen Hill and Cristian Poblete, GEOVIA Dassault Systèmes, Australia, discuss the benefits of implementing optimization engines in strategic mine planning to improve workflow and operational efficiencies.
The creation of a strategic mine plan is a challenging task. Mining engineers need to plan the extraction of earth blocks to maximise profits while adhering to product requirements and operational and sustainability constraints. Each block has attributes like mineral grade, tonnage, and other rock properties, along with constraints such as extraction capacity, slope angles, and operational constraints. The inclusion of these constraints is critical to ensure mining operations’ safety, efficiency, and profitability. To solve this intricate problem, a mining engineering team will use their skills, experience, and mine planning optimisation tools to construct a viable solution.
Dassault Systèmes, GEOVIA has created a new mine planning optimisation engine called GMX (GEOVIA Mine Maximizer). GMX is the solution engine available exclusively in the Strategic Mine Planner and Pit Optimizer roles available on the 3DEXPERIENCE platform.
Historical context and advancements
The Lerchs and Grossmann algorithm (LG) was first used in 1965 to solve the most economical pit shape optimally. It identifies the set of blocks that can be mined to maximise the economic value of the mine, considering only the physical constraints of maximum wall slopes for stability.
Later developments showed that the problem could be modelled as a flow problem, leading to the development of the Pseudoflow algorithm, which produced results much faster than LG. However, these methods do not consider the temporal aspect of mining operations, such as discounting of value or equipment production rate, which is crucial for long-term planning.
Multi-period problems and MILP
Multi-period problems, which involve planning over several time periods, introduce additional complexity. These problems must account for hard constraints related to the sequencing of block extraction, processing limits, and ore blending requirements. Such constraints can be modelled as a Mixed Integer Linear Programming (MILP) problem. Over the years, this approach has relied on commercial solvers like CPLEX or Gurobi to solve it. However, the primary challenge remains the execution time, which increases exponentially with the size of the problem.
Addressing execution time challenges
To address the execution time challenge, other approaches using heuristics have been developed. These heuristics aim to find good solutions within a reasonable time-frame, though they cannot guarantee that the solutions are close to the optimal. This trade-off between solution quality and computational efficiency is a key consideration in strategic mine planning.
BZ algorithm
Recent mining planning studies have introduced new methodologies. Among these, the Bienstock-Zuckerberg (BZ) algorithm has emerged as a key development since its introduction in 2009. The BZ algorithm is an advanced mathematical optimisation technique designed to solve large opencast mine planning problems. It addresses the execution time challenges for these problems by efficiently solving the easier linear programming (LP) problem. This solution technique can then be used to solve the problem optimally or used in a heuristic to generate a good solution.
Like with MILP solver, the primary goal of the BZ algorithm is to maximise an objective function obtained from the extraction of mining blocks while adhering to various constraints such as mining capacity, wall slope, and ore blending specifications. Common objective functions aim to maximise profit, but can also seek to minimise other objectives, such as CO2 emissions.
Key features and functionality
1. Holistic modelling: Unlike traditional heuristic methods, the BZ algorithm is a global optimisation technique that can holistically model the mining problem. Hence, it often leads to solutions closer to the global optimum.
2. Simplify the problem: The BZ algorithm uses a Lagrangian decomposition technique to break down the original problem into more manageable subproblems to solve the overall problem. This is achieved by dividing the constraint set into precedence and a smaller set of hard constraints. The BZ algorithm groups variables into partitions, simplifying the problem. These partitions are iteratively refined by solving subproblems, including a master LP problem. The goal is to converge to an optimal solution through these iterations.
Step-by-step algorithm
1. Initial formulation: The original problem is formulated as a MILP, identifying all constraints and the objective of maximising extraction value.
2. Problem division: Constraints are divided into precedence constraints (e.g., wall slopes) and hard constraints (e.g., mining capacity).
3. Pseudoflow solution: The precedence constraint subproblem is solved using the Pseudoflow algorithm, which efficiently handles network flows. For each iteration, Pseudoflow costs are updated using penalties that come from the LP Master problem.
4. Partitioning and refinement: Variables are grouped into partitions and solved iteratively. Each iteration adjusts the partitions based on the results from the master LP problem and the Pseudoflow sub-problem, refining the solution.
5. Convergence: The iterative process continues until the LP Master problem and the Pseudoflow sub-problem solutions converge, indicating that an optimal solution has been found.
The new optimisation engine
GMX uses the BZ algorithm and various speed-ups from the Dassault Systèmes – GEOVIA R&D Team and other authors’ work. The benefits of this new work, compared to traditional approaches of formulating the problem and then solving it using a commercial MILP software package, are clear. For a class of mine planning problems, which includes stockpiling, the speed of GMX allows Dassault Systèmes to create the best/near best solutions quickly.
To illustrate the effectiveness of this work, Dassault Systèmes conducted a comparative analysis using the well-documented KD copper mine problem. KD is a copper mine with 14 153 blocks, of which 12 154 appear in the Ultimate Pit to be scheduled over 12 time periods. Each block can go to two destinations, where it is processed as ore or sent to dump as waste. For benchmarking, the company used a commercial MILP software package that employs either the Simplex or Barrier algorithm to solve the LP problem. This commercial solver completed the task in 78.5 min. GMX solves the LP in 2.6 seconds, a 1811x speed-up!
A feature of GMX is its use of a new scheme to reduce the number of BZ iterations significantly. Figure 2 illustrates the effectiveness of this approach by example. For the largest MineLib literature problem, McLaughlin, the number of iterations was 79, using an early implementation of the original BZ algorithm. For the new implementation, this has been reduced to 16 iterations. Of note is the rate of change of the Optimality Gap from one iteration to the next, highlighting the much faster convergence and run times.
Computational results
Figure 3 shows the results for the nine benchmark MineLib literature projects. These are Direct Block Scheduling (DBS) problems of various sizes, having processing and/or extraction capacity constraints. All test runs were completed on a standard Lenovo ThinkPad P53 laptop. The BZ algorithm runs until different bounds converge (the BZ Optimality Gap is less than 10 power -6). The last column reports the time to do this work in seconds(s).
Once the LP has been solved, Dassault Systèmes runs ten variants of the literature TopoSort heuristic and the Optimize-Destinations heuristic, to create near-optimal solutions. The combined runtime for these heuristics is fast, taking less than a minute to complete on average. The total maximum runtime to produce a solution is under 5 and a half minutes. Comparing the Optimality Gap (GMX Gap) to the best literature result (Literature Gap), it is clear that best/near best solutions are produced in each case. Lastly, these results compare favourably to those of specialised meta-heuristics, which can take many hours to run.
Conclusion
The GMX engine, using a fast implementation of the BZ algorithm, is the cornerstone of the new Dassault Systèmes’ strategic mine planning solutions suite running on the 3DEXPERIENCE platform. These solutions incorporate a comprehensive workflow for scheduling and design.
This new capability facilitates an improved workflow, allowing mining engineers to explore many scenarios they otherwise would not have time to assess. By exploring more scenarios, project risk is reduced, and operational efficiencies are enhanced, leading to better overall results. This acceleration facilitates quicker strategic decisions and ensures results are closely aligned with company objectives.
GMX, along with the integrated workflow tools, fosters better collaboration and further insights into the key mine drivers. Nonetheless, it is understood that this is only the beginning. Dassault Systèmes’ future work will extend GMX to include additional strategic mine planning features, allowing the company to be optimistic about the future of strategic mine planning.
Community is a place for GEOVIA users – from beginners to experts and everyone in between – to get answers to your questions, learn from each other, and network. Join our community to know more:
GEOVIA User Community – Read about industry topics from GEOVIA experts, be the first to know about new product releases and product tips and tricks, and share information and questions with your peers. All industry professionals are welcome to learn, engage, discover and share knowledge to shape a sustainable future of mining.
New member? Create an account, it’s free! Learn more about this community HERE.
When mining companies seek to increase mine productivity, they turn to Dassault Systèmes for technology and services. It is home to world-renowned and award-winning mining solutions and to industry thought leaders who are pushing the boundaries of what’s possible in mining, through the GEOVIA brand. The largest global supplier of mining software, GEOVIA delivers comprehensive solutions in all major mining centers in more than 130 countries at over 4,000 sites.