Chapter 6. Optimization Algorithms

The 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 is 10⁸⁰. 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.

Calculating the number of possible solutions depends on the design of the domain model:

An algorithm that checks every possible solution (even with pruning such as in Branch And Bound) 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, Late Acceptance, …​) usually perform best for real-world problems given real-world time limitations.

The business wants the optimal solution, but they also have other requirements:

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, it often comes out as the best reusable software.

The nature of NP-complete problems makes scaling a prime concern. The result quality of a small dataset guarantees nothing about the result quality of a large dataset. Scaling issues cannot be mitigated by hardware purchases later on. Start testing with a production sized dataset as soon as possible. Don’t assess quality on small datasets (unless production encounters only such datasets). Instead, solve a production sized dataset and compare the results of longer executions, different algorithms and—​if available—​the human planner.

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:

Planner supports 3 families of optimization algorithms: Exhaustive Search, Construction Heuristics and Metaheuristics. In practice, Metaheuristics (in combination with Construction Heuristics to initialize) are the recommended choice:

Each of these families of algorithms has multiple optimization algorithms:

If you want to learn more about metaheuristics, read the free books 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, add Late Acceptance 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 different Tabu Search, Simulated Annealing and Late Acceptance configurations, for example:

Use the Benchmarker to improve the values for those size parameters.

If it’s worth your time, continue experimenting further. For example, try combining multiple algorithms together:

Many optimization algorithms have parameters which affect results and scalability. Planner applies configuration by exception, so all optimization algorithms have default parameter values. This is very similar to the Garbage Collection parameters in a JVM: most users have no need to tweak them, but power users do tweak them.

The default parameter values are good enough for many cases (and especially for prototypes), but if development time allows, it can be well worth to power tweak them with the benchmarker for better results and scalability on a specific use case. The documentation for each optimization algorithm also declares its advanced configuration for power tweaking.

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

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

<solver>
  ...
  <constructionHeuristic>
    ... <!-- First phase: First Fit Decreasing -->
  </constructionHeuristic>
  <localSearch>
    ... <!-- Second phase: Late Acceptance -->
  </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:

If no phases are configured, Planner will default to a Construction Heuristic phase followed by a Local Search phase.

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 -->
    <secondsSpentLimit>90</secondsSpentLimit>
  </termination>
  <localSearch>
    <termination><!-- Phase termination -->
      <secondsSpentLimit>60</secondsSpentLimit><!-- 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.

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.

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, just before its solution is used, …​ 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 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 Phase when it needs to stop. You can implement your own Termination, but the built-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 spent solving and the estimated entire solving time of the Solver or Phase.

  <termination>
    <millisecondsSpentLimit>500</millisecondsSpentLimit>
  </termination>

  <termination>
    <secondsSpentLimit>10</secondsSpentLimit>
  </termination>

  <termination>
    <minutesSpentLimit>5</minutesSpentLimit>
  </termination>

  <termination>
    <hoursSpentLimit>1</hoursSpentLimit>
  </termination>

  <termination>
    <daysSpentLimit>2</daysSpentLimit>
  </termination>

  <termination>
    <minutesSpentLimit>150</minutesSpentLimit>
  </termination>

  <termination>
    <hoursSpentLimit>2</hoursSpentLimit>
    <minutesSpentLimit>30</minutesSpentLimit>
  </termination>

  <localSearch>
    <termination>
      <unimprovedMillisecondsSpentLimit>500</unimprovedMillisecondsSpentLimit>
    </termination>
  </localSearch>

  <localSearch>
    <termination>
      <unimprovedSecondsSpentLimit>10</unimprovedSecondsSpentLimit>
    </termination>
  </localSearch>

  <localSearch>
    <termination>
      <unimprovedMinutesSpentLimit>5</unimprovedMinutesSpentLimit>
    </termination>
  </localSearch>

  <localSearch>
    <termination>
      <unimprovedHoursSpentLimit>1</unimprovedHoursSpentLimit>
    </termination>
  </localSearch>

  <localSearch>
    <termination>
      <unimprovedDaysSpentLimit>1</unimprovedDaysSpentLimit>
    </termination>
  </localSearch>

  <termination>
    <bestScoreLimit>0</bestScoreLimit>
  </termination>

  <termination>
    <bestScoreLimit>0hard/-5000soft</bestScoreLimit>
  </termination>

  <termination>
    <bestScoreLimit>0/0/0/-5000</bestScoreLimit>
  </termination>

  <termination>
    <bestScoreFeasible>true</bestScoreFeasible>
  </termination>

  <localSearch>
    <termination>
      <stepCountLimit>100</stepCountLimit>
    </termination>
  </localSearch>

  <localSearch>
    <termination>
      <unimprovedStepCountLimit>100</unimprovedStepCountLimit>
    </termination>
  </localSearch>

  <termination>
    <calculateCountLimit>100000</calculateCountLimit>
  </termination>

  <termination>
    <terminationCompositionStyle>OR</terminationCompositionStyle>
    <stepCountLimit>100</stepCountLimit>
    <bestScoreLimit>0</bestScoreLimit>
  </termination>

  <termination>
    <terminationCompositionStyle>AND</terminationCompositionStyle>
    <unimprovedStepCountLimit>5</unimprovedStepCountLimit>
    <bestScoreLimit>-100</bestScoreLimit>
  </termination>

