Optimization Algorithms: Overview

Terminates when an amount of time has been used.

Alternatively to a java.util.Duration in ISO 8601 format, you can also use:

Multiple time types can be used together, for example to configure 150 minutes, either configure it directly:

Or use a combination that sums up to 150 minutes:

Terminates when the best score has not improved in a specified amount of time. Each time a new best solution is found, the timer basically resets.

Alternatively to a java.util.Duration in ISO 8601 format, you can also use:

Just like time spent termination, combinations are summed up.

It is preffered to configure this termination on a specific Phase (such as <localSearch>) instead of on the Solver itself.

Several phases, such as construction heuristics, do not count towards this termination because they only trigger new best solution events when they are done. If such a phase is encountered, the termination is disabled and when the next phase is started, the termination is enabled again and the timer resets back to zero. In the most typical case, where a local search phase follows a construction heuristic phase, the termination will only trigger if the local search phase does not improve the best solution for the specified time.

Optionally, configure a score difference threshold by which the best score must improve in the specified time. For example, if the score doesn’t improve by at least 100 soft points every 30 seconds or less, it terminates:

If the score improves by 1 hard point and drops 900 soft points, it’s still meets the threshold, because 1hard/-900soft is larger than the threshold 0hard/100soft.

On the other hand, a threshold of 1hard/0soft is not met by any new best solution that improves 1 hard point at the expense of 1 or more soft points, because 1hard/-100soft is smaller than the threshold 1hard/0soft.

To require a feasibility improvement every 30 seconds while avoiding the pitfall above, use a wildcard * for lower score levels that are allowed to deteriorate if a higher score level improves:

This effectively implies a threshold of 1hard/-2147483648soft, because it relies on Integer.MIN_VALUE.

BestScoreTermination terminates when a certain score has been reached. Use this Termination where the perfect score is known, for example for four queens (which uses a SimpleScore):

A planning problem with a HardSoftScore may look like this:

A planning problem with a BendableScore with three hard levels and one soft level may look like this:

In this instance, Termination once a feasible solution has been reached is not practical because it requires a bestScoreLimit such as 0hard/-2147483648soft. Use the next termination instead.

Terminates as soon as a feasible solution has been discovered.

This Termination is usually combined with other terminations.

Terminates when a number of steps has been reached. This is useful for hardware performance independent runs.

This Termination can only be used for a Phase (such as <localSearch>), not for the Solver itself.

Terminates when the best score has not improved in a number of steps. This is useful for hardware performance independent runs.

If the score has not improved recently, it is unlikely to improve in a reasonable timeframe. It has been observed that once a new best solution is found (even after a long time without improvement on the best solution), the next few steps tend to improve the best solution.

This Termination can only be used for a Phase (such as <localSearch>), not for the Solver itself.

ScoreCalculationCountTermination terminates when a number of score calculations have been reached. This is often the sum of the number of moves and the number of steps. This is useful for benchmarking.

Switching EnvironmentMode can heavily impact when this termination ends.

MoveCountTermination terminates when a number of evaluated moves have been reached. This is useful for benchmarking.

Switching EnvironmentMode can heavily impact when this termination ends.

Terminations can be combined, for example: terminate after 100 steps or if a score of 0 has been reached:

Alternatively you can use AND, for example: terminate after reaching a feasible score of at least -100 and no improvements in 5 steps:

This example ensures it does not just terminate after finding a feasible solution, but also completes any obvious improvements on that solution before terminating.

Asynchronous termination cannot be configured by a Termination as it is impossible to predict when and if it will occur. For example, a user action or a server restart could require a solver to terminate earlier than predicted.

To terminate a solver from another thread asynchronously call the terminateEarly() method from another thread:

The solver then terminates at its earliest convenience. After termination, the Solver.solve(Solution) method returns in the solver thread (which is the original thread that called it).

A Move is a change (or set of changes) from a solution A to a solution B. For example, the move below changes queen C from row 0 to row 2:

The new solution is called a neighbor of the original solution, because it can be reached in a single Move. Although a single move can change multiple queens, the neighbors of a solution should always be a tiny subset of all possible solutions. For example, on that original solution, these are all possible changeMoves:

