Every initialized Solution has a score. That score is an objective way to compare 2
solutions: the solution with the highest score is better. 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 solving,
so it might be the optimal solution.
Planner cannot automatically know which Solution your business prefers, so you need to
tell it how to calculate the score of a Solution.
Most planning problems use negative scores, because they have negative constraints. In that case, the score is usually the sum of the weight of the negative constraints being broken, with an perfect score of 0. This explains why the score of a solution of 4 queens is the negative (and not the positive!) of the number of queen couples which can attack each other.
Negative and positive constraints can be combined, even in the same level.
Note
Don't presume your business knows all its score constraints in advance. Expect score constraints to be added or changed after the first releases.
When a constraint activates (because the negative constraint is broken or the positive constraint is fulfilled) on a certain planning entity set, it is called a constraint occurrence.
Not all score constraints are equally important. If breaking one constraint is equally bad as breaking another constraint x times, then those 2 constraints have a different weight (but they are in the same score level). For example in vehicle routing, you can make 5 broken "avoid crossroads" soft constraints count as much as 1 broken "avoid highways at rush hour" soft constraint.
The weight of a constraint occurrence is often dynamically based on the planning entities involved. For
example in cloud balance: the weight of the soft constraint occurrence for an active Computer
is the cost of that Computer.
Note
Your business will probably tell you that your hard constraints all have the same weight, because they
cannot be broken (so their weight does not matter). This is not true and it could create a score trap. For example in cloud balance: if a Computer has 7 CPU
too little for its Processes, then it must be weighted 7 times as much as if it had only 1
CPU too little. This way, there is an incentive to move a Process with 6 CPU or less away
from that Computer.
Sometimes score constraints are in different level. If breaking one constraint is always worse than another, no matter how much another constraint is broken, then those 2 constraints are in a different level.
Most use cases have 2 score levels: hard and soft. When comparing 2 scores, the higher score level gets compared first. If those differ, the lower score levels are ignored. For example: a score that breaks 0 hard constraints and 1000000 soft constraints is better than a score that breaks 1 hard constraint and 0 soft constraints.
A score is represented by the Score interface, which naturally extends
Comparable:
public interface Score<...> extends Comparable<...> {
...
}
The Score implementation to use depends on your use case. Your score might not
efficiently fit in a single double value. Planner has several build-in Score implementations,
but you can also implement a custom Score too. Most use cases will just use the build-in
HardAndSoftScore.
The Score implementation (for example DefaultHardAndSoftScore) must be
the same throughout a Solver runtime. The Score implementation is configured
in the solver configuration as a ScoreDefinition:
<scoreDirectorFactory>
<scoreDefinitionType>HARD_AND_SOFT</scoreDefinitionType>
...
</scoreDirectorFactory>
Based on your score constraints and score level requirements, you 'll choose a certain
ScoreDefinition:
The SimpleScoreDefinition defines the Score as a
SimpleScore which has a single int value, for example
-123. It has 1 score level.
<scoreDirectorFactory>
<scoreDefinitionType>SIMPLE</scoreDefinitionType>
...
</scoreDirectorFactory>
Variants:
SimpleDoubleScore: Uses adoublevalue instead of anintvalue. Configure it withscoreDefinitionTypeSIMPLE_DOUBLE.
The HardAndSoftScoreDefinition defines the Score as a
HardAndSoftScore which has a hard int value and a soft
int value, for example -123hard/-456soft. It has 2 score levels (hard and
soft).
<scoreDirectorFactory>
<scoreDefinitionType>HARD_AND_SOFT</scoreDefinitionType>
...
</scoreDirectorFactory>
Variants:
HardAndSoftLongScore: Useslongvalues instead ofintvalues. Configure it withscoreDefinitionTypeHARD_AND_SOFT_LONG.
The ScoreDefinition interface defines the score representation.
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:
<scoreDirectorFactory>
<scoreDefinitionClass>org.drools.planner.examples.my.score.definition.MyScoreDefinition</scoreDefinitionClass>
...
</scoreDirectorFactory>
There are several ways to calculate the Score of a Solution:
Simple Java score calculation: implement a single Java method
Incremental Java score calculation: implement multiple Java methods
Drools score calculation: implement score rules
Every score calculation type can use any Score definition. For example, simple score calculation can output
a HardAndSoftScore.
All score calculation types are Object Orientated and can reuse existing Java code.
A simple 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:
Slower and less scalable
Because there is no incremental score calculation
Just implement one method of the interface SimpleScoreCalculator:
public interface SimpleScoreCalculator<Sol extends Solution> {
Score calculateScore(Sol solution);
}
For example in n queens:
public class NQueensSimpleScoreCalculator implements SimpleScoreCalculator<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 DefaultSimpleScore.valueOf(score);
}
}
Configure it in your solver configuration:
<scoreDirectorFactory>
<scoreDefinitionType>...</scoreDefinitionType>
<simpleScoreCalculatorClass>org.drools.planner.examples.nqueens.solver.score.NQueensSimpleScoreCalculator</simpleScoreCalculatorClass>
</scoreDirectorFactory>
Alternatively, build a SimpleScoreCalculator instance at runtime and set it with the
programmatic API:
solverFactory.getSolverConfig().getScoreDirectorFactoryConfig.setSimpleScoreCalculator(simpleScoreCalculator);
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:
public interface IncrementalScoreCalculator<Sol extends Solution> {
void resetWorkingSolution(Sol workingSolution);
void beforeEntityAdded(Object entity);
void afterEntityAdded(Object entity);
void beforeAllVariablesChanged(Object entity);
void afterAllVariablesChanged(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 beforeAllVariablesChanged(Object entity) {
retract((Queen) entity);
}
public void afterAllVariablesChanged(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 DefaultSimpleScore.valueOf(score);
}
}
Configure it in your solver configuration:
<scoreDirectorFactory>
<scoreDefinitionType>...</scoreDefinitionType>
<incrementalScoreCalculatorClass>org.drools.planner.examples.nqueens.solver.score.NQueensAdvancedIncrementalScoreCalculator</incrementalScoreCalculatorClass>
</scoreDirectorFactory>
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
Guvnor WebUI
Translate them into natural language with DSL
Store and release in the Guvnor 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
There are sever ways to define where your score rules live.
This is the easy 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:
<scoreDirectorFactory>
<scoreDefinitionType>...</scoreDefinitionType>
<scoreDrl>/org/drools/planner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
</scoreDirectorFactory>
You can add multiple <scoreDrl> entries if needed, but normally you 'll define
all your score rules in 1 file.
Here's an example of a score constraint implemented as a score rule in 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));
endThis 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.
A ScoreHolder instance is asserted into the WorkingMemory as a
global called scoreHolder. Your score rules need to (directly or indirectly) update that
instance. Usually you 'll make a single rule as an aggregation of the other rules to update the score:
global SimpleScoreHolder scoreHolder;
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
scoreHolder.setScore(- $occurrenceCount.intValue());
endMost use cases will also weigh their constraints differently, by multiplying the count of each score rule with its weight.
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:
// 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
scoreHolder.setSoftConstraintsBroken($softTotal.intValue());
endThe Solver will normally spend most of its execution time running the score calculation
(which is called in its deepest loops). Faster score calculation will return the same solution in less time, which
normally means a better solution in equal time.
After solving a problem, the Solver will log the average calculation count per second.
This is a good measurement of Score calculation performance, but it depends on the problem scale. Normally, even
for high scale problems, it is higher than 1000, unless you're using
SimpleScoreCalculator.
When a Solution changes, incremental score calculation (AKA delta based score
calculation), will calculate the delta with the previous state to find the new Score, instead
of recalculating the entire score on every solution evaluation.
For example, if a single queen A moves from row 1 to 2, it won't
bother to check if queen B and C can attack each other, since neither of them changed.
This is a huge performance and scalability gain. Drools score calculation gives you this huge scalability gain without forcing you to write a complicated incremental score calculation algorithm. Just let the Drools rule engine do the hard work.
Notice that the speedup is relative to the size of your planning problem (your n), making incremental score calculation far more scalable.
Do not call remote services in your score calculation (except if you're bridging
SimpleScoreCalculator to a legacy system). The network latency will kill your score calculation
performance. Cache the results of those remote services if possible
If some parts of a constraint can be calculated once, when the Solver starts, and never
change during solving, then turn them into cached problem facts.
If you know a certain constraint can never be broken, don't bother writing a score constraint for it. For
example in n queens, the score calculation doesn't check if multiple queens occupy the same column, because a
Queen's column never changes and every Solution starts
with each Queen on a different column.
Note
Don't go overboard with this. If some datasets don't use a specific constraint but others do, just return out of the constraint as soon as you can. There is no need to dynamically change your score calculation based on the dataset.
Instead of implementing a hard constraint, you can sometimes make it build-in too. For example: If
Course A should never be assigned to Room X, but it uses ValueRange from
Solution, the Solver will often try to assign it to Room X too (only to find
out that it breaks a hard constraint). Switch to ValueRange from
planning entity to define that Course A should only be assigned a Room other then
X.
This tends to give a good performance gain, not just because the score calculation is faster, but mainly because most optimization algorithms will spend less time evaluating unfeasible solutions.
Note
Don't go overboard with this. Many optimization algorithms rely on the freedom to break hard constraints when changing planning entities, to get out of local optima. There is a risk of trading short term benefits for long term harm.
Verify that your score calculation happens in the correct
Numbertype. If you're making the sum ofintvalues, don't let Drools sum it in adoublewhich takes longer.For optimal performance, always use server mode (
java -server). We have seen performance increases of 50% by turning on server mode.For optimal performance, use at least java 1.6. We have seen performance increases of 30% by switching from java 1.5 to 1.6.
Always remember that premature optimization is the root of all evil. Make sure your design is flexible enough to allow configuration based tweaking.
Be watchful 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 incentive 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 incentive to move a doctor to table which is short of a doctor and a politician.
Other parts of your application, for example your webUI, might need to calculate the score too. Do that by
reusing the ScoreDirectorFactory of the Solver to build a separate
ScoreDirector for that webUI:
ScoreDirectorFactory scoreDirectorFactory = solver.getScoreDirectorFactory();
ScoreDirector guiScoreDirector = scoreDirectorFactory.buildScoreDirector();
Then use it when you need to calculate the Score of a Solution:
guiScoreDirector.setWorkingSolution(solution);
Score score = guiScoreDirector.calculateScore();
Currently it's not officially supported to get the specific constraint occurrences, so you can explain in the
GUI what entities are causing which part of the Score. But if you're using the
DroolsScoreDirector, it's possible. See the examples.