Open Pit Mine Optimization with Maximum Satisfiability

A common casualty of modern open pit mine optimization is the assurance that the resulting design is actually achievable. Optimized mine plans that consider value and a bare minimum of precedence constraints do not, in general, translate into practical, operational mine designs that can really be used in the field. Ultimate pits may come to a sharp point at the bottom. Schedules may require taking small parcels of material from many disparate areas of the pit in a single period. And grade control polygons may be ragged, narrow, and not minable with realistic equipment. In this paper all of these problems are addressed by encoding these three fundamental open pit mine optimization problems as maximum satisfiability problems. Maximum satisfiability provides a useful framework for problems that are non-linear and may guarantee the optimality that metaheuristics cannot. INTRODUCTION Open pit mines are large and complicated operations, which require significant initial and ongoing investment. A single mine may employ hundreds or thousands of people and creates substantial benefits for both the surrounding and global communities. Planning an operation of this magnitude requires a lot of effort and cannot be done optimally by hand. Mining engineers today rely on many techniques from operations research to guide decision making, and to maximize the value of the mine. Techniques including linear programming, metaheuristics, and network algorithms are all used to solve different problems throughout mine design and optimization. However, techniques based on Boolean satisfiability, including the optimization extension of maximum satisfiability, have not seen much use in mining despite being used in many other fields including electronics design, scheduling, and artificial intelligence. We claim that maximum satisfiability is a useful and meaningful way of expressing and solving optimization problems in mine planning. However, this technique does not come without challenges; the problem is NP-hard, and modern techniques for solving these problems can struggle with the number of variables and clauses that a typical mining problem requires. Also, some of the constraints that mining must contend with do not fit nicely into the satisfiability paradigm. Despite these challenges, we believe that maximum satisfiability provides a useful framework for considering operational constraints and expressing some problems that other techniques can't easily express. Maximum satisfiability can be solved exactly, yielding the true optimal answer which metaheuristics cannot guarantee. In this paper we show the applicability of maximum satisfiability to mining by specifying three fundamental problems in open pit mine optimization. We show how these fundamental problems can be formulated and how they can be extended within the framework of maximum satisfiability. For the remainder of the paper we first give a brief background on common elements between the three problems and an introduction to satisfiability. Then we tackle the three problems; the Ultimate Pit Problem, the Block Scheduling Problem, and the Grade Control Polygon Problem. In the Ultimate Pit Problem we specifically show how to extend the problem to support a minimum mining width – a coveted result for many mining engineers. We then discuss some of the complexities and shortcomings of this framework and possible research directions.