JBoss.org Community Documentation

- Prev
- Next

## Chapter 6. Optimization algorithms

## 6.1. Search space size in the real world

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

- 4 queens has `256` possible solutions (`4 ^ 4`) and 2 optimal solutions.

- 5 queens has `3125` possible solutions (`5 ^ 5`) and 1 optimal solution.

- 8 queens has `16777216` possible solutions (`8 ^ 8`) and 92 optimal solutions.

- 64 queens has more than `10^115` possible solutions (`64 ^ 64`).

- Most real-life planning problems have an incredible number of possible solutions and only 1 or a few optimal solutions.

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.

An algorithm that checks every possible solution (even with pruning) 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, ...) 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:

- Scale out: Large production datasets must not crash and have good results too.

- Optimize the right problem: The constraints must match the actual business needs.

- Available time: The solution must be found in time, before it becomes useless to execute.

- Reliability: Every dataset must have at least a decent result (better than a human planner).

Given these requirements, and despite the promises of some salesmen, it's usually impossible for anyone or anything to find the optimal solution. Therefore, Planner focuses on finding the best solution in available time. In realistic, independent competitions, Planner often comes out as the best reusable software.

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 problems cannot be mitigated by hardware purchases. Start testing with a production sized dataset as soon as possible. Don't asses quality on small datasets (unless production encounters such datasets). Instead, solve a production sized dataset and compare with the results of longer execution, different algorithms and - if available - the human planner.

## 6.3. Architecture overview

OptaPlanner is the first framework to combine optimization algorithms (metaheuristics, ...) with score calculation by a rule engine such as Drools Expert. This combination turns out to be a very efficient, because:

- A rule engine such as Drools Expert is great for calculating the score of a solution of a planning problem. It makes it easy and scalable to add additional soft or hard constraints such as "a teacher shouldn't teach more then 7 hours a day". It does delta based score calculation without any extra code. However it tends to be not suitable to actually find new solutions.

- An optimization algorithm is great at finding new improving solutions for a planning problem, without necessarily brute-forcing every possibility. However it needs to know the score of a solution and offers no support in calculating that score efficiently.

## 6.4. Optimization algorithms overview

Table 6.1. Optimization algorithms overview

Algorithm | Scalable? | Optimal? | Easy to use? | Tweakable? | Requires CH?
--- | --- | --- | --- | --- | ---
Exact algorithms |  |  |  |  |
Brute force | 0/5 | 5/5 | 5/5 | 0/5 | No
Branch and bound | 0/5 | 5/5 | 4/5 | 1/5 | No
Construction heuristics (CH) |  |  |  |  |
First Fit | 5/5 | 1/5 | 5/5 | 1/5 | No
First Fit Decreasing | 5/5 | 2/5 | 4/5 | 2/5 | No
Best Fit | 5/5 | 2/5 | 4/5 | 2/5 | No
Best Fit Decreasing | 5/5 | 2/5 | 4/5 | 2/5 | No
Cheapest Insertion | 3/5 | 2/5 | 5/5 | 2/5 | No
Metaheuristics (MH) |  |  |  |  |
Local Search |  |  |  |  |
Hill-Climbing | 5/5 | 2/5 | 4/5 | 3/5 | Yes
Tabu Search | 5/5 | 4/5 | 3/5 | 5/5 | Yes
Simulated Annealing | 5/5 | 4/5 | 2/5 | 5/5 | Yes
Late Acceptance | 5/5 | 4/5 | 3/5 | 5/5 | Yes
Late Simulated Annealing | 5/5 | 4/5 | 3/5 | 5/5 | Yes
Evolutionary Algorithms |  |  |  |  |
Evolutionary Strategies | 4/5 | 3/5 | ?/5 | ?/5 | Yes
Genetic Algorithms | 4/5 | 3/5 | ?/5 | ?/5 | Yes

If you want to learn more about metaheuristics, read the free book Essentials of Metaheuristics or Clever Algorithms.

## 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:

1. First Fit

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

1. First Fit Decreasing

Next, implement moves and add tabu search behind it:

1. First Fit Decreasing

2. Tabu Search (use planning entity tabu)

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 Simulated Annealing or Late Acceptance configurations, for example:

1. First Fit Decreasing

2. Late Acceptance (try several sizes)

And combine them with Tabu Search:

1. First Fit Decreasing

2. Late Acceptance (relatively long time)

3. Tabu Search (relatively short time)

If you have time, continue experimenting even further. Blog about your experiments!

## 6.6. `SolverPhase`

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

## Note

Some `SolverPhase` implementations can combine techniques from multiple optimization algorithms, but they are still just 1 `SolverPhase`. For example: a local search `SolverPhase` can do simulated annealing with planning entity tabu.

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

    <solver>

      ...

      <constructionHeuristic>

        ... <!-- First phase: First Fit Decreasing -->

      </constructionHeuristic>

      <localSearch>

        ... <!-- Second phase: Simulated Annealing -->

      </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 -->

        <maximumSecondsSpend>90</maximumSecondsSpend>

      </termination>

      <localSearch>

        <termination><!-- Phase termination -->

          <maximumSecondsSpend>60</maximumSecondsSpend><!-- 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 billions of 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 `SolverPhase` when it needs to stop. You can implement your own `Termination`, but the build-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 spend solving and the estimated entire solving time of the `Solver` or `SolverPhase`.

