JBoss.org Community Documentation

- Prev
- Next

## Chapter 4. Score calculation with a rule engine

## 4.1. Rule based score calculation

The score calculation (or fitness function) of a planning problem is based on constraints (such as hard constraints, soft constraints, rewards, ...). A rule engine, such as Drools Expert, makes it easy to implement those constraints as score rules.

Adding more constraints is easy and scalable (once you understand the DRL syntax). This allows you to add a bunch of soft constraint score rules on top of the hard constraints score rules with little effort and at a reasonable performance cost. For example, for a freight routing problem you could add a soft constraint to avoid the certain flagged highways during rush hour.

## 4.2. Choosing a Score implementation

### 4.2.1. The ScoreDefinition interface

The `ScoreDefinition` interface defines the score representation. The score must be a `Score` instance and the instance type (for example `DefaultHardAndSoftScore`) must be stable throughout the solver runtime.

The solver aims to find the solution with the highest score. The best solution is the solution with the highest score that it has encountered during its solving.

## Note

Most planning problems use negative scores, because they use negative constraints. The score is usually the sum of the weight of the negative constraints being broken, with an impossible perfect score of 0. This explains why the score of a solution of 4 queens is the negative of the number of queen couples which can attack each other.

Configure a `ScoreDefinition` in the solver configuration. You can implement a custom `ScoreDefinition`, although the build-in score definitions should suffice for most needs:

### 4.2.2. SimpleScore

The `SimpleScoreDefinition` defines the `Score` as a `SimpleScore` which has a single int value, for example `-123`.

        <scoreDefinition>

            <scoreDefinitionType>SIMPLE</scoreDefinitionType>

        </scoreDefinition>

### 4.2.3. HardAndSoftScore

The `HardAndSoftScoreDefinition` defines the `Score` as a `HardAndSoftScore` which has a hard int value and a soft int value, for example `-123hard/-456soft`.

        <scoreDefinition>

            <scoreDefinitionType>HARD_AND_SOFT</scoreDefinitionType>

        </scoreDefinition>

### 4.2.4. Implementing a custom Score

To implement a custom Score, you 'll also need to implement a custom `ScoreDefinition`. Extend `AbstractScoreDefinition` (preferable by copy pasting `HardAndSoftScoreDefinition` or `SimpleScoreDefinition`) and start from there.

Then hook you custom `ScoreDefinition` in your `SolverConfig.xml`:

        <scoreDefinition>

            <scoreDefinitionClass>org.drools.planner.examples.my.score.definition.MyScoreDefinition</scoreDefinitionClass>

        </scoreDefinition>

## 4.3. Defining the score rules source

There are 2 ways to define where your score rules live.

### 4.3.1. A scoreDrl resource on the classpath

This is the simplest way: the score rule live in a DRL file which is a resource on the classpath. Just add your score rules `*.drl` file in the solver configuration, for example:

        <scoreDrl>/org/drools/planner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>

You can add multiple `<scoreDrl>` entries if needed, but normally you 'll define all your score rules in 1 file.

### 4.3.2. A RuleBase (possibly defined by Guvnor)

If you prefer to build the `RuleBase` yourself or if you're combining Planner with Guvnor, you can set the `RuleBase` on the `XmlSolverConfigurer` before building the `Solver`:

        xmlSolverConfigurer.getSolverConfig().setRuleBase(ruleBase);

## 4.4. Implementing a score rule

The score calculation of a planning problem is based on constraints (such as hard constraints, soft constraints, rewards, ...). A rule engine, such as Drools, makes it easy to implement those constraints as score rules.

Here's an example of a constraint implemented as a score rule in such a DRL file:

    rule "multipleQueensHorizontal"
        when
            $q1 : Queen($id : id, $y : y);
            $q2 : Queen(id > $id, y == $y);
        then
            insertLogical(new UnweightedConstraintOccurrence("multipleQueensHorizontal", $q1, $q2));
    end

This score rule will fire once for every 2 queens with the same `y`. The `(id > $id)` condition is needed to assure that for 2 queens A and B, it can only fire for (A, B) and not for (B, A), (A, A) or (B, B). Let's take a closer look at this score rule on this solution of 4 queens:

In this solution the multipleQueensHorizontal score rule will fire for 6 queen couples: (A, B), (A, C), (A, D), (B, C), (B, D) and (C, D). Because none of the queens are on the same vertical or diagonal line, this solution will have a score of `-6`. An optimal solution of 4 queens has a score of `0`.

## Note

Notice that every score rule will relate to at least 1 planning entity class (directly or indirectly though a logically inserted fact).

This is normal: it would be a waste of time to write a score rule that only relates to problem facts, as the consequence will never change during planning, no matter what the possible solution.

## 4.5. Aggregating the score rules into the `Score`

A `ScoreCalculator` instance is asserted into the `WorkingMemory` as a global called `scoreCalculator`. Your score rules need to (direclty or indirectly) update that instance. Usually you 'll make a single rule as an aggregation of the other rules to update the score:

    global SimpleScoreCalculator scoreCalculator;

    rule "multipleQueensHorizontal"
        when
            $q1 : Queen($id : id, $y : y);
            $q2 : Queen(id > $id, y == $y);
        then
            insertLogical(new UnweightedConstraintOccurrence("multipleQueensHorizontal", $q1, $q2));
    end

    // multipleQueensVertical is obsolete because it is always 0

    rule "multipleQueensAscendingDiagonal"
        when
            $q1 : Queen($id : id, $ascendingD : ascendingD);
            $q2 : Queen(id > $id, ascendingD == $ascendingD);
        then
            insertLogical(new UnweightedConstraintOccurrence("multipleQueensAscendingDiagonal", $q1, $q2));
    end

    rule "multipleQueensDescendingDiagonal"
        when
            $q1 : Queen($id : id, $descendingD : descendingD);
            $q2 : Queen(id > $id, descendingD == $descendingD);
        then
            insertLogical(new UnweightedConstraintOccurrence("multipleQueensDescendingDiagonal", $q1, $q2));
    end

    rule "hardConstraintsBroken"
        when
            $occurrenceCount : Number() from accumulate(
                $unweightedConstraintOccurrence : UnweightedConstraintOccurrence(),
                count($unweightedConstraintOccurrence)
            );
        then
            scoreCalculator.setScore(- $occurrenceCount.intValue());
    end

