JBoss.org Community Documentation

- Prev
- Next

## Chapter 5. Optimization algorithms

## 5.1. The size of real world problems

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

## 5.2. The secret sauce of Drools Planner

Drools Planner 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 make 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 suited to use 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.

## 5.3. Optimization algorithms overview

Table 5.1. Optimization algorithms overview

Algorithm | Scalable? | Optimal solution? | Needs little configuration? | Highly configurable? | Requires initialized solution?
--- | --- | --- | --- | --- | ---
Exact algorithms |  |  |  |  |
Brute force | 0/5 | 5/5 - Guaranteed | 5/5 | 0/5 | No
Branch and bound | 0/5 | 5/5 - Guaranteed | 4/5 | 1/5 | No
Construction heuristics |  |  |  |  |
First Fit | 5/5 | 1/5 - Stops after initialization | 5/5 | 1/5 | No
First Fit Decreasing | 5/5 | 2/5 - Stops after initialization | 4/5 | 2/5 | No
Best Fit | 5/5 | 2/5 - Stops after initialization | 4/5 | 2/5 | No
Best Fit Decreasing | 5/5 | 2/5 - Stops after initialization | 4/5 | 2/5 | No
Cheapest Insertion | 3/5 | 2/5 - Stops after initialization | 5/5 | 2/5 | No
Metaheuristics |  |  |  |  |
Local search |  |  |  |  |
Hill-climbing | 4/5 | 2/5 - Gets stuck in local optima | 3/5 | 3/5 | Yes
Tabu search | 4/5 | 4/5 | 3/5 | 5/5 | Yes
Simulated annealing | 4/5 | 4/5 | 2/5 | 5/5 | Yes
Evolutionary algorithms |  |  |  |  |
Evolutionary strategies | 4/5 | ?/5 | ?/5 | ?/5 | Yes
Genetic algorithms | 4/5 | ?/5 | ?/5 | ?/5 | Yes

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

## 5.4. `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 property tabu.

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

    <solver>
      ...
      <customSolverPhase><!-- Phase 1 -->
        ... <!-- custom construction heuristic -->
      </customSolverPhase>
      <localSearch><!-- Phase 2 -->
        ... <!-- simulated annealing -->
      </localSearch>
      <localSearch><!-- Phase 3 -->
        ... <!-- Tabu search -->
      </localSearch>
    </solver>

When the first phase terminates, the second phase starts, and so on. When the last phase terminates, the `Solver` terminates.

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.

## 5.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 property tabu or move 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 configurations:

1. First Fit Decreasing

2. Simulated annealing (try several starting temperatures)

And combine them with tabu search:

1. First Fit Decreasing

2. Simulated annealing (relatively long time)

3. Tabu search (relatively short time)

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

## 5.6. Logging level: What is the `Solver` doing?

The best way to illuminate the black box that is a `Solver`, is to play with the logging level:

- WARN: Log only when things go wrong.

- INFO: Log every phase and the solver itself.

- DEBUG: Log every step of every phase.

- TRACE: Log every move of every step of every phase.

Set the logging level on the category `org.drools.planner`, for example with log4j:

    <log4j:configuration xmlns:log4j="http://jakarta.apache.org/log4j/">

        <category name="org.drools.planner">
            <priority value="debug" />
        </category>

        ...

    </log4j:configuration>

For example, set it to `DEBUG` logging, to see when the phases end and how fast steps are taken:

    INFO  Solver started: time spend (0), score (null), new best score (null), random seed (0).
    DEBUG     Step index (0), time spend (1), score (0), initialized planning entity (2 @ 0).
    DEBUG     Step index (1), time spend (3), score (0), initialized planning entity (1 @ 2).
    DEBUG     Step index (2), time spend (4), score (0), initialized planning entity (3 @ 3).
    DEBUG     Step index (3), time spend (5), score (-1), initialized planning entity (0 @ 1).
    INFO  Phase construction heuristic finished: step total (4), time spend (6), best score (-1).
    DEBUG     Step index (0), time spend (10), score (-1),     best score (-1), accepted move size (12) for picked step (1 @ 2 => 3).
    DEBUG     Step index (1), time spend (12), score (0), new best score (0), accepted move size (12) for picked step (3 @ 3 => 2).
    INFO  Phase local search finished: step total (2), time spend (13), best score (0).
    INFO  Solved: time spend (13), best score (0), average calculate count per second (4846).

All time spends are in milliseconds.

## 5.7. 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(SolutionDirector solutionDirector);

    }

For example:

    public class ExaminationStartingSolutionInitializer implements CustomSolverPhaseCommand {

        public void changeWorkingSolution(SolutionDirector solutionDirector) {
            Examination examination = (Examination) solutionDirector.getWorkingSolution();
            for (Exam exam : examination.getExamList()) {
                Score unscheduledScore = solutionDirector.calculateScoreFromWorkingMemory();
                ...
                for (Period period : examination.getPeriodList()) {
                    exam.setPeriod(period)
                    workingMemory.update(examHandle, exam);
                    Score score = solutionDirector.calculateScoreFromWorkingMemory();
                    ...
                }
                ...
            }
        }

    }

## Warning

Any change on the planning entities in a `CustomSolverPhaseCommand` must be told to the `WorkingMemory` of `solutionDirector.getWorkingMemory()`.

## 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 the section about Real-time planning instead.

And configure it like this:

    <solver>
      ...
      <customSolverPhase>
        <customSolverPhaseCommandClass>org.drools.planner.examples.examination.solver.solution.initializer.ExaminationStartingSolutionInitializer</customSolverPhaseCommandClass>
      </customSolverPhase>
      ... <!-- Other phases -->
    </solver>

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

## Note

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`). TODO: we might want to change this behaviour?

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

- PrevChapter 4. Score calculation with a rule engine
- Top of page
- Front page
- NextChapter 6. Exact methods