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

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.

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:

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

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, implement moves and add tabu search behind it:

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:

And combine them with tabu search:

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

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.

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

<solver>
  ...
  <constructionHeuristic>
    ... <!-- Phase 1: First Fit decreasing -->
  </constructionHeuristic>
  <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.

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

    <termination>

        <maximumTimeMillisSpend>500</maximumTimeMillisSpend>

    </termination>

    <termination>

        <maximumSecondsSpend>10</maximumSecondsSpend>

    </termination>

    <termination>

        <maximumMinutesSpend>5</maximumMinutesSpend>

    </termination>

    <termination>

        <maximumHoursSpend>1</maximumHoursSpend>

    </termination>

    <termination>

        <scoreAttained>0</scoreAttained>

    </termination>

    <termination>

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

    </termination>

    <termination>

        <maximumStepCount>100</maximumStepCount>

    </termination>

    <termination>

        <maximumUnimprovedStepCount>100</maximumUnimprovedStepCount>

    </termination>

    <termination>

        <terminationCompositionStyle>OR</terminationCompositionStyle>

        <maximumStepCount>100</maximumStepCount>

        <scoreAttained>0</scoreAttained>

    </termination>

    <termination>

        <terminationCompositionStyle>AND</terminationCompositionStyle>

        <maximumUnimprovedStepCount>5</maximumUnimprovedStepCount>

        <scoreAttained>-100</scoreAttained>

    </termination>

public interface Solver {


    // ...


    boolean terminateEarly();

    boolean isTerminateEarly();


}

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.

Implement the CustomSolverPhaseCommand interface:

public interface CustomSolverPhaseCommand {

    void changeWorkingSolution(SolutionDirector solutionDirector);

}

For example:

public class ExaminationSolutionInitializer 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();
                ...
            }
            ...
        }
    }

}

And configure it like this:

<solver>
  ...
  <customSolverPhase>
    <customSolverPhaseCommandClass>org.drools.planner.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.