## Chapter 6. Optimization algorithms

6.1. Search space size in the real world
6.2. Does Planner find the optimal solution?
6.3. Architecture overview
6.4. Optimization algorithms overview
6.5. Which optimization algorithms should I use?
6.6. Solver phase
6.7. Scope overview
6.8. Termination
6.8.1. TimeMillisSpentTermination
6.8.2. UnimprovedTimeMillisSpentTermination
6.8.3. BestScoreTermination
6.8.4. BestScoreFeasibleTermination
6.8.5. StepCountTermination
6.8.6. UnimprovedStepCountTermination
6.8.7. Combining multiple Terminations
6.8.8. Asynchronous termination from another thread
6.9. SolverEventListener
6.10. Custom solver phase

## 6.1. Search space size in the real world

The number of possible solutions for a planning problem can be mind blowing. For example:

For comparison: the minimal number of atoms in the known universe (10^80). As a planning problem gets bigger, the search space tends to blow up really fast. Adding only 1 extra planning entity or planning value can heavily multiply the running time of some algorithms.

Calculating the number of possible solutions depends on the design of the domain model:

An algorithm that checks every possible solution (even with pruning such as in Branch And Bound) can easily run for billions of years on a single real-life planning problem. What we really want is to find the best solution in the limited time at our disposal. Planning competitions (such as the International Timetabling Competition) show that Local Search variations (Tabu Search, Simulated Annealing, Late Acceptance, ...) usually perform best for real-world problems given real-world time limitations.

## 6.2. Does Planner find the optimal solution?

The business wants the optimal solution, but they also have other requirements:

The nature of NP-complete problems make scaling a prime concern. The result quality of a small dataset guarantees nothing about the result quality of a large dataset. Scaling issues cannot be mitigated by hardware purchases later on. Start testing with a production sized dataset as soon as possible. Don't assess quality on small datasets (unless production encounters only such datasets). Instead, solve a production sized dataset and compare the results of longer executions, different algorithms and - if available - the human planner.

## 6.5. Which optimization algorithms should I use?

The best optimization algorithms configuration for your use case depends heavily on your use case. Nevertheless, this vanilla recipe will get you into the game with a pretty good configuration, probably much better than what you're used to.

Start with a quick configuration that involves little or no configuration and optimization code:

Next, implement planning entity difficulty comparison and turn it into:

Next, add Late Acceptance behind it:

1. First Fit Decreasing

2. Late Acceptance. A Late Acceptance size of 400 usually works well.

At this point the free lunch is over. The return on invested time lowers. The result is probably already more than good enough.

But you can do even better, at a lower return on invested time. Use the Benchmarker and try a couple of different Tabu Search, Simulated Annealing and Late Acceptance configurations, for example:

1. First Fit Decreasing

2. Tabu Search. An entity tabu size of 7 usually works well.

Use the Benchmarker to improve the values for those size parameters.

If it's worth your time, continue experimenting further. For example, try combining multiple algorithms together:

1. First Fit Decreasing

2. Late Acceptance (relatively long time)

3. Tabu Search (relatively short time)

## 6.6. Solver phase

A `Solver` can use multiple optimization algorithms in sequence. Each optimization algorithm is represented by a solver `Phase`. There is never more than 1 `Phase` solving at the same time.

Here's a configuration that runs 3 phases in sequence:

``````<solver>
...
<constructionHeuristic>
... <!-- First phase: First Fit Decreasing -->
</constructionHeuristic>
<localSearch>
... <!-- Second phase: Late Acceptance -->
</localSearch>
<localSearch>
... <!-- Third phase: Tabu Search -->
</localSearch>
</solver>``````

The solver phases are run in the order defined by solver configuration. When the first `Phase` terminates, the second `Phase` starts, and so on. When the last `Phase` terminates, the `Solver` terminates. Usually, a `Solver` will first run a construction heuristic and then run 1 or multiple metaheuristics:

Some phases (especially construction heuristics) will terminate automatically. Other phases (especially metaheuristics) will only terminate if the `Phase` is configured to terminate:

