First Look – Drools Planner

Drools Planner is a sub project of the Drools project that started 4 years ago as Drools Solver. Drools Planner is focused on “NP complete” planning problems where a solution is hard to find, but easy to prove feasible once found. Examples include scheduling, bin packing and timetabling for instance. Drools Planner is particularly good at larger ones with lots of constraints, such as a staffing/roster problem where they are many roles and constraints as to who can be scheduled when. Drools Planner has a number of live projects and over 2,000 downloads of the 5.1 release (probably a lot more). It is not currently “productized”, meaning you can use it (under the open source Apache License) but you cannot buy “official” support from Red Hat yet (unlike for Drools BRMS for instance).

Drools Planner, like its competitors, considers both hard and soft constraints (though you can extend the Score interface to add extra levels of constraints). Hard constraints are those that must be met – for example all required shifts must be assigned to someone and no-one is assigned more than one shift per day. Soft constraints are those that can be violated but where violating them reduces the value of a solution. The solver will essentially try and find a solution that violates no hard constraints and minimizes the degree to which soft constraints are violated. Drools Planner is aimed at normal Java programmers who find themselves tasked with solving an optimization problem.

Constraints in Drools Planner are implemented using the Drools Rule Language (DRL) – the conditions of the rule are the constraint itself and the action of the rule is to lower the “score” of the solution. Thus solutions that break more constraints have a lower score. A score contains how many hard and soft constraints are violated. This approach means that the different constraints are clearly isolated and can have a weighted negative or positive impact on the solution’s score. The rule engine also ensures that if something changes during solution generation and a constraint is no longer violated then the score is amended appropriately and efficiently.

Drools Planner’s strength is to handle large solution sets and lots of constraints.  Drools Planner was used in a research contest 3 years ago with over 10^3023 solutions and 14 constraints (http://www.cs.qub.ac.uk/itc2007/) where it placed in the top 5 out of over 200 entries. The limit on the number of constraints it can handle has not yet been determined.

Drools Planner uses POJOs for input data and result data so it is easy to pull/push data from/to services, databases, jBPM etc. Developers can reuse Java methods (such as isHoliday(country, date) for instance) in constraints.

There are a number of interesting side effects of using the Drools rule language and integrating with the Drools rule engine. Using the forward chaining rules engine means that only potentially changed constraints must be re-evaluated: this “delta based score calculation” – rescoring the solution only based on the changed constraints – dramatically improves performance. Also, each performance improvement in the Drools engine usually improves the Planner speed. In addition, using Drools Guvnor, non technical users can be empowered to write constraints (today this is a bit of a hack but it is possible and will get easier). This would allow, for instance, a constraint to be exposed using standard Guvnor features so that business users could change the constraint in defined ways without getting into the code.

The solver itself uses local search algorithms – a search path is built by trying a set of possible changes, the one with the best result is then adopted as a new start point for another set of changes. To avoid getting stuck in local optima the local search engine has “tabus” – it has a solution tabu (won’t go to a solution it has seen before), a move tabu (if it has done something recently it won’t do it again yet) and a property tabu (if it has changed this value recently it won’t change it again soon). Simulated annealing is also supported (this is apparently quite hard to implement correctly). This algorithm initially allows fairly random changes to the solution and as it runs through solutions it gets “pickier” – only allowing better solutions. The randomness helps prevent the solver getting stuck in local optima while the decreasing tolerance of bad results causes it to drive to a solution. Of course you can add your own algorithms too, this being an open source project.

Here are a couple of good presentations on Drools Planner – http://www.slideshare.net/ge0ffrey/pushing-the-rule-engine-to-its-limits-with-drools-planner-parisjug-20101109/12, http://vimeo.com/9204264 and http://www.parleys.com/#id=1714&sl=1&st=5

The official Drools Planner page is here (http://www.jboss.org/drools/drools-planner). Obviously you can download Drools Planner from Jboss ( http://www.jboss.org/drools/downloads). You can get the sources of the examples from the download page or directly from github (https://github.com/droolsjbpm/drools-planner/tree/master/drools-planner-examples/src/main) and the manual at http://downloads.jboss.com/drools/docs/5.1.1.34858.FINAL/drools-planner/html_single/index.html. The next release, 5.2.0, is coming soon.