If you’re a mathematician, operations research professional or computer scientist, you really don’t want to read any further. This is not even close to technical enough for you. But if you’re someone involved in mine planning who wants to understand one of the latest technologies in mine planning, possibly a game-changer, then read on.
The technology that we’re talking about is the Bienstock-Zuckerberg (BZ) algorithm for mine scheduling. You may not have heard of BZ yet, but you probably will before long. It was created by two mathematicians, Daniel Bienstock and Mark Zuckerberg. No, not the Facebook guy — there’s another very bright Mark Zuckerberg.
So why is BZ so important? Well, algorithms to date have really struggled with mine schedule optimization, even using modern high-end computers. Some large problems take longer to solve than people are willing to wait.
BZ drastically improves the solve times for large mine schedule optimization problems. It might even become to mine schedule optimization what LG was to pit optimization.
The main reason mine schedule optimization is so difficult is due to precedences between mining blocks; large numbers of precedences result in long solve times. BZ promises to change all of that.
So what exactly does BZ do? BZ can tell you very quickly what the highest potential value of your mine schedule is. This is what operations research professionals call a bound to the linear programming (LP) problem. The cool thing is that BZ does this in seconds, while a commercial Mixed Integer Linear Programming (MILP) solver could take hours for the same schedule. That’s the game-changer.
It does this in two key steps that iterate until BZ sees that it can’t iterate any more. The first step is doing some clever things to, in a way, aggregate block scheduling decisions through what is called a column generation procedure. A maxflow algorithm called pseudoflow is used in this step. The results of this step are used in the second step of running a very small and fast linear programming (LP) optimization. The results of the LP Optimization are input into the next round of column generation. This continues until BZ knows it has reached the bound.
Are we there yet? Not quite. BZ is almost there when it finds this LP bound. Most of the precedences are satisfied, but a little more work is needed to get all of the precedences right.
This final little bit of work can take a number of forms including
- Using information from BZ’s final LP optimization to guide a very fast heuristic to give a complete schedule. This schedule will be close to optimal, but not guaranteed optimal.
- Use the bound from BZ to speed up a separate MILP solver working with the full blown MILP problem.
- Use what is known as branch and cut to iteratively use BZ to reach an optimal solution.
The first is relatively fast while the second two are much slower but provably optimal.
To date, BZ has been used in mining companies, universities and mining software companies. It can be used for both open-pit and underground settings, and at any planning level from strategic down to short-term. Minemax has been using BZ in its Tempo product for detailed mine planning and is continuing research with applications in this and other areas.
For the brave, and/or lovers of maths, one of the earlier papers is here http://www.columbia.edu/~dano/papers/lpprec.pdf.