5.3. Calculate the Score

5.3.1. Score Calculation Types

There are several ways to calculate the Score of a Solution:
  • Easy Java score calculation: implement a single Java method
  • Incremental Java score calculation: implement multiple Java methods
  • Drools score calculation (recommended): implement score rules
Every score calculation type can use any Score definition. For example, easy Java score calculation can output a HardSoftScore.
All score calculation types are Object Oriented and can reuse existing Java code.
Important
The score calculation should be read-only: it should not change the planning entities or the problem facts in any way. For example, it must not call a setter method on a planning entity in a Drools score rule's RHS. This does not apply to logically inserted objects, which can be changed by the score rules that logically inserted them in the first place.
Planner will not recalculate the score of a Solution if it can predict it (unless an environmentMode assertion is enabled). For example, after a winning step is done, there is no need to calculate the score because that move was done and undone earlier. As a result, there's no guarantee that such changes applied during score calculation are actually done.

5.3.2. Easy Java Score Calculation

An easy way to implement your score calculation in Java.
  • Advantages:
    • Plain old Java: no learning curve
    • Opportunity to delegate score calculation to an existing code base or legacy system
  • Disadvantages:
Just implement one method of the interface EasyScoreCalculator: 
public interface EasyScoreCalculator<Sol extends Solution> {

    Score calculateScore(Sol solution);
   
}
For example in n queens: 
public class NQueensEasyScoreCalculator implements EasyScoreCalculator<NQueens> {

    public SimpleScore calculateScore(NQueens nQueens) {
        int n = nQueens.getN();
        List<Queen> queenList = nQueens.getQueenList();
        
        int score = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                Queen leftQueen = queenList.get(i);
                Queen rightQueen = queenList.get(j);
                if (leftQueen.getRow() != null && rightQueen.getRow() != null) {
                    if (leftQueen.getRowIndex() == rightQueen.getRowIndex()) {
                        score--;
                    }
                    if (leftQueen.getAscendingDiagonalIndex() == rightQueen.getAscendingDiagonalIndex()) {
                        score--;
                    }
                    if (leftQueen.getDescendingDiagonalIndex() == rightQueen.getDescendingDiagonalIndex()) {
                        score--;
                    }
                }
            }
        }
        return SimpleScore.valueOf(score);
    }

}
Configure it in your solver configuration: 
  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <easyScoreCalculatorClass>org.optaplanner.examples.nqueens.solver.score.NQueensEasyScoreCalculator</easyScoreCalculatorClass>
  </scoreDirectorFactory>
Alternatively, build a EasyScoreCalculator instance at runtime and set it with the programmatic API: 
    solverFactory.getSolverConfig().getScoreDirectorFactoryConfig.setEasyScoreCalculator(easyScoreCalculator);

5.3.3. Incremental Java Score Calculation

A way to implement your score calculation incrementally in Java.
  • Advantages:
    • Very fast and scalable
      • Currently the fastest if implemented correctly
  • Disadvantages:
    • Hard to write
      • A scalable implementation heavily uses maps, indexes, ... (things the Drools rule engine can do for you)
      • You have to learn, design, write and improve all these performance optimizations yourself
    • Hard to read
      • Regular score constraint changes can lead to a high maintenance cost
Implement all the methods of the interface IncrementalScoreCalculator and extend the class AbstractIncrementalScoreCalculator: 
public interface IncrementalScoreCalculator<Sol extends Solution> {

    void resetWorkingSolution(Sol workingSolution);

    void beforeEntityAdded(Object entity);

    void afterEntityAdded(Object entity);

    void beforeVariableChanged(Object entity, String variableName);

    void afterVariableChanged(Object entity, String variableName);

    void beforeEntityRemoved(Object entity);

    void afterEntityRemoved(Object entity);

    Score calculateScore();
    
}
For example in n queens: 
public class NQueensAdvancedIncrementalScoreCalculator extends AbstractIncrementalScoreCalculator<NQueens> {

