Constraints and Score

Every @PlanningSolution class has a score. The score is an objective way to compare two solutions. The solution with the higher score is better. The Solver aims to find the solution with the highest Score of all possible solutions. The best solution is the solution with the highest Score that Solver has encountered during solving, which might be the optimal solution.

Timefold Solver cannot automatically know which solution is best for your business, so you need to tell it how to calculate the score of a given @PlanningSolution instance according to your business needs. If you forget or are unable to implement an important business constraint, the solution is probably useless:

To implement a verbal business constraint, it needs to be formalized as a score constraint. Luckily, defining constraints in Timefold Solver is very flexible through the following score techniques:

Take the time to acquaint yourself with the first three techniques. Once you understand them, formalizing most business constraints becomes straightforward.

All score techniques are based on constraints. A constraint can be a simple pattern (such as Maximize the apple harvest in the solution) or a more complex pattern. A positive constraint is a constraint you want to maximize. A negative constraint is a constraint you want to minimize

The image above illustrates that the optimal solution always has the highest score, regardless if the constraints are positive or negative.

Most planning problems have only negative constraints and therefore have a negative score. In that case, the score is the sum of the weight of the negative constraints being broken, with a perfect score of 0. For example in n queens, the score is the negative of the number of queen pairs which can attack each other.

Negative and positive constraints can be combined, even in the same score level.

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 match.

Not all score constraints are equally important. If breaking one constraint is equally bad as breaking another constraint x times, then those two constraints have a different weight (but they are in the same score level). For example in vehicle routing, you can make one unhappy driver constraint match count as much as two fuel tank usage constraint matches:

Score weighting is easy in use cases where you can put a price tag on everything. In that case, the positive constraints maximize revenue and the negative constraints minimize expenses, so together they maximize profit. Alternatively, score weighting is also often used to create social fairness. For example, a nurse, who requests a free day, pays a higher weight on New Years eve than on a normal day.

The weight of a constraint match can depend on the planning entities involved. For example in cloud balancing, the weight of the soft constraint match for an active Computer is the maintenance cost of that Computer (which differs per computer).

Putting a good weight on a constraint is often a difficult analytical decision, because it is about making choices and trade-offs against other constraints. Different stakeholders have different priorities. Don’t waste time with constraint weight discussions at the start of an implementation, instead add a constraint configuration and allow users to change them through a UI. A non-accurate weight is less damaging than mediocre algorithms:

Most use cases use a Score with int weights, such as HardSoftScore.

Sometimes a score constraint outranks another score constraint, no matter how many times the latter is broken. In that case, those score constraints are in different levels. For example, a nurse cannot do two shifts at the same time (due to the constraints of physical reality), so this outranks all nurse happiness constraints.

Most use cases have only two score levels, hard and soft. The levels of two scores are compared lexicographically. The first score level gets compared first. If those differ, the remaining 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.

If there are two (or more) score levels, for example HardSoftScore, then a score is feasible if no hard constraints are broken.

For each constraint, you need to pick a score level, a score weight and a score signum. For example: -1soft which has score level of soft, a weight of 1 and a negative signum. Do not use a big constraint weight when your business actually wants different score levels. That hack, known as score folding, is broken:

Three or more score levels are also supported. For example: a company might decide that profit outranks employee satisfaction (or vice versa), while both are outranked by the constraints of physical reality.

Most use cases use a Score with two or three weights, such as HardSoftScore and HardMediumSoftScore.

Far less common is the use case of pareto optimization, which is also known as multi-objective optimization. In pareto scoring, score constraints are in the same score level, yet they are not weighted against each other. When two scores are compared, each of the score constraints are compared individually and the score with the most dominating score constraints wins. Pareto scoring can even be combined with score levels and score constraint weighting.