Most use cases will also weigh their constraints differently, by multiplying the count of each score rule with its weight. For example in freight routing, you can make 5 broken "avoid crossroads" soft constraints count as much as 1 broken "avoid highways at rush hour" soft constraint. This allows your business analysts to easily tweak the score function as they see fit.

Here's an example from CurriculumCourse, where assiging a `Lecture` to a `Room` which is missing 2 seats is weighted equally bad as having 1 isolated `Lecture` in a `Curriculum`:

    // RoomCapacity: For each lecture, the number of students that attend the course must be less or equal
    // than the number of seats of all the rooms that host its lectures.
    // Each student above the capacity counts as 1 point of penalty.
    rule "roomCapacity"
        when
            ...
        then
            insertLogical(new IntConstraintOccurrence("roomCapacity", ConstraintType.NEGATIVE_SOFT,
                    ($studentSize - $capacity),
                    ...));
    end

    // CurriculumCompactness: Lectures belonging to a curriculum should be adjacent
    // to each other (i.e., in consecutive periods).
    // For a given curriculum we account for a violation every time there is one lecture not adjacent
    // to any other lecture within the same day.
    // Each isolated lecture in a curriculum counts as 2 points of penalty.
    rule "curriculumCompactness"
        when
            ...
        then
            insertLogical(new IntConstraintOccurrence("curriculumCompactness", ConstraintType.NEGATIVE_SOFT,
                    2,
                    ...));
    end

    // Accumulate soft constraints
    rule "softConstraintsBroken"
            salience -1 // Do the other rules first (optional, for performance)
        when
            $softTotal : Number() from accumulate(
                IntConstraintOccurrence(constraintType == ConstraintType.NEGATIVE_SOFT, $weight : weight),
                sum($weight)
            )
        then
            scoreCalculator.setSoftConstraintsBroken($softTotal.intValue());
    end

## 4.6. Delta based score calculation

It's recommended to use Drools in forward-chaining mode (which is the default behaviour), because this will create the effect of a delta based score calculation, instead of a full score calculation on each solution evaluation. For example, if a single queen A moves from y `0` to `3`, it won't bother to recalculate the "multiple queens on the same horizontal line" constraint between 2 queens if neither of those involved queens is queen A.

This is a huge performance and scalibility gain. Drools Planner gives you this huge scalibility gain without forcing you to write a very complicated delta based score calculation algorithm. Just let the Drools rule engine do the hard work.

Figure 4.1. Delta based score calculation for the 4 queens puzzle

The speedup due to delta based score calculation is huge, because the speedup is relative to the size of your planning problem (your n). By using score rules, you get that speedup without writing any delta code.

## 4.7. Tips and tricks

- If you know a certain constraint can never be broken, don't bother writing a score rule for it. For example in n queens, there is no "multipleQueensVertical" rule because a `Queen`'s `column` never changes and each `Solution` build puts each `Queen` on a different `column`. This tends to give a huge performance gain, not just because the score function is faster, but mainly because most `Solver` implementations will spend less time evaluating unfeasible solutions.

- Be watchfull for score traps. A score trap is a state in which several moves need to be done to resolve or lower the weight of a single constraint occurrence. Some examples of score traps:

  - If you need 2 doctors at each table, but you're only moving 1 doctor at a time, then the solver has no insentive to move a doctor to a table with no doctors. Punish a table with no doctors more then a table with only 1 doctor in your score function.

  - If you only add the table as a cause of the ConstraintOccurrence and forget the jobType (which is doctor or politician), then the solver has no insentive to move a docter to table which is short of a doctor and a politician.

- If you use tabu search, combine it with a `minimalAcceptedSelection` selector. Take some time to tweak the value of `minimalAcceptedSelection`.

- Verify that your score calculation happens in the correct `Number` type. If you're making the sum of integer values, don't let drools use Double's or your performance will hurt. The `Solver` will usually spend most of its execution time running the score function.

- Always remember that premature optimization is the root of all evil. Make sure your design is flexible enough to allow configuration based tweaking.

- Currently, don't allow drools to backward chain instead of forward chain, so avoid query's. It kills delta based score calculation (so it kills scalibility).

- Currently, don't allow drools to switch to MVEL mode, for performance.

- For optimal performance, use at least java 1.6 and always use server mode (`java -server`). We have seen performance increases of 30% by switching from java 1.5 to 1.6 and 50% by turning on server mode.

- If you're doing performance tests, always remember that the JVM needs to warm up. First load your `Solver` and do a short run, before you start benchmarking it.

In case you haven't figured it out yet: performance (and scalability) is very important for solving planning problems well. What good is a real-time freight routing solver that takes a day to find a feasible solution? Even small and innocent looking problems can hide an enormous problem size. For example, they probably still don't know the optimal solution of the traveling tournament problem for as little as 12 traveling teams.

- PrevChapter 3. Planner configuration
- Top of page
- Front page
- NextChapter 5. Optimization algorithms