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.

Drools solver Javapolis 2007 slides

The BOF was a success and as promised, I 've posted the slides online:

• Javapolis 2007 slides and speaker notes (ODF)
• Javapolis 2007 slides and speaker notes (PDF)

People asked a bunch of interesting questions afterwards.
One question I felt I left a bit unanswered: how do you weigh your constraints in DRL? So, here's a code example that should answer that question too:

rule "twoExamsInARow"
  when
    // ...
  then
    insertLogical(new IntConstraintOccurrence(
        "twoExamsInARow",
        10, // weight
        $leftExam, $rightExam));
end

rule "twoExamsInADay"
  when
    // ...
  then
    insertLogical(new IntConstraintOccurrence(
        "twoExamsInADay",
        1, // weight
        $leftExam, $rightExam));
end

rule "softConstraintsBroken"
  when
    $total : Double() from accumulate(
      IntConstraintOccurrence($weight : weight),
      sum($weight)
    );
  then
    scoreCalculator.setSoftConstraintsBroken($total.intValue());
end

So the 2 in a row constraint is 10 times heavier than the 2 in a day constraint.

Drools solver @ Javapolis

I 'll hold a Drools Solver BOF at Javapolis 2007 on Tuesday December 11th at 20:00. You're all invited :)
Take a look at the schedule here.
Take a look the contents of the BOF here.

The drools solver manual has also been expanded with more info about the examples:
Take a look at the updated manual here.

The manual now contains some insight about the problem size of the examples. Did you know that the traveling tournament example nl16 finds a feasible solution out of 2,45064610271441678267620602e+259 possible solutions?

And of course I 've added some more eye candy:

Drools solver in a nutshell

Drools-solver combines a search algorithm with the power of the drools rule engine to solve planning problems, such as:

• Employee shift rostering

• Freight routing

• Supply sorting

• Lesson scheduling

• Exam scheduling

• The traveling salesmen problem

• The traveling tournament problem

Drools-solver supports several search algorithms, such as simple local search, tabu search and simulated annealing. You can easily switch the search algorithm, by simply changing the configuration. There's even a benchmark utility which allows you to play out the different search algorithms against each other on your planning problem.

Drools-solver uses the drools rule engine to calculate the score, based on score rules. This allows you to easily add hard and soft constraints in your score function, simply by adding a score rule.

It's available now in the drools trunk and the manual explains how to run the examples yourself in no time.

Drools Solver

Geoffrey De Smet has been busy working on the Drools Solver module, which will hopefully be part of the next major Drools release. Drools solver aims to efficiently solve search based problems finding a valid solution from large search areas. It currently provides implementations for Tabu, simulated annealing and Local search. I personally hope to expand the system for Genetic Algorithms in the future, I'll have a good look at jgap too see if we can provide true value over existing systems.

Geoffrey has started to flesh out the manual and is looking for feedback, it focuses on explaining the engine via solving the N-Queens problems.

Drools Solver Manual

Drools Solver provides a framework for searching and uses Drools to provide the scoring, moves themselves are still done in Java code. I know that Geoffrey long term is hoping to have the move instructions also as part of the DRL.

Local search 101 (Geoffrey De Smet)

I am working on a local search implementation on top of Drools.
My proof of concept is already able to tackle planning problems such as:

• NQueens
• A simplified lesson schedule with teachers, groups, lessons and timeslots.
  
• Traveling Tournament Problem (TTP) (only breaking old records at the moment though)
  

Local search and Drools turns out to be a really nice combination because:

• A rule engine such as Drools is great for calculating the score of a solution of a planning problem. They make it easy to add additional soft or hard constraints such as "a teacher shouldn't teach more then 7 hours a day". However it tends to be too complex to use to actually find new solutions.
• Local search is great at finding new solutions for a planning problem, without brute-forcing every possibility. However it needs to know the score of a solution and offers no support in calculating that score.

So combining the two, I created Taseree, which will probably be accepted as Drools Solver (Local Search) once it's no longer just a proof of concept. But there's a bunch of work to be done meanwhile though.
You can find it at SourceForge for now, under the same license as Drools. As far as I know I am the first one to think of making a hybrid of local search and a rule engine.

I 'll attempt to open the black box a bit, to get some feed-back on my implementation.

I 'll start with explaining some terms used in the current implementation:

• Solution: A state of the problem which can be evaluated into a score. The solver will try to find a solution with the highest score it can find. The initial solution's facts are asserted into the Drools WorkingMemory.
  
• Score: Calculated on a solution. Higher is better. Many planning problems tend to use negative scores (the amount of constraints being broken) with an impossible perfect score of 0.
• Move: A migration path from a solution A to a solution B. Some moves are small (move the French lesson to an hour earlier), others are large (switch all lessons on monday with those on friday). Each move has an undo move: a move from solution B back to solution A. A move notifies the Drools WorkingMemory of its changes.
  
• Local search: A solver that starts from an initial solution and takes steps to evolve it. It remembers the best solution it comes across.
  
• Step: The decided move. Every step taken by a local search solver is picked by the decider from a number of possible moves.
• Decider: Decides which move is the next step. A decider uses a selector to find moves, a score calculator to calculate the score of each selected move and an accepter to decide whether or not to accept the move as the next step.
• Selector: Figures out which moves can be made on the current solution.
• Accepter: Accepts or rejects a move. Implementations can turn the local search into tabu search, simulated annealing, great deluge, ...
• Tabu search: A specific local search which does not accept moves which evolve the solution into an already encountered solution. Most of the examples use tabu search.
  
• Score calculator: Calculates the score for a given solution. It uses the Drools WorkingMemory.
  
• Finish: Decides when it's time to give up in trying new steps to find a better solution. Implementations can check time, number of steps, feasibility of best score, ... A local search never knows that it found the perfect solution, so a finish needs to be set. However even small planning problems tend to be so complicated to solve that trying every combination (even with pruning) takes too long (TTP level 10 is a great example of that).
  

Now, let's take a look at some pseudo code for the local search algoritm combined with a rule engine:

workingMemory.assert(solution.getFacts());
// continue searching until our time is up
while (!finish.isFinished()) {
  Move step = decider.decideNextStep() {
    for (Move move : selector) {
      doMove(workingMemory);
      scoreCalculator.calculateScore(workingMemory);
      if (accepter.calculateAcceptChance() is accepted) {
        return move;
      }
      undoMove(workingMemory);
    }
  }
  doStep(workingMemory);
  if (stepScore > bestScore) {
    // remember bestSolution and bestScore
  }
}