Friday, February 22, 2008

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.

9 comments:

  1. Hi Geoffrey, will Drools-Solver be an official part of Drools 5?

    Best regards, Martin.

    ReplyDelete
  2. There are currently no plans to officially support drools-solver at the moment. We are waiting to see how it matures and for market adoption to occur.

    ReplyDelete
  3. I just did a big refactor which will makes it easier to write isolated unit tests on specific parts of the algoritms. Once more of those unit tests are in place, we're thinking about releasing the first alfa of drools-solver.

    ReplyDelete
  4. That's very good news. I believe having a module such as solver available will be good PR for the whole drools project because of the added AI-shininess that will appeal even to the uninitiated.

    Are you aiming for continued drools 4.0.6 compliance, or will you be requiring 5.0 features?

    ReplyDelete
  5. I am not using any 5.0 features yet, but if anything interesting appears, such as accumulate sum(Integer), I 'll probably use it.
    However, that's isolated in the examples's score DRL's, so drools-solver-core will probably still run with drools 4.0.2+ just fine.

    ReplyDelete
  6. Hi Geoffrey,
    I am trying to use Solver 5M1 with Drools 4.0.7. in a Seam environment. However, I am getting a ClassCastException: org.drools.rule.builder.dialect.mvel.MVELDialectConfiguration cannot be cast to org.drools.compiler.DialectConfiguration
    at org.drools.compiler.PackageBuilderConfiguration.addDialect(PackageBuilderConfiguration.java:155)

    When invoking buildSolver() on a XmlSolverConfigurer
    Am I doing something wrong, or is it simply impossible to use these versions together?
    Thanks in advance, Martin

    ReplyDelete
  7. If you're not using maven: you're ending up with at least the wrong mvel jar version... read which jars need which jars and fix all that manually.

    If you are: It's probably a maven dependency conflict and you're ending up with the wrong mvel jar version.

    Things you can do:
    1) Use maven 2.0.9. If both mvel jars use the same groupId, starting from maven 2.0.9, the highest version should win IIRC.
    2) Explicitly depend on the correct mvel jar version in your pom.xml. The correct mvel jar version is the one the drools-parent pom.xml uses. see http://repository.jboss.org
    3) Use high quality seam pom.xml that mark drools correctly as an optional dependency.
    4) In the seam dependency, use exclusion> for the drools stuff. Use drools as a direct dependency.

    PS: note that drools-solver 5.0.0.m2 is borked. So use either m1 or trunk (or m3 which will hopefully be released soon).

    ReplyDelete
  8. By the way: What kind of problem are you using drools-solver for? I am interested in the diversity of the use cases people use it for.

    ReplyDelete
  9. Thanks!
    I want to use Solver for routeplanning.
    Cheers, Martin

    ReplyDelete