## Thursday, April 24, 2008

### Solving the Examination problem part 2: score function

This is the second part in a blog series about drools-solver and the Examination problem. If you haven't done so, read Solving the Examination problem: Domain diagram first.

Each possible solution has a score. Before we try to find the best solution, we need a way to calculate the score of a solution. And that's where the drools rule engine comes into play.

So the current working solution is asserted into the working memory (based on it's getFacts() method) and a number of score rules are fired upon it. Generally, each (hard or soft) constraint translates into a single score rule.

For example, this is the score rule to penalize all exams for which the period duration doesn't suffice.
`// More time required during a period than available in that period.rule "periodDurationTooShort"    when        // Any exam who's duration is longer that it's period duration ...        \$exam : Exam(eval(topicDuration > periodDuration));    then        // ... is penalized hard.        insertLogical(new IntConstraintOccurrence("periodDurationTooShort", ConstraintType.NEGATIVE_HARD,                \$exam.getTopicStudentSize(),                \$exam));end`

Of course, some rules are more complicated, like the score rule to penalize all conflicting exams in a row:
`// Two exams in a row which share studentsrule "twoExamsInARow"    when        // When 2 in row exams are penalized, ...        \$institutionalWeighting : InstitutionalWeighting(twoInARowPenality != 0);        // ..., any 2 exams that share students ...        \$topicConflict : TopicConflict(\$leftTopic : leftTopic, \$rightTopic : rightTopic);        // ... of which the periods ...        \$leftExam : Exam(topic == \$leftTopic, \$leftPeriod : period);        \$rightExam : Exam(topic == \$rightTopic, \$rightPeriod : period);        // ... occur on the same day ...        eval(\$leftPeriod.getDayIndex() == \$rightPeriod.getDayIndex());        // ... and are successive, ...        eval(Math.abs(\$leftPeriod.getPeriodIndex() - \$rightPeriod.getPeriodIndex()) == 1);    then        // ..., are penalized softly.        insertLogical(new IntConstraintOccurrence("twoExamsInARow", ConstraintType.NEGATIVE_SOFT,                \$topicConflict.getStudentSize() * \$institutionalWeighting.getTwoInARowPenality(),                \$leftExam, \$rightExam));end`

Using the drools rule engine to calculate the score has a bunch of advantages:
• The constraint score rules are easier to implement, once you get the hang of the DRL pattern syntax.

• The implementations of the constraints are isolated from each other.
So adding extra constraints is easy and scalable.

• If the working solution changes into an adjacent solution (for example due to a solver move), drools does forward-chaining. This means you get delta based score calculation without any effort. That's a huge performance boost without breaking a sweat.

Now that we know how to calculate the score of solution, we can recognize a good solution. In a next blog we 'll take a look at finding the best solution we can find out of 10^5761 possible solutions. 