    private Map<Integer, List<Queen>> rowIndexMap;
    private Map<Integer, List<Queen>> ascendingDiagonalIndexMap;
    private Map<Integer, List<Queen>> descendingDiagonalIndexMap;

    private int score;

    public void resetWorkingSolution(NQueens nQueens) {
        int n = nQueens.getN();
        rowIndexMap = new HashMap<Integer, List<Queen>>(n);
        ascendingDiagonalIndexMap = new HashMap<Integer, List<Queen>>(n * 2);
        descendingDiagonalIndexMap = new HashMap<Integer, List<Queen>>(n * 2);
        for (int i = 0; i < n; i++) {
            rowIndexMap.put(i, new ArrayList<Queen>(n));
            ascendingDiagonalIndexMap.put(i, new ArrayList<Queen>(n));
            descendingDiagonalIndexMap.put(i, new ArrayList<Queen>(n));
            if (i != 0) {
                ascendingDiagonalIndexMap.put(n - 1 + i, new ArrayList<Queen>(n));
                descendingDiagonalIndexMap.put((-i), new ArrayList<Queen>(n));
            }
        }
        score = 0;
        for (Queen queen : nQueens.getQueenList()) {
            insert(queen);
        }
    }

    public void beforeEntityAdded(Object entity) {
        // Do nothing
    }

    public void afterEntityAdded(Object entity) {
        insert((Queen) entity);
    }

    public void beforeVariableChanged(Object entity, String variableName) {
        retract((Queen) entity);
    }

    public void afterVariableChanged(Object entity, String variableName) {
        insert((Queen) entity);
    }

    public void beforeEntityRemoved(Object entity) {
        retract((Queen) entity);
    }

    public void afterEntityRemoved(Object entity) {
        // Do nothing
    }

    private void insert(Queen queen) {
        Row row = queen.getRow();
        if (row != null) {
            int rowIndex = queen.getRowIndex();
            List<Queen> rowIndexList = rowIndexMap.get(rowIndex);
            score -= rowIndexList.size();
            rowIndexList.add(queen);
            List<Queen> ascendingDiagonalIndexList = ascendingDiagonalIndexMap.get(queen.getAscendingDiagonalIndex());
            score -= ascendingDiagonalIndexList.size();
            ascendingDiagonalIndexList.add(queen);
            List<Queen> descendingDiagonalIndexList = descendingDiagonalIndexMap.get(queen.getDescendingDiagonalIndex());
            score -= descendingDiagonalIndexList.size();
            descendingDiagonalIndexList.add(queen);
        }
    }

    private void retract(Queen queen) {
        Row row = queen.getRow();
        if (row != null) {
            List<Queen> rowIndexList = rowIndexMap.get(queen.getRowIndex());
            rowIndexList.remove(queen);
            score += rowIndexList.size();
            List<Queen> ascendingDiagonalIndexList = ascendingDiagonalIndexMap.get(queen.getAscendingDiagonalIndex());
            ascendingDiagonalIndexList.remove(queen);
            score += ascendingDiagonalIndexList.size();
            List<Queen> descendingDiagonalIndexList = descendingDiagonalIndexMap.get(queen.getDescendingDiagonalIndex());
            descendingDiagonalIndexList.remove(queen);
            score += descendingDiagonalIndexList.size();
        }
    }

    public SimpleScore calculateScore() {
        return SimpleScore.valueOf(score);
    }

}
Configure it in your solver configuration: 
  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <incrementalScoreCalculatorClass>org.optaplanner.examples.nqueens.solver.score.NQueensAdvancedIncrementalScoreCalculator</incrementalScoreCalculatorClass>
  </scoreDirectorFactory>
Optionally, to explain a score with ScoreDirector.getConstraintMatchTotals() or to get better output when the IncrementalScoreCalculator is corrupted in FAST_ASSERT or FULL_ASSERT environmentMode, implement also the ConstraintMatchAwareIncrementalScoreCalculator interface: 
public interface ConstraintMatchAwareIncrementalScoreCalculator<Sol extends Solution> {

    void resetWorkingSolution(Sol workingSolution, boolean constraintMatchEnabled);

    Collection<ConstraintMatchTotal> getConstraintMatchTotals();
    
}

5.3.4. Drools Score Calculation

5.3.4.1. Overview

Implement your score calculation using the Drools rule engine. Every score constraint is written as one or more score rules.
  • Advantages:
    • Incremental score calculation for free
      • Because most DRL syntax uses forward chaining, it does incremental calculation without any extra code
    • Score constraints are isolated as separate rules
      • Easy to add or edit existing score rules
    • Flexibility to augment your score constraints by
      • Defining them in decision tables
        • Excel (XLS) spreadsheet
        • KIE Workbench WebUI
      • Translate them into natural language with DSL
      • Store and release in the KIE Workbench repository
    • Performance optimizations in future versions for free
      • In every release, the Drools rule engine tends to become faster
  • Disadvantages:
    • DRL learning curve
    • Usage of DRL
      • Polyglot fear can prohibit the use of a new language such as DRL in some organizations

5.3.4.2. Drools Score Rules Configuration

There are several ways to define where your score rules live.
5.3.4.2.1. A scoreDrl Resource on the Classpath
This is the easy way: the score rule live in a DRL file which is provided as a classpath resource. Just add the score rules DRL file in the solver configuration as a <scoreDrl> element: 
  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
  </scoreDirectorFactory>
In a typical project (following the Maven directory structure), that DRL file would be located at $PROJECT_DIR/src/main/resources/org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl (even for a war project).
Note
The <scoreDrl> element expects a classpath resource, as defined by ClassLoader.getResource(String), it does not accept a File, nor an URL, nor a webapp resource. See below to use a File instead.
Add multiple <scoreDrl> elements if the score rules are split across multiple DRL files.
Optionally, you can also set drools configuration properties (but be careful of backwards compatibility issues): 
  <scoreDirectorFactory>
    ...
    <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
    <kieBaseConfigurationProperties>
      <drools.equalityBehavior>...</drools.equalityBehavior>
    </kieBaseConfigurationProperties>
  </scoreDirectorFactory>
5.3.4.2.2. A scoreDrlFile
To use File on the local file system, instead of a classpath resource, add the score rules DRL file in the solver configuration as a <scoreDrlFile> element: 
  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <scoreDrlFile>/home/ge0ffrey/tmp/nQueensScoreRules.drl</scoreDrlFile>
  </scoreDirectorFactory>
Warning
For portability reasons, a classpath resource is recommended over a File. An application build on one computer, but used on another computer, might not find the file on the same location. Worse, if they use a different Operating System, it's hard to choose a portable file path.
Add multiple <scoreDrlFile> elements if the score rules are split across multiple DRL files.
5.3.4.2.3. A KieBase (Possibly Defined by Drools Workbench)
To build the KieBase yourself or to combine Planner with KIE Workbench (formerly known as Guvnor), set the KieBase on the SolverFactory before building the Solver: 
    solverFactory.getSolverConfig().getScoreDirectorFactoryConfig.setKieBase(kieBase);
Note
To be able to define your score rules in Drools Workbench, you'll want to:
  1. Upload the optaplanner-core jar as a POJO model.
  2. Add a global variable called scoreHolder (see below).

5.3.4.3. Implementing a Score Rule

Here's an example of a score constraint implemented as a score rule in a DRL file: 
rule "multipleQueensHorizontal"
    when
        Queen($id : id, row != null, $i : rowIndex)
        Queen(id > $id, rowIndex == $i)
    then
        scoreHolder.addConstraintMatch(kcontext, -1);
end
This score rule will fire once for every 2 queens with the same rowIndex. 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 through 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.
Note
The kcontext variable is a magic variable in Drools Expert. The scoreHolder's method uses it to do incremental score calculation correctly and to create a ConstraintMatch instance.

5.3.4.4. Weighing Score Rules

A ScoreHolder instance is asserted into the KieSession as a global called scoreHolder. Your score rules need to (directly or indirectly) update that instance. 
global SimpleScoreHolder scoreHolder;

rule "multipleQueensHorizontal"
    when
        Queen($id : id, row != null, $i : rowIndex)
        Queen(id > $id, rowIndex == $i)
    then
        scoreHolder.addConstraintMatch(kcontext, -1);
end

// multipleQueensVertical is obsolete because it is always 0

rule "multipleQueensAscendingDiagonal"
    when
        Queen($id : id, row != null, $i : ascendingDiagonalIndex)
        Queen(id > $id, ascendingDiagonalIndex == $i)
    then
        scoreHolder.addConstraintMatch(kcontext, -1);
end

rule "multipleQueensDescendingDiagonal"
    when
        Queen($id : id, row != null, $i : descendingDiagonalIndex)
        Queen(id > $id, descendingDiagonalIndex == $i)
    then
        scoreHolder.addConstraintMatch(kcontext, -1);
end
Most use cases will also weigh their constraint types or even their matches differently, by using a specific weight for each constraint match.
Here's an example from CurriculumCourse, where assigning a Lecture to a Room which is missing 2 seats is weighted equally bad as having 1 isolated Lecture in a Curriculum: 
global HardSoftScoreHolder scoreHolder;

// 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
        $room : Room($capacity : capacity)
        $lecture : Lecture(room == $room, studentSize > $capacity, $studentSize : studentSize)
    then
        scoreHolder.addSoftConstraintMatch(kcontext, ($capacity - $studentSize));
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
        scoreHolder.addSoftConstraintMatch(kcontext, -2);
end

5.3.5. InitializingScoreTrend

The InitializingScoreTrend specifies how the Score will change as more and more variables are initialized (while the already initialized variables don't change). Some optimization algorithms (such Construction Heuristics and Exhaustive Search) run faster if they have such information.
For for the Score (or each score level separately), specify a trend:
  • ANY (default): Initializing an extra variable can change the score positively or negatively. Gives no performance gain.
  • ONLY_UP (rare): Initializing an extra variable can only change the score positively. Implies that:
    • There are only positive constraints
    • And initializing the next variable can not unmatch a positive constraint that was matched by a previous initialized variable.
  • ONLY_DOWN: Initializing an extra variable can only change the score negatively. Implies that:
    • There are only negative constraints
    • And initializing the next variable can not unmatch a negative constraint that was matched by a previous initialized variable.
Most use cases only have negative constraints. Many of those have an InitializingScoreTrend that only goes down: 
  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    <scoreDrl>.../cloudBalancingScoreRules.drl</scoreDrl>
    <initializingScoreTrend>ONLY_DOWN</initializingScoreTrend>
  </scoreDirectorFactory>
Alternatively, you can also specify the trend for each score level separately: 
  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    <scoreDrl>.../cloudBalancingScoreRules.drl</scoreDrl>
    <initializingScoreTrend>ONLY_DOWN/ONLY_DOWN</initializingScoreTrend>
  </scoreDirectorFactory>

5.3.6. Invalid Score Detection

Put the environmentMode in FULL_ASSERT (or FAST_ASSERT) to detect corruption in the incremental score calculation. For more information, see the section about environmentMode. However, that will not verify that your score calculator implements your score constraints as your business actually desires.
A piece of incremental score calculator code can be difficult to write and to review. Assert its correctness by using a different implementation (for example a EasyScoreCalculator) to do the assertions triggered by the environmentMode. Just configure the different implementation as a assertionScoreDirectorFactory: 
  <environmentMode>FAST_ASSERT</environmentMode>
  ...
  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
    <assertionScoreDirectorFactory>
      <easyScoreCalculatorClass>org.optaplanner.examples.nqueens.solver.score.NQueensEasyScoreCalculator</easyScoreCalculatorClass>
    </assertionScoreDirectorFactory>
  </scoreDirectorFactory>
This way, the scoreDrl will be validated by the EasyScoreCalculator.