As we shared in an earlier article, the Bienstock-Zuckerberg algorithm, or BZ, could be a game-changing technology for mine planning. It has the potential to drastically speed up mine schedule optimization solutions. Speed in mine scheduling is important. If miners can create optimal schedules for alternative business scenarios faster, they can analyze more scenarios and thus respond more effectively to business opportunities and threats. So how fast is BZ really?
Well, we clocked our own implementation of BZ to see just how fast it was and compared it to its counterpart, the Simplex algorithm. A form of Simplex is used in most commercial MILP solvers. We used IBM’s CPLEX version. The chosen racetrack was a dataset from the Minelib library of mine planning problems. The particular dataset was the PCPSP option for KD, a copper deposit in Arizona, USA. PCPSP (Precedence Constrained Production Scheduling Problem) is a format where destinations are not pre-determined for blocks, but are part of the solution. Now we knew beforehand that this would be a tough problem for Simplex, but we really didn’t know how tough.
The Bugatti Veyron Super Sport has the Guinness World Record as the fastest production car at 431 km/hr or 267 mph. We wondered: if BZ were the Bugatti Veyron Super Sport, where would Simplex line up?
Pop quiz. What do you think?
- A Ford Mustang (252km/hr)?
- A Renault Twizy (80 km/hr)?
- A Three-Toed Sloth (0.24 km/hr)?
Back to our experiment, both algorithms gave the same relaxed LP objective value for KD of 410,891,003. This also corresponds to the value given on the Minelib site for KD. Running BZ took a grand total of 20 seconds. On the same hardware, running CPLEX with parallel optimization using 8 threads took 90,105 seconds. That is 25 hours, 1 minute and 45 seconds. A factor of more than 4500!
So if BZ were the Bugatti Veyron at a speed of 431 km/hr, then Simplex would have a speed of 0.096 km/hr for this dataset. Slower than the sloth.
We are very excited with the disruption BZ is bringing to mine planning through its lightning-fast speed.