``````<solver>
...
<termination><!-- Solver termination -->
<secondsSpentLimit>90</secondsSpentLimit>
</termination>
<localSearch>
<termination><!-- Phase termination -->
<secondsSpentLimit>60</secondsSpentLimit><!-- Give the next phase a chance to run too, before the Solver terminates -->
</termination>
...
</localSearch>
<localSearch>
...
</localSearch>
</solver>``````

If the `Solver` terminates (before the last `Phase` terminates itself), the current phase is terminated and all subsequent phases won't run.

## 6.7. Scope overview

A solver will iteratively run phases. Each phase will usually iteratively run steps. Each step, in turn, usually iteratively runs moves. These form 4 nested scopes: solver, phase, step and move.

Configure logging to display the log messages of each scope.

## 6.8. Termination

Not all phases terminate automatically and sometimes you don't want to wait that long anyway. A `Solver` can be terminated synchronously by up-front configuration or asynchronously from another thread.

Especially metaheuristic phases will need to be told when to stop solving. This can be because of a number of reasons: the time is up, the perfect score has been reached, ... The only thing you can't depend on, is on finding the optimal solution (unless you know the optimal score), because a metaheuristic algorithm generally doesn't know it when it finds the optimal solution. For real-life problems this doesn't turn out to be much of a problem, because finding the optimal solution could take years, so you'll want to terminate sooner anyway. The only thing that matters is finding the best solution in the available time.

For synchronous termination, configure a `Termination` on a `Solver` or a `Phase` when it needs to stop. You can implement your own `Termination`, but the built-in implementations should suffice for most needs. Every `Termination` can calculate a time gradient (needed for some optimization algorithms), which is a ratio between the time already spent solving and the estimated entire solving time of the `Solver` or `Phase`.

### 6.8.1. TimeMillisSpentTermination

Terminates when an amount of time has been used:

``````  <termination>
<millisecondsSpentLimit>500</millisecondsSpentLimit>
</termination>``````
``````  <termination>
<secondsSpentLimit>10</secondsSpentLimit>
</termination>``````
``````  <termination>
<minutesSpentLimit>5</minutesSpentLimit>
</termination>``````
``````  <termination>
</termination>``````

### 6.8.2. UnimprovedTimeMillisSpentTermination

Terminates when the best score hasn't improved in an amount of time:

``````  <localSearch>
<termination>
<unimprovedMillisecondsSpentLimit>500</unimprovedMillisecondsSpentLimit>
</termination>
</localSearch>``````
``````  <localSearch>
<termination>
<unimprovedSecondsSpentLimit>10</unimprovedSecondsSpentLimit>
</termination>
</localSearch>``````
``````  <localSearch>
<termination>
<unimprovedMinutesSpentLimit>5</unimprovedMinutesSpentLimit>
</termination>
</localSearch>``````
``````  <localSearch>
<termination>
</termination>
</localSearch>``````

This termination should not be applied to Construction Heuristics, because they only update the best solution at the end. Therefore it might be better to configure it on a specific `Phase` (such as `<localSearch>`), instead of on the `Solver` itself.

### 6.8.3. BestScoreTermination

``````  <termination>
<bestScoreLimit>0</bestScoreLimit>
</termination>``````

For a planning problem with a HardSoftScore, it could look like this:

``````  <termination>
<bestScoreLimit>0hard/-5000soft</bestScoreLimit>
</termination>``````

For a planning problem with a BendableScore with 3 hard levels and 1 soft level, it could look like this:

``````  <termination>
<bestScoreLimit>0/0/0/-5000</bestScoreLimit>
</termination>``````

To terminate once a feasible solution has been reached, this `Termination` isn't practical because it requires a `bestScoreLimit` such as `0hard/-2147483648soft`. Instead, use the next termination.

### 6.8.4. BestScoreFeasibleTermination

Terminates when a certain score is feasible. Requires that the `Score` implementation implements `FeasibilityScore`.

``````  <termination>
<bestScoreFeasible>true</bestScoreFeasible>
</termination>``````

This `Termination` is usually combined with other terminations.

### 6.8.5. StepCountTermination

Terminates when an amount of steps has been reached:

``````  <localSearch>
<termination>
<stepCountLimit>100</stepCountLimit>
</termination>
</localSearch>``````

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

### 6.8.7. Combining multiple Terminations

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

``````  <termination>
<terminationCompositionStyle>OR</terminationCompositionStyle>
<stepCountLimit>100</stepCountLimit>
<bestScoreLimit>0</bestScoreLimit>
</termination>``````

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

``````  <termination>
<terminationCompositionStyle>AND</terminationCompositionStyle>
<unimprovedStepCountLimit>5</unimprovedStepCountLimit>
<bestScoreLimit>-100</bestScoreLimit>
</termination>``````

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

## 6.9. SolverEventListener

Each time a new best solution is found, the `Solver` fires a `BestSolutionChangedEvent`, in the solver's thread.

To listen to such events, add a `SolverEventListener` to the `Solver`:

``````public interface Solver {

// ...

void addEventListener(SolverEventListener<? extends Solution> eventListener);
void removeEventListener(SolverEventListener<? extends Solution> eventListener);

}``````

The `BestSolutionChangedEvent`'s `newBestSolution` might not be initialized or feasible. Use the methods on `BestSolutionChangedEvent` to detect such cases:

``````    solver.addEventListener(new SolverEventListener<CloudBalance>() {
public void bestSolutionChanged(BestSolutionChangedEvent<CloudBalance> event) {
// Ignore invalid solutions
if (event.isNewBestSolutionInitialized()
&& event.getNewBestSolution().getScore().isFeasible()) {
...
}
}
});``````

## 6.10. Custom solver phase

Between phases or before the first phase, you might want to execute a custom action on the `Solution` to get a better score. Yet you'll still want to reuse the score calculation. For example, to implement a custom construction heuristic without implementing an entire `Phase`.

## Note

Most of the time, a custom construction heuristic is not worth the hassle. The supported constructions heuristics are configurable (use the Benchmarker to tweak them), `Termination` aware and support partially initialized solutions too.

Implement the `CustomPhaseCommand` interface:

``````public interface CustomPhaseCommand {

void changeWorkingSolution(ScoreDirector scoreDirector);

}``````

For example:

``````public class ToOriginalMachineSolutionInitializer implements CustomPhaseCommand {

public void changeWorkingSolution(ScoreDirector scoreDirector) {
MachineReassignment machineReassignment = (MachineReassignment) scoreDirector.getWorkingSolution();
for (MrProcessAssignment processAssignment : machineReassignment.getProcessAssignmentList()) {
scoreDirector.beforeVariableChanged(processAssignment, "machine");
processAssignment.setMachine(processAssignment.getOriginalMachine());
scoreDirector.afterVariableChanged(processAssignment, "machine");
}
}

}``````

## Warning

Any change on the planning entities in a `CustomPhaseCommand` must be notified to the `ScoreDirector`.

## Warning

Do not change any of the planning facts in a `CustomPhaseCommand`. That will corrupt the `Solver` because any previous score or solution was for a different problem. To do that, read about repeated planning and do it with a ProblemFactChange instead.

Configure your `CustomPhaseCommand` like this:

``````<solver>
...
<customPhase>
<customPhaseCommandClass>org.optaplanner.examples.machinereassignment.solver.solution.initializer.ToOriginalMachineSolutionInitializer</customPhaseCommandClass>
</customPhase>
... <!-- Other phases -->
</solver>``````

Configure multiple `customPhaseCommandClass` instances to run them in sequence.

## Important

If the changes of a `CustomPhaseCommand` don't result in a better score, the best solution won't be changed (so effectively nothing will have changed for the next `Phase` or `CustomPhaseCommand`). To force such changes anyway, use `forceUpdateBestSolution`:

``````  <customPhase>
<customPhaseCommandClass>...MyUninitializer</customPhaseCommandClass>
<forceUpdateBestSolution>true</forceUpdateBestSolution>
</customPhase>``````

## Note

If the `Solver` or a `Phase` wants to terminate while a `CustomPhaseCommand` is still running, it will wait to terminate until the `CustomPhaseCommand` is done, however long that takes.