What is Dynamic Programming and How It Is Applied In Mining When Making Decisions Over Time

(By Dr. Luis A. Martinez)

INTRODUCTION

Decision making in mine project evaluation is not a trivial process. This is not only because of the complexity of the different operational and economic variables that need to be considered, but also because these decisions need to be made over time, i.e., considering the future which is uncertain. We introduce the idea of Dynamic Programming and the Principle of Optimality as one useful technique for making ‘optimal’[1] decisions over time.

CONTROL AS OPTIMISATION OVER TIME

Optimisation is key in mine project evaluation. Sometimes it is important to solve a specific mining problem optimally. Other times a near-optimal practical solution is good enough to solve the problem. Either way, optimisation is useful as a way for maximising value over time.

Control theory is concerned with dynamic systems and their optimisation over time. It accounts for the fact that a dynamic system may evolve stochastically and that key variables may be unknown or imperfectly observed (as we see, for instance, in the metal market). In this sense, a mine project is visualised as a very complex dynamic system which needs to be optimised over time. 

Control theory contrasts with optimisation models such as those of Linear Programming and Network Flow models, which are used for static problems where nothing is random or hidden. It is these three new features: dynamic and stochastic evolution, and imperfect state of observation, that give rise to new types of optimisation problems and which require new ways of thinking.

THE PRINCIPLE OF OPTIMALITY

The key idea to be introduced is that optimisation over time can often be regarded as ‘optimisation in stages’. We trade off our desire to obtain either the highest revenue or the lowest possible cost at the present stage against the implication this would have for revenues or costs at future stages. For example, the best action will maximise the sum of the revenue at current stage and the most total revenue that can be obtained from all subsequent stages, consequent on this decision[2]. This is known as the Principle of Optimality.

Definition: Principle of Optimality

From any point on an optimal trajectory, the remaining trajectory is optimal for the corresponding problem initiated at that point.

EXAMPLE: MAXIMISING PROJECT NPV

Consider the ‘mining net present value (“NPV”) maximisation problem’ in which a mine manager wishes to maximise the NPV of a mine project. As displayed in Figure 1 the life of mine of the project is four years, or production periods.

 In this case, the mine manager is faced with different paths for production scheduling, e.g., ABEHJ, and she needs to decide the best schedule path for the mine, i.e., the production scheduling path that maximises current project NPV. In Figure 1, the cash flow (“CF”) generated in a specific production period, P, depends on the path selected and is given by the number connecting the nodes specifying the path; e.g., if path AB is selected for production period P1, then CF=$2m. For discounted cash flow purposes we consider an annual discount rate of 10%.

Fig 1. Available Paths for Production Scheduling.

Solving the problem using the traditional greedy optimisation technique

It is common practice in mine project evaluation to optimise the mine by selecting the highest value at earlier production periods. This is done thinking that it will provide, apparently, the best project value outcome. Figure 2 shows the result of applying the greedy algorithm technique to estimate the project NPV. In this case the selected production scheduling is given by the path ACGIJ which generates high cash flows early in the project, and an NPV of $11.9m.

Fig 2. Greedy technique to estimate project NPV. In this case NPV=$11.9 million (assuming CAPEX=0).

Solving the problem using the principle of optimality: Dynamic Programing

To solve the problem using the Dynamic Programing technique first we divide the problem in stages, in this case there are 4 stages. The process then starts the optimisation process at the end of the life of mine (node J) and goes backwards optimising each production period until arriving to the beginning (i.e., node A). For example, the optimisation process at the last production period outputs the path JI with a CF=$4m. Then it passes to optimise period 3 by selecting the path IE with a CF=$4m, and so on.

Fig 3. DP technique to estimate project NPV. In this case NPV=$13.3 million (assuming CAPEX=0).

In this case, the DP process found that the path ABEIJ provides the best project NPV of $13.3m which is 17% greater than the value estimated using the traditional technique.

COMMENTS AND CONCLUSIONS

Decision making in mine project evaluation is critical and non-trivial. Optimisation techniques are key in identifying the best strategies to implement, i.e., the ones that maximise project value, that otherwise are hidden to the normal vision or intuition. For example, in the mine project value optimisation problem, shown in Figure 1, intuition would say to choose path ACGIJ as it maximises cash flow value from the first production period to the last period (see Figure 2). This type of process belongs to the family of greedy algorithms which follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

However, if we apply the principle of optimality when using DP we will find that the best production scheduling results from following path ABEIJ, which against all intuition, starts by producing a small cash flow during the first year ($2m) but  overall it produces the highest value.   

Even though the problem solved in the example is simple, it clearly shows the benefits of using DP when optimising complex dynamic processes over time. As a matter of fact, when correctly applied DP is a powerful tool that solves more complex problems in mining and is used in advanced decision making processes such as real options analysis; this is done using the Bellman’s equation (see for example Dixit and Pindyck, 1994).

In conclusion, it is recommendable to use optimisation techniques, such as DP, when evaluating mine projects, as the lack of using them could result in spurious results misleading mine managers to make improper decisions.

[1] Note that here we refer to optimality based on the available data.

[2] Similarly, the best action will minimise the cost incurred at the current stage and the least total cost that can be incurred from all subsequent stages.