Drools Planner 5.3.0.Beta1 will include out-of-the-box construction heuristics. Before running metaheuristics (such as tabu search) on a use case, it’s important to first run a construction heuristic on it, as that greatly improves the score. These construction heuristics are already implemented for Beta1:
- First Fit
- First Fit Decreasing
- Best Fit
- Best Fit Decreasing
They are drop-in replacements for your custom StartingSolutionInitializer implementation, which – if you copied the examples – were First Fit Decreasing implementations. Such a StartingSolutionInitializer is pretty difficult to write, pretty long and can easily contain invisible bugs. Now, it’s far easier: just configure a construction heuristic instead:
<solver>
...
<constructionheuristic>
<constructionheuristicType>FIRST_FIT</constructionheuristicType>
</constructionheuristic>
<localSearch>
...
</localSearch>
</solver>
That’s a lot less code, isn’t it? Some construction heuristics (such as FIRST_FIT_DECREASING) do require you to implement a simple difficulty Comparator (more info in the manual).
If you’re keen on your custom StartingSolutionInitializer ‘s boilerplate code, you can still use that too of course. Although it probably doesn’t support these features that the construction heuristics implementations do:
- Immediate termination
- Start with a partially initialized solution (needed for real-time planning)
So which construction heuristic is better?
Well, let’s use the Benchmarker to find out. Below are some benchmarks on different examples. Note that construction heuristics should be suffixed with metaheuristics (such as tabu search): these scores are just the starting scores for the more advanced optimization algorithms (metaheuristics), they are not the final scores for these use cases.
PatientAdmissionSchedule (hospital bed planning)
Notice that the Best Fit Decreasing (purple) is better than my original StartingSolutionInitializer (red) for at least 2000soft on these 3 datasets. The latter took me a lot longer to implement, yet it’s worse. In some cases, tabu search takes over 10 minutes to compensate for that difference in starting score! I ‘ll talk about that, the importance of phasing, in a later blog.
Nurse rostering
In this use case, First Fit and Best Fit win, but it’s not significantly better than the StartingSolutionInitializer. In fact, the StartingSolutionInitializer behaves exactly like First Fit Decreasing. The Decreasing variants are university worse than the non-decreasing variants. That’s big, fat indication that I should take a look at my difficulty Comparator implementation (which is used by the Decreasing variants an my original StartingSolutionInitializer): it’s probably wrong.
So how long does it take to run these constructions heuristics? Not long, just a few seconds:
CloudBalance
In this case, First Fit and Best Fit don’t have a feasible solution for the 3th dataset. First Fit Decreasing wins.
Overall, First Fit Decreasing is better, even though Best Fit and Best Fit Decreasing take a few milliseconds longer:
Summary
Using a good construction heuristic is a vital part of getting the better solutions for planning problems. It gives the metaheuristics a head start.
