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 students
rule "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.

Solving the Examination problem part 1: Domain diagram

The examination problem is one of the examples in drools-solver. It has a number of exams, students, periods and rooms. A student is enrolled into multiple exams. Each exam needs to be scheduled into a period and into a room. Multiple exams can share the same room during the same period.

There are a number of hard constraints that cannot be broken:

• Exam conflict: 2 exams that share students should not occur in the same period.


• Room capacity: A room's seating capacity should suffice at all times.


• Period duration: A period's duration should suffice for all of its exams.


• Period related hard constraints should be fulfilled:
  
  
  
  • Coincidence: 2 exams should use the same period (but possibly another room).
  
  
  • Exclusion: 2 exams should not use the same period.
  
  
  • After: 1 exam should occur in a period after another exam's period.
  
  


• Room related hard constraints should be fulfilled:
  
  
  
  • Exclusive: 1 exam should not have to share its room with any other exam.

There are also a number of soft constraints that should be minimized (each of which has parameterized penalty's):

• 2 exams in a row.


• 2 exams in a day.


• Period spread: 2 exams that share students should have a number of periods between them.


• Mixed durations: 2 exams that share a room should not have different durations.


• Front load: Large exams should be scheduled earlier in the schedule.


• Period penalty: Some periods have a penalty when used.


• Room penalty: Some rooms have a penalty when used.

It uses large test data sets of real-life universities. You can find more information here.

So let's take a look at the domain diagram:



The first dataset has 7883 students, 607 exams, 54 periods and 7 rooms. That makes over 10 to the power 1052 possible solutions. Another dataset even has 10^5761 possible solutions. This means that a brute force algorithm is not an option, unless you can wait over 10^5700 years.

In upcoming blogs, I 'll take a deeper look into the implementation and how to deal which such a massive search space. Continue with the next part of this blog series.