JBoss.org Community Documentation

- Prev
- Next

## Chapter 5. Optimization algorithms

## 5.1. Introduction

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

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

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

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

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

An optimization algorithm that checks every possible solution (even with pruning) can easily run for billions of years on a single real-life planning problem. Most of the time, we are happy with a feasible solution found in a limited amount of time.

The combination of Drools Planner's optimization algorithms and the Drools Expert rule engine turn 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.

Drools Planner's implementation combines both. On top of that, it also offers additional support for benchmarking, etc.

## 5.2. Algorithms overview

todo

## 5.3. `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><!-- Let the next phase 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.4. 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 like this as this involves little or no 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:

1. First Fit Decreasing

2. Tabu search (use property tabu 5 or move tabu 7)

At this point the free lunch is over. The result is probably more than good enough, but we can do better. Use the Benchmarker and try a couple of simulated annealing configurations:

1. First Fit Decreasing

2. Simulated annealing (try several starting temperatures)

And try this too:

1. First Fit Decreasing

2. Simulated annealing (relatively long time)

3. Tabu search (relatively short time)

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