If we ignore the four changeMoves that have no impact and are therefore not doable, we can see that the number of moves is n * (n - 1) = 12. This is far less than the number of possible solutions, which is n ^ n = 256. As the problem scales out, the number of possible moves increases far less than the number of possible solutions.

Yet, in four changeMoves or less we can reach any solution. For example we can reach a very different solution in three changeMoves:

All optimization algorithms use Moves to transition from one solution to a neighbor solution. Therefore, all the optimization algorithms are confronted with Move selection: the craft of creating and iterating moves efficiently and the art of finding the most promising subset of random moves to evaluate first.

A MoveSelector's main function is to create Iterator<Move> when needed. An optimization algorithm will iterate through a subset of those moves.

Here’s an example how to configure a changeMoveSelector for the optimization algorithm Local Search:

Out of the box, this works and all properties of the changeMoveSelector are defaulted sensibly (unless that fails fast due to ambiguity). On the other hand, the configuration can be customized significantly for specific use cases. For example: you might want to configure a filter to discard pointless moves.

To create a Move, a MoveSelector needs to select one or more planning entities and/or planning values to move. Just like MoveSelectors, EntitySelectors and ValueSelectors need to support a similar feature set (such as scalable just-in-time selection). Therefore, they all implement a common interface Selector and they are configured similarly.

A MoveSelector is often composed out of EntitySelectors, ValueSelectors or even other MoveSelectors, which can be configured individually if desired:

Together, this structure forms a Selector tree:

The root of this tree is a MoveSelector which is injected into the optimization algorithm implementation to be (partially) iterated in every step. For a full list of MoveSelector implementations available out of the box, see Move Selector reference.

A unionMoveSelector selects a Move by selecting one of its MoveSelector children to supply the next Move.

Simplest configuration:

Advanced configuration:

The selectorProbabilityWeightFactory determines in selectionOrder RANDOM how often a MoveSelector child is selected to supply the next Move. By default, each MoveSelector child has the same chance of being selected.

Change the fixedProbabilityWeight of such a child to select it more often. For example, the unionMoveSelector can return a SwapMove twice as often as a ChangeMove:

The number of possible ChangeMoves is very different from the number of possible SwapMoves and furthermore it’s problem dependent. To give each individual Move the same selection chance (as opposed to each MoveSelector), use the FairSelectorProbabilityWeightFactory:

A cartesianProductMoveSelector selects a new CompositeMove. It builds that CompositeMove by selecting one Move per MoveSelector child and adding it to the CompositeMove.

Simplest configuration:

Advanced configuration:

The ignoreEmptyChildIterators property (true by default) will ignore every empty childMoveSelector to avoid returning no moves. For example: a cartesian product of changeMoveSelector A and B, for which B is empty (because all it’s entities are pinned) returns no move if ignoreEmptyChildIterators is false and the moves of A if ignoreEmptyChildIterators is true.

To enforce that two child selectors use the same entity or value efficiently, use mimic selection, not move filtering.

A Selector's cacheType determines when a selection (such as a Move, an entity, a value, …​) is created and how long it lives.

Almost every Selector supports setting a cacheType:

The following cacheTypes are supported:

A cacheType can be set on composite selectors too:

Nested selectors of a cached selector cannot be configured to be cached themselves, unless it’s a higher cacheType. For example: a STEP cached unionMoveSelector can contain a PHASE cached changeMoveSelector, but it cannot contain a STEP cached changeMoveSelector.

A Selector's selectionOrder determines the order in which the selections (such as Moves, entities, values, …​) are iterated. An optimization algorithm will usually only iterate through a subset of its MoveSelector's selections, starting from the start, so the selectionOrder is critical to decide which Moves are actually evaluated.

Almost every Selector supports setting a selectionOrder:

The following selectionOrders are supported:

A selectionOrder can be set on composite selectors too.

There can be certain moves that you don’t want to select, because:

If a move is unaccepted by the filter, it’s not executed and the score isn’t calculated.

Filtering uses the interface SelectionFilter:

Implement the accept method to return false on a discarded selection (see below). Filtered selection can happen on any Selector in the selector tree, including any MoveSelector, EntitySelector or ValueSelector. It works with any cacheType and selectionOrder.