Consider this example with positive constraints, where we want to get the most apples and oranges. Since it is impossible to compare apples and oranges, we cannot weigh them against each other. Yet, despite that we cannot compare them, we can state that two apples are better than one apple. Similarly, we can state that two apples and one orange are better than just one orange. So despite our inability to compare some Scores conclusively (at which point we declare them equal), we can find a set of optimal scores. Those are called pareto optimal.

Scores are considered equal far more often. It is left up to a human to choose the better out of a set of best solutions (with equal scores) found by Timefold Solver. In the example above, the user must choose between solution A (three apples and one orange) and solution B (one apple and six oranges). It is guaranteed that Timefold Solver has not found another solution which has more apples or more oranges or even a better combination of both (such as two apples and three oranges).

Pareto scoring is currently not supported in Timefold Solver.

All the score techniques mentioned above, can be combined seamlessly:

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

The Score implementation to use depends on your use case. Your score might not efficiently fit in a single long value. Timefold Solver has several built-in Score implementations. Most use cases tend to use HardSoftScore.

All Score implementations also have an initScore (which is an int). It is mostly intended for internal use in Timefold Solver: 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 which 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:

Avoid the use of float or double in score calculation. Use BigDecimal or scaled long instead.

Floating point numbers (float and double) cannot represent a decimal number correctly. For example: a double cannot hold the value 0.05 correctly. Instead, it holds the nearest representable value. Arithmetic (including addition and subtraction) with floating point numbers, especially for planning problems, leads to incorrect decisions:

Additionally, floating point number addition is not associative:

This leads to score corruption.

Decimal numbers (BigDecimal) have none of these problems.

A SimpleScore has a single int value, for example -123. It has a single score level.

Variants of this Score type:

A HardSoftScore has a hard int value and a soft int value, for example -123hard/-456soft. It has two score levels (hard and soft).

Variants of this Score type:

A HardMediumSoftScore which has a hard int value, a medium int value and a soft int value, for example -123hard/-456medium/-789soft. It has three score levels (hard, medium and soft). The hard level determines if the solution is feasible, and the medium level and soft level score values determine how well the solution meets business goals. Higher medium values take precedence over soft values irrespective of the soft value.

Variants of this Score type:

A BendableScore has a configurable number of score levels. It has an array of hard int values and an array of soft int values, for example with two hard levels and three soft levels, the score can be [-123/-456]hard/[-789/-012/-345]soft. In that case, it has five score levels. A solution is feasible if all hard levels are at least zero.

A BendableScore with one hard level and one soft level is equivalent to a HardSoftScore, while a BendableScore with one hard level and two soft levels is equivalent to a HardMediumSoftScore.

The number of hard and soft score levels need to be set at compilation time. It is not flexible to change during solving.

Variants of this Score type:

There are several ways to calculate the Score of a solution in Hava or another JVM language:

Every score calculation type can work with any Score definition (such as HardSoftScore or HardMediumSoftScore). All score calculation types are Object Oriented and can reuse existing Java code.

The InitializingScoreTrend specifies how the Score will change as more and more variables are initialized (while the already initialized variables do not change). Some optimization algorithms (such Construction Heuristics and Exhaustive Search) run faster if they have such information.

For the Score (or each score level separately), specify a trend:

Most use cases only have negative constraints. Many of those have an InitializingScoreTrend that only goes down:

Alternatively, you can also specify the trend for each score level separately:

When you put the environmentMode in FULL_ASSERT (or FAST_ASSERT), it will detect score corruption in the incremental score calculation. However, that will not verify that your score calculator actually implements your score constraints as your business desires. For example, one constraint might consistently match the wrong pattern. To verify the constraints against an independent implementation, configure a assertionScoreDirectorFactory:

This way, the NQueensConstraintProvider implementation is validated by the EasyScoreCalculator.

To use the ConstraintStreams API in your project, first write a pure Java ConstraintProvider implementation similar to the following example.

Add the following code to your solver configuration:

Constraint stream cardinality is a measure of how many objects a single constraint match consists of. The simplest constraint stream has a cardinality of 1, meaning each constraint match only consists of 1 object. Therefore, it is called a UniConstraintStream:

Some constraint stream building blocks can increase stream cardinality, such as join or groupBy:

The latter can also decrease stream cardinality:

The following constraint stream cardinalities are currently supported:

Constraint streams are chains of different operations, called building blocks. Each constraint stream starts with a forEach(…​) building block and is terminated by either a penalty or a reward. The following example shows the simplest possible constraint stream:

This constraint stream penalizes each known and initialized instance of Shift.

We recommend that you test your constraints to ensure that they behave as expected. Constraint streams include the Constraint Verifier unit testing harness. To use it, first add a test scoped dependency to the timefold-solver-test JAR.

The 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 with the same algorithm, which normally means a better solution in equal time.

After solving a problem, the Solver will log the score calculation speed per second. This is a good measurement of Score calculation performance, despite that it is affected by non score calculation execution time. It depends on the problem scale of the problem dataset. Normally, even for high scale problems, it is higher than 1000, except if you are using an EasyScoreCalculator.

When a solution changes, incremental score calculation (AKA delta based score calculation) calculates the delta with the previous state to find the new Score, instead of recalculating the entire score on every solution evaluation.

For example, when a single queen A moves from row 1 to 2, it will not bother to check if queen B and C can attack each other, since neither of them changed:

Similarly in employee rostering:

This is a huge performance and scalability gain. Constraint Streams gives you this huge scalability gain without forcing you to write a complicated incremental score calculation algorithm.* Just let the 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 are bridging EasyScoreCalculator 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 (or it is always broken), do not write a score constraint for it. For example in n queens, the score calculation does not 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.

Instead of implementing a hard constraint, it can sometimes be built in. For example, if Lecture A should never be assigned to Room X, but it uses ValueRangeProvider on Solution, so the Solver will often try to assign it to Room X too (only to find out that it breaks a hard constraint). Use a ValueRangeProvider on the planning entity or filtered selection to define that Course A should only be assigned a Room different than X.

This can give a good performance gain in some use cases, not just because the score calculation is faster, but mainly because most optimization algorithms will spend less time evaluating infeasible solutions. However, usually this is not a good idea because there is a real risk of trading short term benefits for long term harm:

Make sure that none of your score constraints cause a score trap. A trapped score constraint uses the same weight for different constraint matches, when it could just as easily use a different weight. It effectively lumps its constraint matches together, which creates a flatlined score function for that constraint. This can cause a solution state in which several moves need to be done to resolve or lower the weight of that single constraint. Some examples of score traps:

For example, consider this score trap. If the blue item moves from an overloaded computer to an empty computer, the hard score should improve. The trapped score implementation fails to do that:

The Solver should eventually get out of this trap, but it will take a lot of effort (especially if there are even more processes on the overloaded computer). Before they do that, they might actually start moving more processes into that overloaded computer, as there is no penalty for doing so.

There are several ways to deal with a score trap:

Not all score constraints have the same performance cost. Sometimes one score constraint can kill the score calculation performance outright. Use the Benchmarker to do a one minute run and check what happens to the score calculation speed if you comment out all but one of the score constraints.

Some use cases have a business requirement to provide a fair schedule (usually as a soft score constraint), for example:

Implementing such a constraint can seem difficult (especially because there are different ways to formalize fairness), but usually the squared workload implementation behaves most desirable. For each employee/asset, count the workload w and subtract w² from the score.

As shown above, the squared workload implementation guarantees that if you select two employees from a given solution and make their distribution between those two employees fairer, then the resulting new solution will have a better overall score. Do not just use the difference from the average workload, as that can lead to unfairness, as demonstrated below.

When the workload is perfectly balanced, the user often likes to see a 0 score, instead of the distracting -34soft in the image above (for the last solution which is almost perfectly balanced). To nullify this, either add the average multiplied by the number of entities to the score or instead show the variance or standard deviation in the UI.