### 6.8.1. TimeMillisSpendTermination

Terminates when an amount of time has been reached:

        <termination>

            <maximumTimeMillisSpend>500</maximumTimeMillisSpend>

        </termination>

        <termination>

            <maximumSecondsSpend>10</maximumSecondsSpend>

        </termination>

        <termination>

            <maximumMinutesSpend>5</maximumMinutesSpend>

        </termination>

        <termination>

            <maximumHoursSpend>1</maximumHoursSpend>

        </termination>

## Note

If you use this `Termination`, you will most likely sacrifice perfect reproducibility (even with `environmentMode` `REPRODUCIBLE`) because of an available CPU time difference:

- The available CPU time influences the number of steps that can be taken, which might be a few more or less.

- The `Termination` might produce slightly different time gradient values, which will send time gradient based algorithms (such as simulated annealing) on a radically different path.

### 6.8.2. ScoreAttainedTermination

Terminates when a certain score has been reached. You can use this `Termination` if you know the perfect score, for example for 4 queens:

        <termination>

            <scoreAttained>0</scoreAttained>

        </termination>

For a planning problem with hard and soft constraints, it could look like this:

        <termination>

            <scoreAttained>0hard/-5000soft</scoreAttained>

        </termination>

You can use this `Termination` to terminate once it reaches a feasible solution.

### 6.8.3. StepCountTermination

Terminates when an amount of steps has been reached:

        <termination>

            <maximumStepCount>100</maximumStepCount>

        </termination>

This `Termination` can only be used for a `SolverPhase`, not for the `Solver` itself.

### 6.8.4. UnimprovedStepCountTermination

Terminates when the best score hasn't improved in a number of steps:

        <termination>

            <maximumUnimprovedStepCount>100</maximumUnimprovedStepCount>

        </termination>

If the score hasn't improved recently, it's probably not going to improve soon anyway and it's not worth the effort to continue. We have observed that once a new best solution is found (even after a long time of no improvement on the best solution), the next few steps tend to improve the best solution too.

This `Termination` can only be used for a `SolverPhase`, not for the `Solver` itself.

### 6.8.5. 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>

            <maximumStepCount>100</maximumStepCount>

            <scoreAttained>0</scoreAttained>

        </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>

            <maximumUnimprovedStepCount>5</maximumUnimprovedStepCount>

            <scoreAttained>-100</scoreAttained>

        </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.8.6. Asynchronous termination from another thread

Sometimes you'll want to terminate a Solver early from another thread, for example because a user action or a server restart. This cannot be configured by a `Termination` as it's impossible to predict when and if it will occur. Therefore the `Solver` interface has these 2 thread-safe methods:

    public interface Solver {

        // ...

        boolean terminateEarly();

        boolean isTerminateEarly();

    }

If you call the `terminateEarly()` method from another thread, the `Solver` will terminate at its earliest convenience and the `solve()` method will return in the original `Solver` thread.

## 6.9. SolverEventListener

Each time a new best solution is found, the `Solver` fires a `BestSolutionChangedEvent`.

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

    public interface Solver {

        // ...

        void addEventListener(SolverEventListener eventListener);

        void removeEventListener(SolverEventListener eventListener);

    }

## 6.10. Custom SolverPhase

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 `SolverPhase`.

## Note

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

Implement the `CustomSolverPhaseCommand` interface:

    public interface CustomSolverPhaseCommand {

        void changeWorkingSolution(ScoreDirector scoreDirector);

    }

For example:

    public class ExaminationSolutionInitializer implements CustomSolverPhaseCommand {

        public void changeWorkingSolution(ScoreDirector scoreDirector) {

            Examination examination = (Examination) scoreDirector.getWorkingSolution();

            for (Exam exam : examination.getExamList()) {

                Score unscheduledScore = scoreDirector.calculateScore();

                ...

                for (Period period : examination.getPeriodList()) {

                    scoreDirector.beforeVariableChanged(exam, "period");

                    exam.setPeriod(period)

                    scoreDirector.afterVariableChanged(exam, "period");

                    Score score = scoreDirector.calculateScore();

                    ...

                }

                ...

            }

        }

    }

## Warning

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

## Warning

Do not change any of the planning facts in a `CustomSolverPhaseCommand`. That will corrupt the `Solver` because any previous score or solution was for a different problem. If you want to do that, see repeated planning and real-time planning instead.

And configure it like this:

    <solver>

      ...

      <customSolverPhase>

        <customSolverPhaseCommandClass>org.optaplanner.examples.examination.solver.solution.initializer.ExaminationSolutionInitializer</customSolverPhaseCommandClass>

      </customSolverPhase>

      ... <!-- Other phases -->

    </solver>

It's possible to configure multiple `customSolverPhaseCommandClass` instances, which will be run in sequence.

## Important

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

      <customSolverPhase>

        <customSolverPhaseCommandClass>...MyUninitializer</customSolverPhaseCommandClass>

        <forceUpdateBestSolution>true</forceUpdateBestSolution>

      </customSolverPhase>

## Note

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

- PrevChapter 5. Score calculation
- Top of page
- Front page
- NextChapter 7. Move and neighborhood selection