Open-Pit Mining

with integer programming and Gurobi

In this example we'll solve a simple mining problem: how to extract minerals from an open pit in order to generate the most profit.

We'll construct a mathematical model of the business problem, implement this model in Gurobi's Python interface, and compute and visualize an optimal solution.

Although your own business may not involve operating a mine, the same basic techniques used in this example can be used for other applications like selecting what projects your business should undertake.

Click the screenshot to skip directly to the Live Demo!

Live Demo

Problem Description

Open Pit Mine

An open-pit mine is a large cut made in the surface of the earth for the purpose of extracting ore. Unlike other mines, an open-pit mine does not require tunneling into the earth. The mine remains open to the surface for its entire lifetime.

Engineers use measurements of gravity, magnetism, and radioactivity to find a location for the mine that is rich in metal ore. As part of this survey, the subsurface of the unexcavated mine is divided into multiple blocks, and the concentraction of ore in each block is determined. Blocks with larger concentrations of ore provide more revenue for the mine.

However, there is a cost associated with extracting each block from the mine. Usually the deeper a block lies the more expensive it is to remove. In addition, blocks cannot be removed in arbitrary order. To remove a block, we must remove the blocks directly above, and to the left, and right, of it.

The picture below shows a set of blocks below the surface of the earth. Hover over each block, to see which blocks must be removed to access it. Notice that to remove block 5, we must first remove blocks 1, 2, and 3.

The business problem that a mine manager faces is to determine the set of blocks to remove from the mine. The goal is to extract the most profitable blocks from the mine, while leaving unprofitable blocks. However, the mine manager may be forced to extract unprofitable blocks in order to reach those that are rich in ore. Typically a plan, an order for the excavation of blocks in the mine, is made before any digging begins.

Mathematical Model

The open-pit mining problem is an instance of a more general problem known as project selection. In the project selection problem, a business manager wants to select a group of projects to undertake. Some projects are profitable, others are costly, and there are a set of dependencies between projects. We'll describe the mathematical model for this business problem in terms of blocks in a mine. But it's important to remember that the blocks can be viewed more generally as projects that a business wishes to complete.

We begin by defining a binary variable $x_i$ for each block in the mine: \[ x_{i} = \begin{cases} 1 & \text{if block $i$ is extracted} \\ 0 & \text{otherwise}. \end{cases} \]

In addition, there is a value $v_i$ associated with each block, and a cost $c_i$ to extract the block. This allows us to compute a profit $p_i = v_i - c_i$ for each block.

To remove a block, we must first remove the blocks directly above, and to the left, and right, of it. We can impose these constraints by constructing a precedence graph $G(V,E)$. The vertices $V$ in the graph represent the blocks, and we create an edge $(i, j)$ in the graph, if block $j$ must be removed before block $i$.

Our optimization model is then: \[ \begin{align*} \text{maximize} & \quad {\displaystyle \sum_{i} p_i x_i} \\ \text{subject to} & \quad x_i \leq x_j \quad \forall (i,j) \, \in E \label{prec} \tag{1}\\ & \quad x_i \in \{ 0, 1 \} \, \quad \forall i \in V \label{int}. \end{align*} \]

The objective of the model is simple, maximize the profit of the blocks that are selected to be removed.

Constraint \ref{prec} enforces the precendent constraints on the removal of blocks. If $x_i$ is 1, meaning block $i$ should be removed, then we must also have that $x_j$ is 1. The set of edges $E$ in the graph corresponds exactly to the pairs $(i,j)$ where block $j$ must be removed before block $i$.

For more information on models for open pit mining see the book: Mathematical Optimization Models and Methods for Open-Pit Mining.

Implementation

Below is the full implementation of the model (and the associated data) in Gurobi's Python interface:

from gurobipy import * # Example data for problem cost = [100, 100, 100, 100, 200, 200]; value = [50, 150, 150, 150, 300, 50]; edges = [[4,0], [4,1], [4,2], [5,1], [5,2], [5,3]]; m = Model() n = len(cost) # number of blocks # Indicator variable for each block x = {} for i in range(n): x[i] = m.addVar(vtype=GRB.BINARY, name="x%d" % i) m.update() # Set objective m.setObjective(quicksum((value[i] - cost[i])*x[i] for i in range(n)), GRB.MAXIMIZE) # Add constraints for edge in edges: u = edge[0] v = edge[1] m.addConstr(x[u] <= x[v]) m.optimize()

Live Demo

As an example we consider a mine where 28 blocks on 4 levels have been identified. The colors of the blocks correspond to different concentrations of ore (and hence different values of the blocks) and extraction costs increase with depth.

You can change the ore concentration of each block by clicking them. You can click the buttons on the top to change the type of concentration you want to add. Click the Mine away! button to compute the optimal block removing order using Gurobi. To restart, click on any block.

Try Gurobi for Free

We hope this example has taught you a bit about open-pit mining and using Gurobi. We encourage you to try the example out for yourself with Gurobi. To enable this, we provide easy access to a full-featured evaluation version of Gurobi.

We are always happy to discuss your needs and answer your questions. Just contact us at your convenience.