JBoss.orgCommunity Documentation

Chapter 5. Optimization algorithms

5.1. Introduction
5.2. Algorithms overview
5.3. SolverPhase
5.4. Which optimization algorithms should I use?
5.5. Custom SolverPhase

5.1. Introduction

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

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:

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.