public interface Solver<S extends Solution> {

    // ...

    boolean terminateEarly();
    boolean isTerminateEarly();

}

Each time a new best solution is found, the Solver fires a BestSolutionChangedEvent, in the solver’s thread.

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

public interface Solver<S extends Solution> {

    // ...

    void addEventListener(SolverEventListener<S> eventListener);
    void removeEventListener(SolverEventListener<S> eventListener);

}

The BestSolutionChangedEvent's newBestSolution might not be initialized or feasible. Use the methods on BestSolutionChangedEvent to detect such cases:

    solver.addEventListener(new SolverEventListener<CloudBalance>() {
        public void bestSolutionChanged(BestSolutionChangedEvent<CloudBalance> event) {
            // Ignore invalid solutions
            if (event.isNewBestSolutionInitialized()
                    && event.getNewBestSolution().getScore().isFeasible()) {
                ...
            }
        }
    });

Between phases or before the first phase, you might want to run a custom optimization algorithm to initialize the Solution or to take some low hanging fruit to get a better score quickly. Yet you’ll still want to reuse the score calculation. For example, to implement a custom Construction Heuristic without implementing an entire Phase.

The CustomPhaseCommand interface looks like this:

public interface CustomPhaseCommand {

    void applyCustomProperties(Map<String, String> customPropertyMap);

    void changeWorkingSolution(ScoreDirector scoreDirector);

}

For example, extend AbstractCustomPhaseCommand and implement the changeWorkingSolution() method:

public class ToOriginalMachineSolutionInitializer extends AbstractCustomPhaseCommand {

    public void changeWorkingSolution(ScoreDirector scoreDirector) {
        MachineReassignment machineReassignment = (MachineReassignment) scoreDirector.getWorkingSolution();
        for (MrProcessAssignment processAssignment : machineReassignment.getProcessAssignmentList()) {
            scoreDirector.beforeVariableChanged(processAssignment, "machine");
            processAssignment.setMachine(processAssignment.getOriginalMachine());
            scoreDirector.afterVariableChanged(processAssignment, "machine");
            scoreDirector.triggerVariableListeners();
        }
    }

}

Configure your CustomPhaseCommand like this:

<solver>
  ...
  <customPhase>
    <customPhaseCommandClass>org.optaplanner.examples.machinereassignment.solver.solution.initializer.ToOriginalMachineSolutionInitializer</customPhaseCommandClass>
  </customPhase>
  ... <!-- Other phases -->
</solver>

Configure multiple customPhaseCommandClass instances to run them in sequence.

  <customPhase>
    <customPhaseCommandClass>...MyUninitializer</customPhaseCommandClass>
    <forceUpdateBestSolution>true</forceUpdateBestSolution>
  </customPhase>

To configure values of your CustomPhaseCommand dynamically in the solver configuration (so you can tweak those parameters with the Benchmarker), use the customProperties element:

  <customPhase>
    <customProperties>
      <mySelectionSize>5</mySelectionSize>
    </customProperties>
  </customPhase>

Then override the applyCustomProperties() method to parse and apply them when a Solver is built.

public class MySolutionInitializer extends AbstractCustomPhaseCommand {

    private int mySelectionSize;

    public void applyCustomProperties(Map<String, String> customPropertyMap) {
        String mySelectionSizeString = customPropertyMap.get("mySelectionSize");
        if (mySelectionSizeString == null) {
            throw new IllegalArgumentException("A customProperty (mySelectionSize) is missing from the solver configuration.");
        }
        solverFactory = SolverFactory.createFromXmlResource(partitionSolverConfigResource);
        if (customPropertyMap.size() != 1) {
            throw new IllegalArgumentException("The customPropertyMap's size (" + customPropertyMap.size() + ") is not 1.");
        }
        mySelectionSize = Integer.parseInt(mySelectionSizeString);
    }

    ...
}