First, create a new class to hold the constraint weights and other constraint parameters. Annotate it with @ConstraintConfiguration:

There will be exactly one instance of this class per planning solution. The planning solution and the constraint configuration have a one-to-one relationship, but they serve a different purpose, so they aren’t merged into a single class. A @ConstraintConfiguration class can extend a parent @ConstraintConfiguration class, which can be useful in international use cases with many regional constraints.

Add the constraint configuration on the planning solution and annotate that field or property with @ConstraintConfigurationProvider:

The @ConstraintConfigurationProvider annotation automatically exposes the constraint configuration as a problem fact, there is no need to add a @ProblemFactProperty annotation.

The constraint configuration class holds the constraint weights, but it can also hold constraint parameters. For example in conference scheduling, the minimum pause constraint has a constraint weight (like any other constraint), but it also has a constraint parameter that defines the length of the minimum pause between two talks of the same speaker. That pause length depends on the conference (= the planning problem): in some big conferences 20 minutes isn’t enough to go from one room to the other. That pause length is a field in the constraint configuration without a @ConstraintWeight annotation.

In the constraint configuration class, add a @ConstraintWeight field or property for each constraint:

The type of the constraint weights must be the same score class as the planning solution’s score member. For example in conference scheduling, ConferenceSolution.getScore() and ConferenceConstraintConfiguration.getSpeakerConflict() both return a HardMediumSoftScore.

A constraint weight cannot be null. Give each constraint weight a default value, but expose them in a UI so the business users can tweak them. The example above uses the ofHard(), ofMedium() and ofSoft() methods to do that. Notice how it defaults the content conflict constraint as ten times more important than the theme track conflict constraint. Normally, a constraint weight only uses one score level, but it’s possible to use multiple score levels (at a small performance cost).

Each constraint has a constraint package and a constraint name, together they form the constraint id. These connect the constraint weight with the constraint implementation. For each constraint weight, there must be a constraint implementation with the same package and the same name.

So every constraint weight ends up with a constraint package and a constraint name. Each constraint weight links with a constraint implementation, for example in Constraint streams:

Each of the constraint weights defines the score level and score weight of their constraint. The constraint implementation calls rewardConfigurable() or penalizeConfigurable() and the constraint weight is automatically applied.

If the constraint implementation provides a match weight, that match weight is multiplied with the constraint weight. For example, the content conflict constraint weight defaults to 100soft and the constraint implementation penalizes each match based on the number of shared content tags and the overlapping duration of the two talks:

So when 2 overlapping talks share only 1 content tag and overlap by 60 minutes, the score is impacted by -6000soft. But when 2 overlapping talks share 3 content tags, the match weight is 180, so the score is impacted by -18000soft.

If other parts of your application, for example your webUI, need to calculate the score of a solution, use the SolutionManager API:

Then use it when you need to calculate the Score of a solution:

Furthermore, the ScoreExplanation can help explain the score through constraint match totals and/or indictments:

Each constraint may be justified by a different ConstraintJustification implementation, but you can also choose to share them among constraints. To receive all constraint justifications regardless of their type, call:

In Constraint streams, justifications can be customized, so that it can be easily serialized and sent over the wire. Such custom justifications can be queried like so:

To break down the score per constraint, get the ConstraintMatchTotals from the ScoreExplanation:

Each ConstraintMatchTotal represents one constraint and has a part of the overall score. The sum of all the ConstraintMatchTotal.getScore() equals the overall score.

To show a heat map in the UI that highlights the planning entities and problem facts have an impact on the Score, get the Indictment map from the ScoreExplanation:

Each Indictment is the sum of all constraints where that justification object is involved with. The sum of all the Indictment.getScoreTotal() differs from the overall score, because multiple Indictments can share the same ConstraintMatch.