Sorted selection can happen on any Selector in the selector tree, including any MoveSelector, EntitySelector or ValueSelector. It does not work with cacheType JUST_IN_TIME and it only works with selectionOrder SORTED.

It’s mostly used in construction heuristics.

Probabilistic selection can happen on any Selector in the selector tree, including any MoveSelector, EntitySelector or ValueSelector. It does not work with cacheType JUST_IN_TIME and it only works with selectionOrder PROBABILISTIC.

Each selection has a probabilityWeight, which determines the chance that selection will be selected:

Assume the following entities: lesson A (probabilityWeight 2.0), lesson B (probabilityWeight 0.5) and lesson C (probabilityWeight 0.5). Then lesson A will be selected four times more than B and C.

Selecting all possible moves sometimes does not scale well enough, especially for construction heuristics, which don’t support acceptedCountLimit.

To limit the number of selected selection per step, apply a selectedCountLimit on the selector:

During mimic selection, one normal selector records its selection and one or multiple other special selectors replay that selection. The recording selector acts as a normal selector and supports all other configuration properties. A replaying selector mimics the recording selection and supports no other configuration properties.

The recording selector needs an id. A replaying selector must reference a recorder’s id with a mimicSelectorRef:

Mimic selection is useful to create a composite move from two moves that affect the same entity.

Read about nearby selection in the Nearby selection section of the Enterprise Edition manual.

To determine which move types might be missing in your implementation, run a Benchmarker for a short amount of time and configure it to write the best solutions to disk. Take a look at such a best solution: it will likely be a local optima. Try to figure out if there’s a move that could get out of that local optima faster.

If you find one, implement that coarse-grained move, mix it with the existing moves and benchmark it against the previous configurations to see if you want to keep it.

Instead of using the generic Moves (such as ChangeMove) you can also implement your own Move. Generic and custom MoveSelectors can be combined as desired.

A custom Move can be tailored to work to the advantage of your constraints. For example, in examination scheduling, changing the period of an exam A would also change the period of all the other exams that need to coincide with exam A.

A custom Move is far more work to implement and much harder to avoid bugs than a generic Move. After implementing a custom Move, turn on environmentMode TRACED_FULL_ASSERT to check for score corruptions.

All moves implement the Move interface:

To implement a custom move, it’s recommended to extend AbstractMove instead implementing Move directly. Timefold Solver calls AbstractMove.doMove(ScoreDirector), which calls doMoveOnGenuineVariables(ScoreDirector). For example, in school timetabling, this move changes one lesson to another timeslot:

The implementation must notify the ScoreDirector of any changes it makes to planning entity’s variables: Call the scoreDirector.beforeVariableChanged(Object, String) and scoreDirector.afterVariableChanged(Object, String) methods directly before and after modifying an entity’s planning variable.

The example move above is a fine-grained move because it changes only one planning variable. On the other hand, a coarse-grained move changes multiple entities or multiple planning variables in a single move, usually to avoid breaking hard constraints by making multiple related changes at once. For example, a swap move is really just two change moves, but it keeps those two changes together.

Timefold Solver automatically filters out non doable moves by calling the isMoveDoable(ScoreDirector) method on each selected move. A non doable move is:

In the school timetabling example, a move which assigns a lesson to the timeslot it’s already assigned to is not doable:

We don’t need to check if toTimeslot is in the value range, because we only generate moves for which that is the case. A move that is currently not doable can become doable when the working solution changes in a later step, otherwise we probably shouldn’t have created it in the first place.

Each move has an undo move: a move which does the exact opposite. The users do not need to implement this move, as the solver is smart enough to know what to undo based on the move that was done.

A solver phase might do and undo the same Move more than once. In fact, many solver phases will iteratively do and undo a number of moves to evaluate them, before selecting one of those and doing that move again (without undoing it the last time).

Always implement the toString() method to keep Timefold Solver’s logs readable. Keep it non-verbose and make it consistent with the generic moves:

Optionally, implement the getSimpleMoveTypeDescription() method to support picked move statistics:

Now, let’s generate instances of this custom Move class. There are 2 ways: