Chapter 10. The OptaPlanner Score interface

A score is represented by the Score interface, which extends the Comparable interface:

public interface Score<...> extends Comparable<...> {
    ...
}

The score implementation to use depends on your use case. Your score might not efficiently fit in a single long value. OptaPlanner has several built-in score implementations, but you can implement a custom score as well. Most use cases use the built-in HardSoftScore score.

Example score class diagram

All Score implementations also have an initScore (which is an int). It is mostly intended for internal use in OptaPlanner: it is the negative number of uninitialized planning variables. From a user’s perspective, this is 0, unless a construction heuristic is terminated before it could initialize all planning variables. In this case, Score.isSolutionInitialized() returns false.

The score implementation (for example HardSoftScore) must be the same throughout a solver runtime. The score implementation is configured in the solution domain class:

@PlanningSolution
public class CloudBalance {
    ...

    @PlanningScore
    private HardSoftScore score;

}

10.1. Floating point numbers in score calculation

Avoid the use of the floating point number types float or double in score calculation. Use BigDecimal or scaled long instead. Floating point numbers cannot represent a decimal number correctly. For example, a double cannot contain the value 0.05 correctly. Instead, it contains the nearest representable value. Arithmetic, including addition and subtraction, that uses floating point numbers, especially for planning problems, leads to incorrect decisions as shown in the following illustration:

Illustration of score weight types

Additionally, floating point number addition is not associative:

System.out.println( ((0.01 + 0.02) + 0.03) == (0.01 + (0.02 + 0.03)) ); // returns false

This leads to score corruption.

Decimal numbers (BigDecimal) have none of these problems.

Note

BigDecimal arithmetic is considerably slower than int, long, or double arithmetic. In some experiments, the score calculation takes five times longer.

Therefore, in many cases, it can be worthwhile to multiply all numbers for a single score weight by a plural of ten, so the score weight fits in a scaled int or long. For example, if you multiply all weights by 1000, a fuelCost of 0.07 becomes a fuelCostMillis of 70 and no longer uses a decimal score weight.

10.2. Score calculation types

There are several types of ways to calculate the score of a solution:

  • Easy Java score calculation: Implement all constraints together in a single method in Java or another JVM language. This method does not scale.
  • Constraint streams score calculation: Implement each constraint as a separate constraint stream in Java or another JVM language. This method is fast and scalable.
  • Incremental Java score calculation (not recommended): Implement multiple low-level methods in Java or another JVM language. This method is fast and scalable but very difficult to implement and maintain.
  • Drools score calculation (deprecated): Implement each constraint as a separate score rule in DRL. This method is scalable.

Each score calculation type can work with any score definition, for example HardSoftScore or HardMediumSoftScore. All score calculation types are object oriented and can reuse existing Java code.

Important

The score calculation must be read-only. It must not change the planning entities or the problem facts in any way. For example, the score calculation must not call a setter method on a planning entity in the score calculation.

OptaPlanner does 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 is no guarantee that changes applied during score calculation actually happen.

To update planning entities when the planning variable changes, use shadow variables instead.

10.2.1. Implenting the Easy Java score calculation type

The Easy Java score calculation type provides an easy way to implement your score calculation in Java. You can implement all constraints together in a single method in Java or another JVM language.

  • Advantages:

    • Uses plain old Java so there is no learning curve
    • Provides an opportunity to delegate score calculation to an existing code base or legacy system
  • Disadvantages:

    • Slowest calculation type
    • Does not scale because there is no incremental score calculation

Procedure

  1. Implement the EasyScoreCalculator interface:

    public interface EasyScoreCalculator<Solution_, Score_ extends Score<Score_>> {
    
        Score_ calculateScore(Solution_ solution);
    
    }

    The following example implements this interface in the N Queens problem:

    public class NQueensEasyScoreCalculator
        implements EasyScoreCalculator<NQueens, SimpleScore> {
    
        @Override
        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);
        }
    
    }
  2. Configure the EasyScoreCalculator class in the solver configuration. The following example shows how to implement this interface in the N Queens problem:

      <scoreDirectorFactory>
        <easyScoreCalculatorClass>org.optaplanner.examples.nqueens.optional.score.NQueensEasyScoreCalculator</easyScoreCalculatorClass>
      </scoreDirectorFactory>
  3. To configure values of the EasyScoreCalculator method dynamically in the solver configuration so that the benchmarker can tweak those parameters, add the easyScoreCalculatorCustomProperties element and use custom properties:

      <scoreDirectorFactory>
        <easyScoreCalculatorClass>...MyEasyScoreCalculator</easyScoreCalculatorClass>
        <easyScoreCalculatorCustomProperties>
          <property name="myCacheSize" value="1000" />
        </easyScoreCalculatorCustomProperties>
      </scoreDirectorFactory>

10.2.2. Implementing the Incremental Java score calculation type

The Incremental Java score calculation type provides a way to implement your score calculation incrementally in Java.

Note

This type is not recommended.

  • Advantages:

    • Very fast and scalable. This is currently the fastest type if implemented correctly.
  • Disadvantages:

    • Hard to write.

      • A scalable implementation that heavily uses maps, indexes, and so forth.
      • You have to learn, design, write, and improve all of these performance optimizations yourself.
    • Hard to read. Regular score constraint changes can lead to a high maintenance cost.

Procedure

  1. Implement all of the methods of the IncrementalScoreCalculator interface:

    public interface IncrementalScoreCalculator<Solution_, Score_ extends Score<Score_>> {
    
        void resetWorkingSolution(Solution_ 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();
    
    }
    IncrementalScoreCalculator sequence diagram

    The following example implements this interface in the N Queens problem:

    public class NQueensAdvancedIncrementalScoreCalculator
        implements IncrementalScoreCalculator<NQueens, SimpleScore> {
    
        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);
        }
    
    }
  2. Configure the incrementalScoreCalculatorClass class in the solver configuration. The following example shows how to implement this interface in the N Queens problem:

      <scoreDirectorFactory>
        <incrementalScoreCalculatorClass>org.optaplanner.examples.nqueens.optional.score.NQueensAdvancedIncrementalScoreCalculator</incrementalScoreCalculatorClass>
      </scoreDirectorFactory>
    Important

    A piece of incremental score calculator code can be difficult to write and to review. Assert its correctness by using an EasyScoreCalculator to fulfill the assertions triggered by the environmentMode.

  3. To configure values of an IncrementalScoreCalculator dynamically in the solver configuration so the benchmarker can tweak those parameters, add the incrementalScoreCalculatorCustomProperties element and use custom properties:

      <scoreDirectorFactory>
        <incrementalScoreCalculatorClass>...MyIncrementalScoreCalculator</incrementalScoreCalculatorClass>
        <incrementalScoreCalculatorCustomProperties>
          <property name="myCacheSize" value="1000"/>
        </incrementalScoreCalculatorCustomProperties>
      </scoreDirectorFactory>
  4. Optional: Implement the ConstraintMatchAwareIncrementalScoreCalculator interface to facilitate the following goals:

    • Explain a score by splitting it up for each score constraint with ScoreExplanation.getConstraintMatchTotalMap().
    • Visualize or sort planning entities by how many constraints each one breaks with ScoreExplanation.getIndictmentMap().
    • Receive a detailed analysis if the IncrementalScoreCalculator is corrupted in FAST_ASSERT or FULL_ASSERT environmentMode.

      public interface ConstraintMatchAwareIncrementalScoreCalculator<Solution_, Score_ extends Score<Score_>> {
      
          void resetWorkingSolution(Solution_ workingSolution, boolean constraintMatchEnabled);
      
          Collection<ConstraintMatchTotal<Score_>> getConstraintMatchTotals();
      
          Map<Object, Indictment<Score_>> getIndictmentMap();
      }

      For example, in machine reassignment create one ConstraintMatchTotal for each constraint type and call addConstraintMatch() for each constraint match:

      public class MachineReassignmentIncrementalScoreCalculator
              implements ConstraintMatchAwareIncrementalScoreCalculator<MachineReassignment, HardSoftLongScore> {
          ...
      
          @Override
          public void resetWorkingSolution(MachineReassignment workingSolution, boolean constraintMatchEnabled) {
              resetWorkingSolution(workingSolution);
              // ignore constraintMatchEnabled, it is always presumed enabled
          }
      
          @Override
          public Collection<ConstraintMatchTotal<HardSoftLongScore>> getConstraintMatchTotals() {
              ConstraintMatchTotal<HardSoftLongScore> maximumCapacityMatchTotal = new DefaultConstraintMatchTotal<>(CONSTRAINT_PACKAGE,
                  "maximumCapacity", HardSoftLongScore.ZERO);
              ...
              for (MrMachineScorePart machineScorePart : machineScorePartMap.values()) {
                  for (MrMachineCapacityScorePart machineCapacityScorePart : machineScorePart.machineCapacityScorePartList) {
                      if (machineCapacityScorePart.maximumAvailable < 0L) {
                          maximumCapacityMatchTotal.addConstraintMatch(
                                  Arrays.asList(machineCapacityScorePart.machineCapacity),
                                  HardSoftLongScore.valueOf(machineCapacityScorePart.maximumAvailable, 0));
                      }
                  }
              }
              ...
              List<ConstraintMatchTotal<HardSoftLongScore>> constraintMatchTotalList = new ArrayList<>(4);
              constraintMatchTotalList.add(maximumCapacityMatchTotal);
              ...
              return constraintMatchTotalList;
          }
      
          @Override
          public Map<Object, Indictment<HardSoftLongScore>> getIndictmentMap() {
              return null; // Calculate it non-incrementally from getConstraintMatchTotals()
          }
      }

      The getConstraintMatchTotals() code often duplicates some of the logic of the normal IncrementalScoreCalculator methods. Constraint Streams and Drools Score Calculation do not have this disadvantage because they are constraint-match aware automatically when needed without any extra domain-specific code.