Friday, April 05, 2013

Score DRL: faster and easier in OptaPlanner

For OptaPlanner (= Drools Planner) 6.0.0.Beta1, I 've replaced the ConstraintOccurrence with the much more elegant ConstraintMatch system. The result is that your score DRL files are:
  • much faster
  • easier to read and write
  • far less error-prone, because they make it a lot harder to cause score corruption
Let's look at the results first, before we look at the code readability improvements.

Faster

"Show me the benchmarks!"

The average calculate count - which is the number of scores OptaPlanner calculates per second - has risen dramatically.
  • N queens: +39% calc count for 256 queens
  • Cloud balance: +27% calc count on average
  • Vehicle routing: +40% calc count on average
  • Course scheduling: +20% calc count on average
  • Exam scheduling: +23% calc count on average
  • Nurse rostering: +7% calc count on average

However, this doesn't necessarily imply a dramatic improvement in result, especially if the old result is already (near) optimal. It means you can get the exact same result in far less time. But - as with all other performance improvements - gives no promise for significantly better results in the same time. It does helps when scaling out.
  • Cloud balance: +0.58% feasible soft score on average in 5 minutes
  • Vehicle routing: +0.14% feasible soft score on average in 5 minutes
  • Course scheduling: +2.28% feasible soft score on average in 7 minutes
  • Exam scheduling: +0.53% feasible soft score on average in 7 minutes
Several of the 30 Vehicle routing datasets were already solved optimally in 5 minutes, so these drag the average down, despite the high vehicle routing speedup.

All benchmarks use the exact same Drools and OptaPlanner version, so these numbers show only the improvements of the ConstraintMatch change. There are several other improvements in 6.0.

How does the average calculate count scale?

Here are a some charts comparing the old ConstraintOccurrence with new ConstraintMatch. The new ConstraintMatch's current implementation hasn't been fully optimized, so it's sometimes referred to being in "slow" mode (even though it's faster).

CloudBalance:

Vehicle routing:

Course scheduling:

Exam rostering:


Easier

"Show me the code!"

For starters, the accumulateHardScore and accumulateSoftScore rules are removed. Less boilerplate :) Next, each of the score rule's RHS (= then side) is simpler:

Before:
    rule "conflictingLecturesSameCourseInSamePeriod"
        when
            ...
        then
            insertLogical(new IntConstraintOccurrence("conflictingLecturesSameCourseInSamePeriod", ConstraintType.HARD,
                    -1,
                    $leftLecture, $rightLecture));
    end


After:
    rule "conflictingLecturesSameCourseInSamePeriod"
        when
            ...
        then
            scoreHolder.addHardConstraintMatch(kcontext, -1);
    end


Notice that you don't need to repeat the ruleName or the causes (the lectures) no more. OptaPlanner figures out it itself through the kcontext variable. Drools automatically exposes the kcontext variable in the RHS, so you don't need any extra code for it. Also, the limited ConstraintType enum has been replaced by a Score type specific method, to allow OptaPlanner to better support multilevel score types, for example HardMediumSoftScore and BendableScore.

You also no longer need to hack the API's to get a list of all ConstraintOcurrence's: the ConstraintMatch objects (and their totals per constraint) are available directly on the ScoreDirector API.

No comments:

Post a Comment