Suppose your company owns a number of cloud computers and needs to run a number of processes on those computers. Assign each process to a computer under the following four constraints.

The following hard constraints must be fulfilled:

The following soft constraints should be optimized:

This problem is a form of bin packing. The following is a simplified example, where we assign four processes to two computers with two constraints (CPU and RAM) with a simple algorithm:

The simple algorithm used here is the First Fit Decreasing algorithm, which assigns the bigger processes first and assigns the smaller processes to the remaining space. As you can see, it is not optimal, as it does not leave enough room to assign the yellow process “D”.

Planner does find the more optimal solution fast by using additional, smarter algorithms. It also scales: both in data (more processes, more computers) and constraints (more hardware requirements, other constraints). So see how Planner can be used in this scenario.

Beginning with the domain model:

In the UML class diagram above, the Planner concepts are already annotated:

Try it yourself. Download and configure the examples in your preferred IDE. Run org.optaplanner.examples.cloudbalancing.app.CloudBalancingHelloWorld. By default, it is configured to run for 120 seconds. It will execute this code:

public class CloudBalancingHelloWorld {

    public static void main(String[] args) {
        // Build the Solver
        SolverFactory<CloudBalance> solverFactory = SolverFactory.createFromXmlResource(
                "org/optaplanner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml");
        Solver<CloudBalance> solver = solverFactory.buildSolver();

        // Load a problem with 400 computers and 1200 processes
        CloudBalance unsolvedCloudBalance = new CloudBalancingGenerator().createCloudBalance(400, 1200);

        // Solve the problem
        CloudBalance solvedCloudBalance = solver.solve(unsolvedCloudBalance);

        // Display the result
        System.out.println("\nSolved cloudBalance with 400 computers and 1200 processes:\n"
                + toDisplayString(solvedCloudBalance));
    }

    ...
}

The code example does the following:

The only complicated part is building the Solver, as detailed in the next section.

Take a look at the solver configuration:

<?xml version="1.0" encoding="UTF-8"?>
<solver>
  <!-- Domain model configuration -->
  <scanAnnotatedClasses/>

  <!-- Score configuration -->
  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    <easyScoreCalculatorClass>org.optaplanner.examples.cloudbalancing.solver.score.CloudBalancingEasyScoreCalculator</easyScoreCalculatorClass>
    <!--<scoreDrl>org/optaplanner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>-->
  </scoreDirectorFactory>

  <!-- Optimization algorithms configuration -->
  <termination>
    <secondsSpentLimit>30</secondsSpentLimit>
  </termination>
</solver>

This solver configuration consists of three parts:

Let’s examine the domain model classes and the score configuration.

Planner will search for the Solution with the highest Score. This example uses a HardSoftScore, which means Planner will look for the solution with no hard constraints broken (fulfill hardware requirements) and as little as possible soft constraints broken (minimize maintenance cost).

Of course, Planner needs to be told about these domain-specific score constraints. There are several ways to implement such a score function:

Let’s take a look at two different implementations:

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    <easyScoreCalculatorClass>org.optaplanner.examples.cloudbalancing.solver.score.CloudBalancingEasyScoreCalculator</easyScoreCalculatorClass>
  </scoreDirectorFactory>

public class CloudBalancingEasyScoreCalculator implements EasyScoreCalculator<CloudBalance> {

    /**
     * A very simple implementation. The double loop can easily be removed by using Maps as shown in
     * {@link CloudBalancingMapBasedEasyScoreCalculator#calculateScore(CloudBalance)}.
     */
    public HardSoftScore calculateScore(CloudBalance cloudBalance) {
        int hardScore = 0;
        int softScore = 0;
        for (CloudComputer computer : cloudBalance.getComputerList()) {
            int cpuPowerUsage = 0;
            int memoryUsage = 0;
            int networkBandwidthUsage = 0;
            boolean used = false;

            // Calculate usage
            for (CloudProcess process : cloudBalance.getProcessList()) {
                if (computer.equals(process.getComputer())) {
                    cpuPowerUsage += process.getRequiredCpuPower();
                    memoryUsage += process.getRequiredMemory();
                    networkBandwidthUsage += process.getRequiredNetworkBandwidth();
                    used = true;
                }
            }

            // Hard constraints
            int cpuPowerAvailable = computer.getCpuPower() - cpuPowerUsage;
            if (cpuPowerAvailable < 0) {
                hardScore += cpuPowerAvailable;
            }
            int memoryAvailable = computer.getMemory() - memoryUsage;
            if (memoryAvailable < 0) {
                hardScore += memoryAvailable;
            }
            int networkBandwidthAvailable = computer.getNetworkBandwidth() - networkBandwidthUsage;
            if (networkBandwidthAvailable < 0) {
                hardScore += networkBandwidthAvailable;
            }

            // Soft constraints
            if (used) {
                softScore -= computer.getCost();
            }
        }
        return HardSoftScore.valueOf(hardScore, softScore);
    }

}

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    <scoreDrl>org/optaplanner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>
  </scoreDirectorFactory>

...

import org.optaplanner.examples.cloudbalancing.domain.CloudBalance;
import org.optaplanner.examples.cloudbalancing.domain.CloudComputer;
import org.optaplanner.examples.cloudbalancing.domain.CloudProcess;

global HardSoftScoreHolder scoreHolder;

// ############################################################################
// Hard constraints
// ############################################################################

rule "requiredCpuPowerTotal"
    when
        $computer : CloudComputer($cpuPower : cpuPower)
        $requiredCpuPowerTotal : Number(intValue > $cpuPower) from accumulate(
            CloudProcess(
                computer == $computer,
                $requiredCpuPower : requiredCpuPower),
            sum($requiredCpuPower)
        )
    then
        scoreHolder.addHardConstraintMatch(kcontext, $cpuPower - $requiredCpuPowerTotal.intValue());
end

rule "requiredMemoryTotal"
    ...
end

rule "requiredNetworkBandwidthTotal"
    ...
end

// ############################################################################
// Soft constraints
// ############################################################################

rule "computerCost"
    when
        $computer : CloudComputer($cost : cost)
        exists CloudProcess(computer == $computer)
    then
        scoreHolder.addSoftConstraintMatch(kcontext, - $cost);
end

Now that this simple example works, try going further. Enrich the domain model and add extra constraints such as these:

This example is explained in a tutorial.

Build a Solver instance with the SolverFactory. Configure the SolverFactory with a solver configuration XML file, provided as a classpath resource (as defined by ClassLoader.getResource()):

       SolverFactory<NQueens> solverFactory = SolverFactory.createFromXmlResource(
               "org/optaplanner/examples/nqueens/solver/nqueensSolverConfig.xml");
       Solver<NQueens> solver = solverFactory.buildSolver();

In a typical project (following the Maven directory structure), that solverConfig XML file would be located at $PROJECT_DIR/src/main/resources/org/optaplanner/examples/nqueens/solver/nqueensSolverConfig.xml. Alternatively, a SolverFactory can be created from a File, an InputStream or a Reader with methods such as SolverFactory.createFromXmlFile(). However, for portability reasons, a classpath resource is recommended.

       SolverFactory<NQueens> solverFactory = SolverFactory.createFromXmlResource(
               ".../nqueensSolverConfig.xml", getClass().getClassLoader());

       KieServices kieServices = KieServices.Factory.get();
       KieContainer kieContainer = kieServices.newKieContainer(
               kieServices.newReleaseId("org.nqueens", "nqueens", "1.0.0"));
       SolverFactory<NQueens> solverFactory = SolverFactory.createFromKieContainerXmlResource(
               kieContainer, ".../nqueensSolverConfig.xml");

Both a Solver and a SolverFactory have a generic type called Solution_, which is the class representing a planning problem and solution.

A solver configuration XML file looks like this:

<?xml version="1.0" encoding="UTF-8"?>
<solver>
  <!-- Define the model -->
  <solutionClass>org.optaplanner.examples.nqueens.domain.NQueens</solutionClass>
  <entityClass>org.optaplanner.examples.nqueens.domain.Queen</entityClass>

  <!-- Define the score function -->
  <scoreDirectorFactory>
    <scoreDefinitionType>SIMPLE</scoreDefinitionType>
    <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
  </scoreDirectorFactory>

  <!-- Configure the optimization algorithms (optional) -->
  <termination>
    ...
  </termination>
  <constructionHeuristic>
    ...
  </constructionHeuristic>
  <localSearch>
    ...
  </localSearch>
</solver>

Notice the three parts in it:

These various parts of a configuration are explained further in this manual.

Planner makes it relatively easy to switch optimization algorithm(s) just by changing the configuration. There is even a Benchmarker which allows you to play out different configurations against each other and report the most appropriate configuration for your use case.

A solver configuration can also be configured with the SolverConfig API. This is especially useful to change some values dynamically at runtime. For example, to change the running time based on user input, before building the Solver:

        SolverFactory<NQueens> solverFactory = SolverFactory.createFromXmlResource(
                "org/optaplanner/examples/nqueens/solver/nqueensSolverConfig.xml");

        TerminationConfig terminationConfig = new TerminationConfig();
        terminationConfig.setMinutesSpentLimit(userInput);
        solverFactory.getSolverConfig().setTerminationConfig(terminationConfig);

        Solver<NQueens> solver = solverFactory.buildSolver();

Every element in the solver configuration XML is available as a *Config class or a property on a *Config class in the package namespace org.optaplanner.core.config. These *Config classes are the Java representation of the XML format. They build the runtime components (of the package namespace org.optaplanner.core.impl) and assemble them into an efficient Solver.

    private SolverFactory<NQueens> base;

    public void init() {
        base = SolverFactory.createFromXmlResource(
                "org/optaplanner/examples/nqueens/solver/nqueensSolverConfig.xml");
        base.getSolverConfig().setTerminationConfig(new TerminationConfig());
    }

    // Called concurrently from different threads
    public void userRequest(..., long userInput)
        SolverFactory<NQueens> solverFactory = base.cloneSolverFactory();
        solverFactory.getSolverConfig().getTerminationConfig().setMinutesSpentLimit(userInput);
        Solver<NQueens> solver = solverFactory.buildSolver();
        ...
    }

To configure your solver, you can use the Solver Editor in Business Central. To learn about Business Central, see chapter 1.4. Business Central from Red Hat JBoss BPM Suite User Guide.

Click New Item → Solver configuration to create the Solver Editor in your Business Central. Note that you can also use other assets, for example DRL rules, or guided decision tables.

Figure 4.1. Solver Configuration Editor

The solver editor creates a basic solver configuration. You can run it, together with DRL rules, planner entities, and planner solution, in the Realtime Decision Server or in plain Java code after the KJAR is deployed.

Once you define your solver in the editor, you can click Source and view it in the XML format:

<solver xStreamId="1">
  <scanAnnotatedClasses xStreamId="2"/>
  <scoreDirectorFactory xStreamId="3">
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
  </scoreDirectorFactory>
  <termination xStreamId="4">
    <secondsSpentLimit>0</secondsSpentLimit>
    <minutesSpentLimit>0</minutesSpentLimit>
    <hoursSpentLimit>5</hoursSpentLimit>
    <daysSpentLimit>0</daysSpentLimit>
  </termination>
</solver>

Use the Validate button to validate the solver configuration. This will actually build a Solver, so most issues in your project will present themselves then, without the need to deploy and run it.

By default, the solver configuration will automatically scan for all planning entities and a planning solution classes. If none are found (or too many), validation will fail.

Data Object Tab

To model planning entities and planning solutions used in Business Resource Planner, use data objects. To learn more about data objects, see chapter 4.14. Data models from Red Hat JBoss BPM Suite User Guide. To designate a data object as a planner entity or solution, see the following steps:

Figure 4.2. Data Object Tab

Look at a dataset of your planning problem. You will recognize domain classes in there, each of which can be categorized as one of the following:

Ask yourself: What class changes during planning? Which class has variables that I want the Solver to change for me? That class is a planning entity. Most use cases have only one planning entity class. Most use cases also have only one planning variable per planning entity class.

A good model can greatly improve the success of your planning implementation. Follow these guidelines to design a good model:

For inspiration, take a look at typical design patterns or how the examples modeled their domain:

In Planner, all problems facts and planning entities are plain old JavaBeans (POJOs). Load them from a database, an XML file, a data repository, a REST service, a noSQL cloud, …​ (see integration): it doesn’t matter.

A problem fact is any JavaBean (POJO) with getters that does not change during planning. Implementing the interface Serializable is recommended (but not required). For example in n queens, the columns and rows are problem facts:

public class Column implements Serializable {

    private int index;

    // ... getters
}

public class Row implements Serializable {

    private int index;

    // ... getters
}

A problem fact can reference other problem facts of course:

public class Course implements Serializable {

    private String code;

    private Teacher teacher; // Other problem fact
    private int lectureSize;
    private int minWorkingDaySize;

    private List<Curriculum> curriculumList; // Other problem facts
    private int studentSize;

    // ... getters
}

A problem fact class does not require any Planner specific code. For example, you can reuse your domain classes, which might have JPA annotations.

A Solver implementation will solve your planning problem.

public interface Solver<S extends Solution> {

    S solve(S planningProblem);

    ...
}

A Solver can only solve one planning problem instance at a time. A Solver should only be accessed from a single thread, except for the methods that are specifically javadocced as being thread-safe. It is built with a SolverFactory, there is no need to implement it yourself.

Solving a problem is quite easy once you have:

Just provide the planning problem as argument to the solve() method and it will return the best solution found:

    NQueens bestSolution = solver.solve(planningProblem);

For example in n queens, the solve() method will return an NQueens instance with every Queen assigned to a Row.

Figure 4.4. Best Solution for the 4 Queens Puzzle in 8ms (Also an Optimal Solution)

The solve(Solution) method can take a long time (depending on the problem size and the solver configuration). The Solver intelligently wades through the search space of possible solutions and remembers the best solution it encounters during solving. Depending on a number factors (including problem size, how much time the Solver has, the solver configuration, …​), that best solution might or might not be an optimal solution.

The environment mode allows you to detect common bugs in your implementation. It does not affect the logging level.

You can set the environment mode in the solver configuration XML file:

<solver>
  <environmentMode>FAST_ASSERT</environmentMode>
  ...
</solver>

A solver has a single Random instance. Some solver configurations use the Random instance a lot more than others. For example Simulated Annealing depends highly on random numbers, while Tabu Search only depends on it to deal with score ties. The environment mode influences the seed of that Random instance.

These are the environment modes:

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

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

INFO  Solving started: time spent (3), best score (uninitialized/0), random (JDK with seed 0).
DEBUG     CH step (0), time spent (5), score (0), selected move count (1), picked move (Queen-2 {null -> Row-0}).
DEBUG     CH step (1), time spent (7), score (0), selected move count (3), picked move (Queen-1 {null -> Row-2}).
DEBUG     CH step (2), time spent (10), score (0), selected move count (4), picked move (Queen-3 {null -> Row-3}).
DEBUG     CH step (3), time spent (12), score (-1), selected move count (4), picked move (Queen-0 {null -> Row-1}).
INFO  Construction Heuristic phase (0) ended: step total (4), time spent (12), best score (-1).
DEBUG     LS step (0), time spent (19), score (-1),     best score (-1), accepted/selected move count (12/12), picked move (Queen-1 {Row-2 -> Row-3}).
DEBUG     LS step (1), time spent (24), score (0), new best score (0), accepted/selected move count (9/12), picked move (Queen-3 {Row-3 -> Row-2}).
INFO  Local Search phase (1) ended: step total (2), time spent (24), best score (0).
INFO  Solving ended: time spent (24), best score (0), average calculate count per second (1625).

All time spent values are in milliseconds.

Everything is logged to SLF4J, which is a simple logging facade which delegates every log message to Logback, Apache Commons Logging, Log4j or java.util.logging. Add a dependency to the logging adaptor for your logging framework of choice.

If you are not using any logging framework yet, use Logback by adding this Maven dependency (there is no need to add an extra bridge dependency):

    <dependency>
      <groupId>ch.qos.logback</groupId>
      <artifactId>logback-classic</artifactId>
      <version>1.x</version>
    </dependency>

Configure the logging level on the org.optaplanner package in your logback.xml file:

<configuration>

  <logger name="org.optaplanner" level="debug"/>

  ...

<configuration>

If instead, you are still using Log4J 1.x (and you do not want to switch to its faster successor, Logback), add the bridge dependency:

    <dependency>
      <groupId>org.slf4j</groupId>
      <artifactId>slf4j-log4j12</artifactId>
      <version>1.x</version>
    </dependency>

And configure the logging level on the package org.optaplanner in your log4j.xml file:

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

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

  ...

</log4j:configuration>

        MDC.put("tenant.name", tenantName);
        Solution bestSolution = solver.solve(planningProblem);
        MDC.remove("tenant.name");

  <appender name="fileAppender" class="ch.qos.logback.classic.sift.SiftingAppender">
    <discriminator>
      <key>tenant.name</key>
      <defaultValue>unknown</defaultValue>
    </discriminator>
    <sift>
      <appender name="fileAppender.${tenant.name}" class="...FileAppender">
        <file>local/log/optaplanner-${tenant.name}.log</file>
        ...
      </appender>
    </sift>
  </appender>

Many heuristics and metaheuristics depend on a pseudorandom number generator for move selection, to resolve score ties, probability based move acceptance, …​ During solving, the same Random instance is reused to improve reproducibility, performance and uniform distribution of random values.

To change the random seed of that Random instance, specify a randomSeed:

<solver>
  <randomSeed>0</randomSeed>
  ...
</solver>

To change the pseudorandom number generator implementation, specify a randomType:

<solver>
  <randomType>MERSENNE_TWISTER</randomType>
  ...
</solver>

The following types are supported:

For most use cases, the randomType has no significant impact on the average quality of the best solution on multiple datasets. If you want to confirm this on your use case, use the benchmarker.

Every initialized Solution has a score. The score is an objective way to compare two solutions. The solution with the higher score is better. The Solver aims to find the Solution with the highest Score of all possible solutions. The best solution is the Solution with the highest Score that Solver has encountered during solving, which might be the optimal solution.

Planner cannot automatically know which Solution is best for your business, so you need to tell it how to calculate the score of a given Solution according to your business needs. If you forget or are unable to implement an important business constraint, the solution is probably useless:

Defining constraints in Planner is very flexible through the following score techniques:

All score techniques are based on constraints. A constraint can be a simple pattern (such as Maximize the apple harvest in the solution) or a more complex pattern. A positive constraint is a constraint you want to maximize. A negative constraint is a constraint you want to minimize.

The image above illustrates that the optimal solution always has the highest score, regardless if the constraints are positive or negative.

Most planning problems have only negative constraints and therefore have a negative score. In that case, the score is the sum of the weight of the negative constraints being broken, with a perfect score of 0. This explains why the score of a solution of four queens is the negative of the number of queen pairs which can attack each other.

Negative and positive constraints can be combined, even in the same score level.

When a constraint activates (because the negative constraint is broken or the positive constraint is fulfilled) on a certain planning entity set, it is called a constraint match.

Not all score constraints are equally important. If breaking one constraint is equally bad as breaking another constraint x times, then those two constraints have a different weight (but they are in the same score level). For example in vehicle routing, you can make one “unhappy driver” constraint match count as much as two “fuel tank usage” constraint matches:

Score weighting is often used in use cases where you can put a price tag on everything. In that case, the positive constraints maximize revenue and the negative constraints minimize expenses, so together they maximize profit. Alternatively, score weighting is also often used to create social fairness. For example, a nurse, who requests a free day, pays a higher weight on New Years eve than on a normal day.

Putting a good weight on a constraint can be a difficult analytical decision, because it is about making choices and tradeoffs with other constraints. However, a non-accurate weight is less damaging than mediocre algorithms:

The weight of a constraint match can be dynamically based on the planning entities involved. For example in cloud balance, the weight of the soft constraint match for an active Computer is the cost of that Computer (which differs per computer).

Sometimes a score constraint outranks another score constraint, no matter how many times the other is broken. In that case, those score constraints are in different levels. For example, a nurse cannot do 2 shifts at the same time (due to the constraints of physical reality), this outranks all nurse happiness constraints.

Most use cases have only two score levels, hard and soft. Two scores are compared lexicographically. The first score level gets compared first. If those differ, the others score levels are ignored. For example, a score that breaks 0 hard constraints and 1 000 000 soft constraints is better than a score that breaks 1 hard constraint and 0 soft constraints.

If there are two (or more) score levels, for example a hard and soft level, then a score is feasible if no hard constraints are broken.

For each constraint, you need to pick a score level, a score weight and a score signum. For example: -1soft which has score level of soft, a weight of 1 and a negative signum. Do not use a big constraint weight when your business actually wants different score levels. That hack, known as score folding, is broken:

Three or more score levels are supported. For example: a company might decide that profit outranks employee satisfaction (or vice versa), while both are outranked by the constraints of physical reality.

Far less common is the use case of pareto optimization, which is also known under the more confusing term multi-objective optimization. In pareto scoring, score constraints are in the same score level, yet they are not weighted against each other. When two scores are compared, each of the score constraints are compared individually and the score with the most dominating score constraints wins. Pareto scoring can even be combined with score levels and score constraint weighting.

Consider this example with positive constraints, where we want to get the most apples and oranges. Since it is impossible to compare apples and oranges, we can not weight them against each other. Yet, despite that we can not compare them, we can state that two apples are better then one apple. Similarly, we can state that two apples and one orange are better than just one orange. So despite our inability to compare some Scores conclusively (at which point we declare them equal), we can find a set of optimal scores. Those are called pareto optimal.

Scores are considered equal far more often. It is left up to a human to choose the better out of a set of best solutions (with equal scores) found by Planner. In the example above, the user must choose between solution A (three apples and one orange) and solution B (one apple and six oranges). It is guaranteed that Planner has not found another solution which has more apples or more oranges or even a better combination of both (such as two apples and three oranges).

To implement pareto scoring in Planner, implement a custom ScoreDefinition and Score (and replace the BestSolutionRecaller). Future versions will provide out-of-the-box support.

All the score techniques mentioned above, can be combined seamlessly:

A score is represented by the Score interface, which naturally extends Comparable:

public interface Score<...> extends Comparable<...> {
    ...
}

The Score implementation to use depends on your use case. Your score might not efficiently fit in a single long value. Planner has several built-in Score implementations, but you can implement a custom Score too. Most use cases tend to use the built-in HardSoftScore.

The Score implementation (for example HardSoftScore) must be the same throughout a Solver runtime. The Score implementation is configured in the solver configuration as a ScoreDefinition:

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    ...
  </scoreDirectorFactory>

Avoid the use of float and double for score calculation. Use BigDecimal instead.

Floating point numbers (float and double) cannot represent a decimal number correctly. For example: a double cannot hold the value 0.05 correctly. Instead, it holds the nearest representable value. Arithmetic (including addition and subtraction) with floating point numbers, especially for planning problems, leads to incorrect decisions:

Additionally, floating point number addition is not associative:

System.out.println( ((0.01 + 0.02) + 0.03) == (0.01 + (0.02 + 0.03)) ); // returns false

This leads to score corruption.

Decimal numbers (BigDecimal) have none of these problems.

A SimpleScore has a single int value, for example -123. It has a single score level.

  <scoreDirectorFactory>
    <scoreDefinitionType>SIMPLE</scoreDefinitionType>
    ...
  </scoreDirectorFactory>

Variants of this scoreDefinitionType:

A HardSoftScore has a hard int value and a soft int value, for example -123hard/-456soft. It has 2 score levels (hard and soft).

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    ...
  </scoreDirectorFactory>

Variants of this scoreDefinitionType:

A HardMediumSoftScore which has a hard int value, a medium int value and a soft int value, for example -123hard/-456medium/-789soft. It has 3 score levels (hard, medium and soft).

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_MEDIUM_SOFT</scoreDefinitionType>
    ...
  </scoreDirectorFactory>

Variants of this scoreDefinitionType:

A BendableScore has a configurable number of score levels. It has an array of hard int values and an array of soft int value, for example with 2 hard levels and 3 soft levels, the score can be -123/-456/-789/-012/-345.

  <scoreDirectorFactory>
    <scoreDefinitionType>BENDABLE</scoreDefinitionType>
    <bendableHardLevelsSize>2</bendableHardLevelsSize>
    <bendableSoftLevelsSize>3</bendableSoftLevelsSize>
    ...
  </scoreDirectorFactory>

The number of hard and soft score levels needs to be set at configuration time. It is not flexible to change during solving.

Variants of this scoreDefinitionType:

The ScoreDefinition interface defines the score representation.

To implement a custom Score, you will also need to implement a custom ScoreDefinition. Extend AbstractScoreDefinition (preferably by copy pasting HardSoftScoreDefinition) and start from there.

Then hook your custom ScoreDefinition in your SolverConfig.xml :

  <scoreDirectorFactory>
    <scoreDefinitionClass>...MyScoreDefinition</scoreDefinitionClass>
    ...
  </scoreDirectorFactory>

To have it integrate seamlessly with JPA/Hibernate, XStream, …​ you might need to write some glue code.

There are several ways to calculate the Score of a Solution:

Every score calculation type can use any Score definition. For example, easy Java score calculation can output a HardSoftScore.

All score calculation types are Object Oriented and can reuse existing Java code.

An easy way to implement your score calculation in Java.

Just implement one method of the interface EasyScoreCalculator:

public interface EasyScoreCalculator<Sol extends Solution> {

    Score calculateScore(Sol solution);

}

For example in n queens:

public class NQueensEasyScoreCalculator implements EasyScoreCalculator<NQueens> {

    public SimpleScore calculateScore(NQueens nQueens) {
        int n = nQueens.getN();
        List<Queen> queenList = nQueens.getQueenList();

        int score = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                Queen leftQueen = queenList.get(i);
                Queen rightQueen = queenList.get(j);
                if (leftQueen.getRow() != null && rightQueen.getRow() != null) {
                    if (leftQueen.getRowIndex() == rightQueen.getRowIndex()) {
                        score--;
                    }
                    if (leftQueen.getAscendingDiagonalIndex() == rightQueen.getAscendingDiagonalIndex()) {
                        score--;
                    }
                    if (leftQueen.getDescendingDiagonalIndex() == rightQueen.getDescendingDiagonalIndex()) {
                        score--;
                    }
                }
            }
        }
        return SimpleScore.valueOf(score);
    }

}

Configure it in your solver configuration:

  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <easyScoreCalculatorClass>org.optaplanner.examples.nqueens.solver.score.NQueensEasyScoreCalculator</easyScoreCalculatorClass>
  </scoreDirectorFactory>

Alternatively, build an EasyScoreCalculator instance at runtime and set it with the programmatic API:

    solverFactory.getSolverConfig().getScoreDirectorFactoryConfig.setEasyScoreCalculator(easyScoreCalculator);

A way to implement your score calculation incrementally in Java.

Implement all the methods of the interface IncrementalScoreCalculator and extend the class AbstractIncrementalScoreCalculator:

public interface IncrementalScoreCalculator<Sol extends Solution> {

    void resetWorkingSolution(Sol workingSolution);

    void beforeEntityAdded(Object entity);

    void afterEntityAdded(Object entity);

    void beforeVariableChanged(Object entity, String variableName);

    void afterVariableChanged(Object entity, String variableName);

    void beforeEntityRemoved(Object entity);

    void afterEntityRemoved(Object entity);

    Score calculateScore();

}

For example in n queens:

public class NQueensAdvancedIncrementalScoreCalculator extends AbstractIncrementalScoreCalculator<NQueens> {

    private Map<Integer, List<Queen>> rowIndexMap;
    private Map<Integer, List<Queen>> ascendingDiagonalIndexMap;
    private Map<Integer, List<Queen>> descendingDiagonalIndexMap;

    private int score;

    public void resetWorkingSolution(NQueens nQueens) {
        int n = nQueens.getN();
        rowIndexMap = new HashMap<Integer, List<Queen>>(n);
        ascendingDiagonalIndexMap = new HashMap<Integer, List<Queen>>(n * 2);
        descendingDiagonalIndexMap = new HashMap<Integer, List<Queen>>(n * 2);
        for (int i = 0; i < n; i++) {
            rowIndexMap.put(i, new ArrayList<Queen>(n));
            ascendingDiagonalIndexMap.put(i, new ArrayList<Queen>(n));
            descendingDiagonalIndexMap.put(i, new ArrayList<Queen>(n));
            if (i != 0) {
                ascendingDiagonalIndexMap.put(n - 1 + i, new ArrayList<Queen>(n));
                descendingDiagonalIndexMap.put((-i), new ArrayList<Queen>(n));
            }
        }
        score = 0;
        for (Queen queen : nQueens.getQueenList()) {
            insert(queen);
        }
    }

    public void beforeEntityAdded(Object entity) {
        // Do nothing
    }

    public void afterEntityAdded(Object entity) {
        insert((Queen) entity);
    }

    public void beforeVariableChanged(Object entity, String variableName) {
        retract((Queen) entity);
    }

    public void afterVariableChanged(Object entity, String variableName) {
        insert((Queen) entity);
    }

    public void beforeEntityRemoved(Object entity) {
        retract((Queen) entity);
    }

    public void afterEntityRemoved(Object entity) {
        // Do nothing
    }

    private void insert(Queen queen) {
        Row row = queen.getRow();
        if (row != null) {
            int rowIndex = queen.getRowIndex();
            List<Queen> rowIndexList = rowIndexMap.get(rowIndex);
            score -= rowIndexList.size();
            rowIndexList.add(queen);
            List<Queen> ascendingDiagonalIndexList = ascendingDiagonalIndexMap.get(queen.getAscendingDiagonalIndex());
            score -= ascendingDiagonalIndexList.size();
            ascendingDiagonalIndexList.add(queen);
            List<Queen> descendingDiagonalIndexList = descendingDiagonalIndexMap.get(queen.getDescendingDiagonalIndex());
            score -= descendingDiagonalIndexList.size();
            descendingDiagonalIndexList.add(queen);
        }
    }

    private void retract(Queen queen) {
        Row row = queen.getRow();
        if (row != null) {
            List<Queen> rowIndexList = rowIndexMap.get(queen.getRowIndex());
            rowIndexList.remove(queen);
            score += rowIndexList.size();
            List<Queen> ascendingDiagonalIndexList = ascendingDiagonalIndexMap.get(queen.getAscendingDiagonalIndex());
            ascendingDiagonalIndexList.remove(queen);
            score += ascendingDiagonalIndexList.size();
            List<Queen> descendingDiagonalIndexList = descendingDiagonalIndexMap.get(queen.getDescendingDiagonalIndex());
            descendingDiagonalIndexList.remove(queen);
            score += descendingDiagonalIndexList.size();
        }
    }

    public SimpleScore calculateScore() {
        return SimpleScore.valueOf(score);
    }

}

Configure it in your solver configuration:

  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <incrementalScoreCalculatorClass>org.optaplanner.examples.nqueens.solver.score.NQueensAdvancedIncrementalScoreCalculator</incrementalScoreCalculatorClass>
  </scoreDirectorFactory>

Optionally, to explain a score with ScoreDirector.getConstraintMatchTotals() or to get better output when the IncrementalScoreCalculator is corrupted in FAST_ASSERT or FULL_ASSERT environmentMode, implement also the ConstraintMatchAwareIncrementalScoreCalculator interface:

public interface ConstraintMatchAwareIncrementalScoreCalculator<Sol extends Solution> {

    void resetWorkingSolution(Sol workingSolution, boolean constraintMatchEnabled);

    Collection<ConstraintMatchTotal> getConstraintMatchTotals();

}

The InitializingScoreTrend specifies how the Score will change as more and more variables are initialized (while the already initialized variables do not change). Some optimization algorithms (such Construction Heuristics and Exhaustive Search) run faster if they have such information.

For the Score (or each score level separately), specify a trend:

Most use cases only have negative constraints. Many of those have an InitializingScoreTrend that only goes down:

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    <scoreDrl>.../cloudBalancingScoreRules.drl</scoreDrl>
    <initializingScoreTrend>ONLY_DOWN</initializingScoreTrend>
  </scoreDirectorFactory>

Alternatively, you can also specify the trend for each score level separately:

  <scoreDirectorFactory>
    <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
    <scoreDrl>.../cloudBalancingScoreRules.drl</scoreDrl>
    <initializingScoreTrend>ONLY_DOWN/ONLY_DOWN</initializingScoreTrend>
  </scoreDirectorFactory>

Put the environmentMode in FULL_ASSERT (or FAST_ASSERT) to detect corruption in the incremental score calculation. For more information, see the section about environmentMode. However, that will not verify that your score calculator implements your score constraints as your business actually desires.

A piece of incremental score calculator code can be difficult to write and to review. Assert its correctness by using a different implementation (for example an EasyScoreCalculator) to do the assertions triggered by the environmentMode. Just configure the different implementation as an assertionScoreDirectorFactory:

  <environmentMode>FAST_ASSERT</environmentMode>
  ...
  <scoreDirectorFactory>
    <scoreDefinitionType>...</scoreDefinitionType>
    <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
    <assertionScoreDirectorFactory>
      <easyScoreCalculatorClass>org.optaplanner.examples.nqueens.solver.score.NQueensEasyScoreCalculator</easyScoreCalculatorClass>
    </assertionScoreDirectorFactory>
  </scoreDirectorFactory>

This way, the scoreDrl will be validated by the EasyScoreCalculator.

The Solver will normally spend most of its execution time running the score calculation (which is called in its deepest loops). Faster score calculation will return the same solution in less time with the same algorithm, which normally means a better solution in equal time.

After solving a problem, the Solver will log the average calculation count per second. This is a good measurement of Score calculation performance, despite that it is affected by non score calculation execution time. It depends on the problem scale of the problem dataset. Normally, even for high scale problems, it is higher than 1000, except when you are using EasyScoreCalculator.

When a Solution changes, incremental score calculation (AKA delta based score calculation), will calculate the delta with the previous state to find the new Score, instead of recalculating the entire score on every solution evaluation.

For example, if a single queen A moves from row 1 to 2, it will not bother to check if queen B and C can attack each other, since neither of them changed.

Figure 5.1. Incremental Score Calculation for the 4 Queens Puzzle

This is a huge performance and scalability gain. Drools score calculation gives you this huge scalability gain without forcing you to write a complicated incremental score calculation algorithm. Just let the Drools rule engine do the hard work.

Notice that the speedup is relative to the size of your planning problem (your n), making incremental score calculation far more scalable.

Do not call remote services in your score calculation (except if you are bridging EasyScoreCalculator to a legacy system). The network latency will kill your score calculation performance. Cache the results of those remote services if possible.

If some parts of a constraint can be calculated once, when the Solver starts, and never change during solving, then turn them into cached problem facts.

If you know a certain constraint can never be broken (or it is always broken), you need not write a score constraint for it. For example in n queens, the score calculation does not check if multiple queens occupy the same column, because a Queen's column never changes and every Solution starts with each Queen on a different column.

Instead of implementing a hard constraint, it can sometimes be built in. For example, If Lecture A should never be assigned to Room X, but it uses ValueRangeProvider on Solution, so the Solver will often try to assign it to Room X too (only to find out that it breaks a hard constraint). Use a ValueRangeProvider on the planning entity or filtered selection to define that Course A should only be assigned a Room different than X.

This can give a good performance gain in some use cases, not just because the score calculation is faster, but mainly because most optimization algorithms will spend less time evaluating unfeasible solutions. However, usually this is not a good idea because there is a real risk of trading short term benefits for long term harm:

Make sure that none of your score constraints cause a score trap. A trapped score constraint uses the same weight for different constraint matches, when it could just as easily use a different weight. It effectively lumps its constraint matches together, which creates a flatlined score function for that constraint. This can cause a solution state in which several moves need to be done to resolve or lower the weight of that single constraint. Some examples of score traps:

For example, consider this score trap. If the blue item moves from an overloaded computer to an empty computer, the hard score should improve. The trapped score implementation fails to do that:

The Solver should eventually get out of this trap, but it will take a lot of effort (especially if there are even more processes on the overloaded computer). Before they do that, they might actually start moving more processes into that overloaded computer, as there is no penalty for doing so.

There are several ways to deal with a score trap:

Not all score constraints have the same performance cost. Sometimes one score constraint can kill the score calculation performance outright. Use the Benchmarker to do a one minute run and check what happens to the average calculation count per second if you comment out all but one of the score constraints.

Some use cases have a business requirement to provide a fair schedule (usually as a soft score constraint), for example:

Implementing such a constraint can seem difficult (especially because there are different ways to formalize fairness), but usually the squared workload implementation behaves most desirable. For each employee/asset, count the workload w and subtract w2 from the score.

As shown above, the squared workload implementation guarantees that if you select two employees from a given solution and make their distribution between those two employees fairer, then the resulting new solution will have a better overall score. Don not just use the difference from the average workload, as that can lead to unfairness, as demonstrated below.

When the workload is perfectly balanced, the user often likes to see a 0 score, instead of the distracting -34soft in the image above (for the last solution which is almost perfectly balanced). To nullify this, either add the average multiplied by the number of entities to the score or instead show the variance or standard deviation in the UI.

Terminates when an amount of time has been used.

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

Multiple time types can be used together, for example to configure 150 minutes, either configure it directly:

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

Or use a combination that sums up to 150 minutes:

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

Terminates when the best score hasn’t improved in an amount of time.

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

This termination should not be applied to Construction Heuristics, because they only update the best solution at the end. Therefore it might be better to configure it on a specific Phase (such as <localSearch>), instead of on the Solver itself.

Terminates when a certain score has been reached. Use this Termination if you know the perfect score, for example for 4 queens (which uses a SimpleScore):

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

For a planning problem with a HardSoftScore, it could look like this:

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

For a planning problem with a BendableScore with 3 hard levels and 1 soft level, it could look like this:

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

To terminate once a feasible solution has been reached, this Termination isn’t practical because it requires a bestScoreLimit such as 0hard/-2147483648soft. Instead, use the next termination.

Terminates when a certain score is feasible. Requires that the Score implementation implements FeasibilityScore.

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

This Termination is usually combined with other terminations.

Terminates when a number of steps has been reached. This is useful for hardware performance independent runs.

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

This Termination can only be used for a Phase (such as <localSearch>), not for the Solver itself.

Terminates when the best score hasn’t improved in a number of steps. This is useful for hardware performance independent runs.

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

If the score hasn’t improved recently, it’s probably not going to improve soon anyway and it’s not worth the effort to continue. We have observed that once a new best solution is found (even after a long time of no improvement on the best solution), the next few steps tend to improve the best solution too.

This Termination can only be used for a Phase (such as <localSearch>), not for the Solver itself.

Terminates when a number of score calculations (which is usually the sum of the number of moves and the number of steps) have been reached. This is useful for benchmarking.

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

Switching EnvironmentMode can heavily impact when this termination ends.

Terminations can be combined, for example: terminate after 100 steps or if a score of 0 has been reached:

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

Alternatively you can use AND, for example: terminate after reaching a feasible score of at least -100 and no improvements in 5 steps:

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

This example ensures it doesn’t just terminate after finding a feasible solution, but also completes any obvious improvements on that solution before terminating.

Sometimes you’ll want to terminate a Solver early from another thread, for example because a user action or a server restart. This cannot be configured by a Termination as it’s impossible to predict when and if it will occur. Therefore the Solver interface has these 2 thread-safe methods:

public interface Solver<S extends Solution> {

    // ...

    boolean terminateEarly();
    boolean isTerminateEarly();

}

If you call the terminateEarly() method from another thread, the Solver will terminate at its earliest convenience and the solve(Solution) method will return (in the original Solver thread).

A Move is a change (or set of changes) from a solution A to a solution B. For example, the move below changes queen C from row 0 to row 2:

The new solution is called a neighbor of the original solution, because it can be reached in a single Move. Although a single move can change multiple queens, the neighbors of a solution should always be a very small subset of all possible solutions. For example, on that original solution, these are all possible changeMoves:

If we ignore the 4 changeMoves that have no impact and are therefore not doable, we can see that number of moves is n * (n - 1) = 12. This is far less than the number of possible solutions, which is nn = 256. As the problem scales out, the number of possible moves increases far less than the number of possible solutions.

Yet, in 4 changeMoves or less we can reach any solution. For example we can reach a very different solution in 3 changeMoves:

All optimization algorithms use Moves to transition from one solution to a neighbor solution. Therefore, all the optimization algorithms are confronted with Move selection: the craft of creating and iterating moves efficiently and the art of finding the most promising subset of random moves to evaluate first.

A MoveSelector's main function is to create an Iterator<Move> when needed. An optimization algorithm will iterate through a subset of those moves.

Here’s an example how to configure a changeMoveSelector for the optimization algorithm Local Search:

  <localSearch>
    <changeMoveSelector/>
    ...
  </localSearch>

Out of the box, this works and all properties of the changeMoveSelector are defaulted sensibly (unless that fails fast due to ambiguity). On the other hand, the configuration can be customized significantly for specific use cases. For example: you might want to configure a filter to discard pointless moves.

To create a Move, a MoveSelector needs to select 1 or more planning entities and/or planning values to move. Just like MoveSelectors, EntitySelectors and ValueSelectors need to support a similar feature set (such as scalable just-in-time selection). Therefore, they all implement a common interface Selector and they are configured similarly.

A MoveSelector is often composed of EntitySelectors, ValueSelectors or even other MoveSelectors, which can be configured individually if desired:

    <unionMoveSelector>
      <changeMoveSelector>
        <entitySelector>
          ...
        </entitySelector>
        <valueSelector>
          ...
        </valueSelector>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        ...
      </swapMoveSelector>
    </unionMoveSelector>

Together, this structure forms a Selector tree:

The root of this tree is a MoveSelector which is injected into the optimization algorithm implementation to be (partially) iterated in every step.

For 1 planning variable, the ChangeMove selects 1 planning entity and 1 planning value and assigns the entity’s variable to that value.

Simplest configuration:

    <changeMoveSelector/>

If there are multiple entity classes or multiple planning variables for 1 entity class, a simple configuration will automatically unfold into a union of ChangeMove selectors for every planning variable.

Advanced configuration:

    <changeMoveSelector>
      ... <!-- Normal selector properties -->
      <entitySelector>
        <entityClass>...Lecture</entityClass>
        ...
      </entitySelector>
      <valueSelector>
        <variableName>room</variableName>
        ...
        <nearbySelection>...</nearbySelection>
      </valueSelector>
    </changeMoveSelector>

A ChangeMove is the finest grained move.

The SwapMove selects 2 different planning entities and swaps the planning values of all their planning variables.

Although a SwapMove on a single variable is essentially just 2 ChangeMoves, it’s often the winning step where the first of the 2 ChangeMoves would not be the winning step because it leaves the solution in a state with broken hard constraints. For example: swapping the room of 2 lectures doesn’t bring the solution in a intermediate state where both lectures are in the same room which breaks a hard constraint.

Simplest configuration:

    <swapMoveSelector/>

If there are multiple entity classes, a simple configuration will automatically unfold into a union of SwapMove selectors for every entity class.

Advanced configuration:

    <swapMoveSelector>
      ... <!-- Normal selector properties -->
      <entitySelector>
        <entityClass>...Lecture</entityClass>
        ...
      </entitySelector>
      <secondaryEntitySelector>
        <entityClass>...Lecture</entityClass>
        ...
        <nearbySelection>...</nearbySelection>
      </secondaryEntitySelector>
      <variableNameInclude>room</variableNameInclude>
      <variableNameInclude>...</variableNameInclude>
    </swapMoveSelector>

The secondaryEntitySelector is rarely needed: if it is not specified, entities from the same entitySelector are swapped.

If one or more variableNameInclude properties are specified, not all planning variables will be swapped, but only those specified. For example for course scheduling, specifying only variableNameInclude room will make it only swap room, not period.

A pillar is a set of planning entities which have the same planning value(s) for their planning variable(s). The PillarChangeMove selects 1 entity pillar (or subset of those) and changes the value of 1 variable (which is the same for all entities) to another value.

In the example above, queen A and C have the same value (row 0) and are moved to row 2. Also the yellow and blue process have the same value (computer Y) and are moved to computer X.

Simplest configuration:

    <pillarChangeMoveSelector/>

Advanced configuration:

    <pillarSwapMoveSelector>
      ... <!-- Normal selector properties -->
      <pillarSelector>
        <entitySelector>
          <entityClass>...Lecture</entityClass>
          ...
        </entitySelector>
        <subPillarEnabled>true</subPillarEnabled>
        <minimumSubPillarSize>1</minimumSubPillarSize>
        <maximumSubPillarSize>1000</maximumSubPillarSize>
      </pillarSelector>
      <valueSelector>
        <variableName>room</variableName>
        ...
      </valueSelector>
    </pillarSwapMoveSelector>

A sub pillar is a subset of entities that share the same value(s) for their variable(s). For example if queen A, B, C and D are all located on row 0, they are a pillar and [A, D] is one of the many sub pillars. If subPillarEnabled (defaults to true) is false, no sub pillars are selected. If sub pillars are enabled, the pillar itself is also included and the properties minimumSubPillarSize (defaults to 1) and maximumSubPillarSize (defaults to infinity) limit the size of the selected (sub) pillar.

The other properties are explained in changeMoveSelector.

A pillar is a set of planning entities which have the same planning value(s) for their planning variable(s). The PillarSwapMove selects 2 different entity pillars and swaps the values of all their variables for all their entities.

Simplest configuration:

    <pillarSwapMoveSelector/>

Advanced configuration:

    <pillarSwapMoveSelector>
      ... <!-- Normal selector properties -->
      <pillarSelector>
        <entitySelector>
          <entityClass>...Lecture</entityClass>
          ...
        </entitySelector>
        <subPillarEnabled>true</subPillarEnabled>
        <minimumSubPillarSize>1</minimumSubPillarSize>
        <maximumSubPillarSize>1000</maximumSubPillarSize>
      </pillarSelector>
      <secondaryPillarSelector>
        <entitySelector>
          ...
        </entitySelector>
        ...
      </secondaryPillarSelector>
      <variableNameInclude>room</variableNameInclude>
      <variableNameInclude>...</variableNameInclude>
    </pillarSwapMoveSelector>

The secondaryPillarSelector is rarely needed: if it is not specified, entities from the same pillarSelector are swapped.

The other properties are explained in swapMoveSelector and pillarChangeMoveSelector.

A tailChain is a set of planning entities with a chained planning variable which form a last part of a chain. The tailChainSwapMove selects a tail chain and swaps it with the tail chain of another planning value (in a different or the same anchor chain). If the targeted planning value doesn’t have a tail chain, it swaps with nothing (resulting in a change-like move). If it occurs within the same anchor chain, a partial chain reverse occurs. In academic papers, this is often called a 2-opt move.

Simplest configuration:

    <tailChainSwapMoveSelector/>

Advanced configuration:

    <subChainChangeMoveSelector>
      ... <!-- Normal selector properties -->
      <entitySelector>
        <entityClass>...Customer</entityClass>
        ...
      </entitySelector>
      <valueSelector>
        <variableName>previousStandstill</variableName>
        ...
        <nearbySelection>...</nearbySelection>
      </valueSelector>
    </subChainChangeMoveSelector>

The entitySelector selects the start of the tail chain that is being moved. The valueSelector selects to where that tail chain is moved. If it has a tail chain itself, that is moved to the location of the original tail chain. It uses a valueSelector instead of a secondaryEntitySelector to be able to include all possible 2-opt moves (such as moving to the end of a tail) and to work correctly with nearby selection (because of asymmetric distances and also swapped entity distance gives an incorrect selection probability).

A subChain is a set of planning entities with a chained planning variable which form part of a chain. The subChainChangeMoveSelector selects a subChain and moves it to another place (in a different or the same anchor chain).

Simplest configuration:

    <subChainChangeMoveSelector/>

Advanced configuration:

    <subChainChangeMoveSelector>
      ... <!-- Normal selector properties -->
      <entityClass>...Customer</entityClass>
      <subChainSelector>
        <valueSelector>
          <variableName>previousStandstill</variableName>
          ...
        </valueSelector>
        <minimumSubChainSize>2</minimumSubChainSize>
        <maximumSubChainSize>40</maximumSubChainSize>
      </subChainSelector>
      <valueSelector>
        <variableName>previousStandstill</variableName>
        ...
      </valueSelector>
      <selectReversingMoveToo>true</selectReversingMoveToo>
    </subChainChangeMoveSelector>

The subChainSelector selects a number of entities, no less than minimumSubChainSize (defaults to 1) and no more than maximumSubChainSize (defaults to infinity).

The selectReversingMoveToo property (defaults to true) enables selecting the reverse of every subchain too.

The subChainSwapMoveSelector selects 2 different subChains and moves them to another place in a different or the same anchor chain.

Simplest configuration:

    <subChainSwapMoveSelector/>

Advanced configuration:

    <subChainSwapMoveSelector>
      ... <!-- Normal selector properties -->
      <entityClass>...Customer</entityClass>
      <subChainSelector>
        <valueSelector>
          <variableName>previousStandstill</variableName>
          ...
        </valueSelector>
        <minimumSubChainSize>2</minimumSubChainSize>
        <maximumSubChainSize>40</maximumSubChainSize>
      </subChainSelector>
      <secondarySubChainSelector>
        <valueSelector>
          <variableName>previousStandstill</variableName>
          ...
        </valueSelector>
        <minimumSubChainSize>2</minimumSubChainSize>
        <maximumSubChainSize>40</maximumSubChainSize>
      </secondarySubChainSelector>
      <selectReversingMoveToo>true</selectReversingMoveToo>
    </subChainSwapMoveSelector>

The secondarySubChainSelector is rarely needed: if it is not specified, entities from the same subChainSelector are swapped.

The other properties are explained in subChainChangeMoveSelector.

A unionMoveSelector selects a Move by selecting 1 of its MoveSelector children to supply the next Move.

Simplest configuration:

    <unionMoveSelector>
      <...MoveSelector/>
      <...MoveSelector/>
      <...MoveSelector/>
      ...
    </unionMoveSelector>

Advanced configuration:

    <unionMoveSelector>
      ... <!-- Normal selector properties -->
      <selectorProbabilityWeightFactoryClass>...ProbabilityWeightFactory</selectorProbabilityWeightFactoryClass>
      <changeMoveSelector>
        <fixedProbabilityWeight>...</fixedProbabilityWeight>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        <fixedProbabilityWeight>...</fixedProbabilityWeight>
        ...
      </swapMoveSelector>
      <...MoveSelector>
        <fixedProbabilityWeight>...</fixedProbabilityWeight>
        ...
      </...MoveSelector>
      ...
    </unionMoveSelector>

The selectorProbabilityWeightFactory determines in selectionOrder RANDOM how often a MoveSelector child is selected to supply the next Move. By default, each MoveSelector child has the same chance of being selected.

Change the fixedProbabilityWeight of such a child to select it more often. For example, the unionMoveSelector can return a SwapMove twice as often as a ChangeMove:

    <unionMoveSelector>
      <changeMoveSelector>
        <fixedProbabilityWeight>1.0</fixedProbabilityWeight>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        <fixedProbabilityWeight>2.0</fixedProbabilityWeight>
        ...
      </swapMoveSelector>
    </unionMoveSelector>

The number of possible ChangeMoves is very different from the number of possible SwapMoves and furthermore it’s problem dependent. To give each individual Move the same selection chance (as opposed to each MoveSelector), use the FairSelectorProbabilityWeightFactory:

    <unionMoveSelector>
      <selectorProbabilityWeightFactoryClass>org.optaplanner.core.impl.heuristic.selector.common.decorator.FairSelectorProbabilityWeightFactory</selectorProbabilityWeightFactoryClass>
      <changeMoveSelector/>
      <swapMoveSelector/>
    </unionMoveSelector>

A cartesianProductMoveSelector selects a new CompositeMove. It builds that CompositeMove by selecting 1 Move per MoveSelector child and adding it to the CompositeMove.

Simplest configuration:

    <cartesianProductMoveSelector>
      <...MoveSelector/>
      <...MoveSelector/>
      <...MoveSelector/>
      ...
    </cartesianProductMoveSelector>

Advanced configuration:

    <cartesianProductMoveSelector>
      ... <!-- Normal selector properties -->
      <ignoreEmptyChildIterators>true</ignoreEmptyChildIterators>
      <changeMoveSelector>
        ...
      </changeMoveSelector>
      <swapMoveSelector>
        ...
      </swapMoveSelector>
      <...MoveSelector>
        ...
      </...MoveSelector>
      ...
    </cartesianProductMoveSelector>

The ignoreEmptyChildIterators property (true by default) will ignore every empty childMoveSelector to avoid returning no moves. For example: a Cartesian product of changeMoveSelector A and B, for which B is empty (because all its entities are immovable) returns no move if ignoreEmptyChildIterators is false and the moves of A if ignoreEmptyChildIterators is true.

To enforce that 2 child selectors use the same entity or value efficiently, use mimic selection, not move filtering.

A Selector's cacheType determines when a selection (such as a Move, an entity, a value, …​) is created and how long it lives.

Almost every Selector supports setting a cacheType:

    <changeMoveSelector>
      <cacheType>PHASE</cacheType>
      ...
    </changeMoveSelector>

The following cacheTypes are supported:

A cacheType can be set on composite selectors too:

    <unionMoveSelector>
      <cacheType>PHASE</cacheType>
      <changeMoveSelector/>
      <swapMoveSelector/>
      ...
    </unionMoveSelector>

Nested selectors of a cached selector cannot be configured to be cached themselves, unless it’s a higher cacheType. For example: a STEP cached unionMoveSelector can hold a PHASE cached changeMoveSelector, but not a STEP cached changeMoveSelector.

A Selector's selectionOrder determines the order in which the selections (such as Moves, entities, values, …​) are iterated. An optimization algorithm will usually only iterate through a subset of its MoveSelector's selections, starting from the start, so the selectionOrder is critical to decide which Moves are actually evaluated.

Almost every Selector supports setting a selectionOrder:

    <changeMoveSelector>
      ...
      <selectionOrder>RANDOM</selectionOrder>
      ...
    </changeMoveSelector>

The following selectionOrders are supported:

A selectionOrder can be set on composite selectors too.

There can be certain moves that you don’t want to select, because:

Filtered selection can happen on any Selector in the selector tree, including any MoveSelector, EntitySelector or ValueSelector. It works with any cacheType and selectionOrder.

Filtering uses the interface SelectionFilter:

public interface SelectionFilter<T> {

    boolean accept(ScoreDirector scoreDirector, T selection);

}

Implement the accept method to return false on a discarded selection. Unaccepted moves will not be selected and will therefore never have their doMove method called.

public class DifferentCourseSwapMoveFilter implements SelectionFilter<SwapMove> {

    public boolean accept(ScoreDirector scoreDirector, SwapMove move) {
        Lecture leftLecture = (Lecture) move.getLeftEntity();
        Lecture rightLecture = (Lecture) move.getRightEntity();
        return !leftLecture.getCourse().equals(rightLecture.getCourse());
    }

}

Apply the filter on the lowest level possible. In most cases, you’ll need to know both the entity and the value involved and you’ll have to apply a filterClass on the moveSelector:

    <swapMoveSelector>
      <filterClass>org.optaplanner.examples.curriculumcourse.solver.move.DifferentCourseSwapMoveFilter</filterClass>
    </swapMoveSelector>

But if possible, apply it on a lower level, such as a filterClass on the entitySelector or valueSelector:

    <changeMoveSelector>
      <entitySelector>
        <filterClass>...EntityFilter</filterClass>
      </entitySelector>
    </changeMoveSelector>

You can configure multiple filterClass elements on a single selector.

Sorted selection can happen on any Selector in the selector tree, including any MoveSelector, EntitySelector or ValueSelector. It does not work with cacheType JUST_IN_TIME and it only works with selectionOrder SORTED.

It’s mostly used in construction heuristics.

public class CloudProcessDifficultyComparator implements Comparator<CloudProcess> {

    public int compare(CloudProcess a, CloudProcess b) {
        return new CompareToBuilder()
                .append(a.getRequiredMultiplicand(), b.getRequiredMultiplicand())
                .append(a.getId(), b.getId())
                .toComparison();
    }

}

    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterComparatorClass>...CloudProcessDifficultyComparator</sorterComparatorClass>
      <sorterOrder>DESCENDING</sorterOrder>
    </entitySelector>

public interface SelectionSorterWeightFactory<Sol extends Solution, T> {

    Comparable createSorterWeight(Sol solution, T selection);

}

public class QueenDifficultyWeightFactory implements SelectionSorterWeightFactory<NQueens, Queen> {

    public Comparable createSorterWeight(NQueens nQueens, Queen queen) {
        int distanceFromMiddle = calculateDistanceFromMiddle(nQueens.getN(), queen.getColumnIndex());
        return new QueenDifficultyWeight(queen, distanceFromMiddle);
    }

    // ...

    public static class QueenDifficultyWeight implements Comparable<QueenDifficultyWeight> {

        private final Queen queen;
        private final int distanceFromMiddle;

        public QueenDifficultyWeight(Queen queen, int distanceFromMiddle) {
            this.queen = queen;
            this.distanceFromMiddle = distanceFromMiddle;
        }

        public int compareTo(QueenDifficultyWeight other) {
            return new CompareToBuilder()
                    // The more difficult queens have a lower distance to the middle
                    .append(other.distanceFromMiddle, distanceFromMiddle) // Decreasing
                    // Tie breaker
                    .append(queen.getColumnIndex(), other.queen.getColumnIndex())
                    .toComparison();
        }

    }

}

    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterWeightFactoryClass>...QueenDifficultyWeightFactory</sorterWeightFactoryClass>
      <sorterOrder>DESCENDING</sorterOrder>
    </entitySelector>

public interface SelectionSorter<T> {

    void sort(ScoreDirector scoreDirector, List<T> selectionList);

}

    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>SORTED</selectionOrder>
      <sorterClass>...MyEntitySorter</sorterClass>
    </entitySelector>

Probabilistic selection can happen on any Selector in the selector tree, including any MoveSelector, EntitySelector or ValueSelector. It does not work with cacheType JUST_IN_TIME and it only works with selectionOrder PROBABILISTIC.

Each selection has a probabilityWeight, which determines the chance that selection will be selected:

public interface SelectionProbabilityWeightFactory<T> {

    double createProbabilityWeight(ScoreDirector scoreDirector, T selection);

}

    <entitySelector>
      <cacheType>PHASE</cacheType>
      <selectionOrder>PROBABILISTIC</selectionOrder>
      <probabilityWeightFactoryClass>...MyEntityProbabilityWeightFactoryClass</probabilityWeightFactoryClass>
    </entitySelector>

For example, if there are 3 entities: process A (probabilityWeight 2.0), process B (probabilityWeight 0.5) and process C (probabilityWeight 0.5), then process A will be selected 4 times more often than B and C.

Selecting all possible moves sometimes does not scale well enough, especially for construction heuristics (which don’t support acceptedCountLimit).

To limit the number of selected selections per step, apply a selectedCountLimit on the selector:

    <changeMoveSelector>
      <selectedCountLimit>100</selectedCountLimit>
    </changeMoveSelector>

During mimic selection, 1 normal selector records its selection and 1 or multiple other special selectors replay that selection. The recording selector acts as a normal selector and supports all other configuration properties. A replaying selector mimics the recording selection and support no other configuration properties.

The recording selector needs an ID. A replaying selector must reference a recorder’s ID with a mimicSelectorRef:

      <cartesianProductMoveSelector>
        <changeMoveSelector>
          <entitySelector id="entitySelector"/>
          <valueSelector>
            <variableName>period</variableName>
          </valueSelector>
        </changeMoveSelector>
        <changeMoveSelector>
          <entitySelector mimicSelectorRef="entitySelector"/>
          <valueSelector>
            <variableName>room</variableName>
          </valueSelector>
        </changeMoveSelector>
      </cartesianProductMoveSelector>

Mimic selection is useful to create a composite move from 2 moves that affect the same entity.

In some use cases (such as TSP and VRP, but also in non-chained variable cases), changing entities to nearby values or swapping nearby entities can heavily increase scalability and improve solution quality.

Nearby selection increases the probability of selecting an entity or value which is nearby to the first entity being moved in that move.

The distance between 2 entities or values is domain specific. Therefore, implement the NearbyDistanceMeter interface:

public interface NearbyDistanceMeter<O, D> {

    double getNearbyDistance(O origin, D destination);

}

It returns a double which represents the distance:

public class CustomerNearbyDistanceMeter implements NearbyDistanceMeter<Customer, Standstill> {

    public double getNearbyDistance(Customer origin, Standstill destination) {
        return origin.getDistanceTo(destination);
    }

}

To configure nearby selection, add a nearbySelection element in the entitySelector or valueSelector and use mimic selection to specify which entity should be near by the selection.

    <unionMoveSelector>
      <changeMoveSelector>
        <entitySelector id="entitySelector1"/>
        <valueSelector>
          <nearbySelection>
            <originEntitySelector mimicSelectorRef="entitySelector1"/>
            <nearbyDistanceMeterClass>...CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
            <parabolicDistributionSizeMaximum>40</parabolicDistributionSizeMaximum>
          </nearbySelection>
        </valueSelector>
      </changeMoveSelector>
      <swapMoveSelector>
        <entitySelector id="entitySelector2"/>
        <secondaryEntitySelector>
          <nearbySelection>
            <originEntitySelector mimicSelectorRef="entitySelector2"/>
            <nearbyDistanceMeterClass>...CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
            <parabolicDistributionSizeMaximum>40</parabolicDistributionSizeMaximum>
          </nearbySelection>
        </secondaryEntitySelector>
      </swapMoveSelector>
      <tailChainSwapMoveSelector>
        <entitySelector id="entitySelector3"/>
        <valueSelector>
          <nearbySelection>
            <originEntitySelector mimicSelectorRef="entitySelector3"/>
            <nearbyDistanceMeterClass>...CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
            <parabolicDistributionSizeMaximum>40</parabolicDistributionSizeMaximum>
          </nearbySelection>
        </valueSelector>
      </tailChainSwapMoveSelector>
    </unionMoveSelector>

A distributionSizeMaximum parameter should not be 1 because if the nearest is already the planning value of the current entity, then the only move that is selectable is not doable.

To allow every element to be selected, regardless of the number of entities, only set the distribution type (so without a distributionSizeMaximum parameter):

  <nearbySelection>
    <nearbySelectionDistributionType>PARABOLIC_DISTRIBUTION</nearbySelectionDistributionType>
  </nearbySelection>

The following NearbySelectionDistributionTypes are supported:

As always, use the Benchmarker to tweak values if desired.

To determine which move types might be missing in your implementation, run a Benchmarker for a short amount of time and configure it to write the best solutions to disk. Take a look at such a best solution: it will likely be a local optimum. Try to figure out if there’s a move that could get out of that local optimum faster.

If you find one, implement that coarse-grained move, mix it with the existing moves and benchmark it against the previous configurations to see if you want to keep it.

Instead of reusing the generic Moves (such as ChangeMove) you can also implement your own Moves. Generic and custom MoveSelectors can be combined as desired.

A custom Move can be tailored to work to the advantage of your constraints. For example, in examination scheduling, changing the period of an exam A also changes the period of all the exams that need to coincide with exam A.

A custom Move is also slightly faster than a generic Move. However, it’s far more work to implement and much harder to avoid bugs. After implementing a custom Move, make sure to turn on environmentMode FULL_ASSERT to check for score corruptions.

Your custom moves must implement the Move interface:

public interface Move {

    boolean isMoveDoable(ScoreDirector scoreDirector);

    Move createUndoMove(ScoreDirector scoreDirector);
    void doMove(ScoreDirector scoreDirector);

    Collection<? extends Object> getPlanningEntities();
    Collection<? extends Object> getPlanningValues();

}

Let’s take a look at the Move implementation for 4 queens which moves a queen to a different row:

public class RowChangeMove extends AbstractMove {

    private Queen queen;
    private Row toRow;

    public RowChangeMove(Queen queen, Row toRow) {
        this.queen = queen;
        this.toRow = toRow;
    }

    // ... see below

}

An instance of RowChangeMove moves a queen from its current row to a different row.

Planner calls the doMove(ScoreDirector) method to do a move, which calls doMoveOnGenuineVariables(ScoreDirector). The Move implementation must notify the ScoreDirector of any changes it makes to planning entity’s variables:

    public void doMoveOnGenuineVariables(ScoreDirector scoreDirector) {
        scoreDirector.beforeVariableChanged(queen, "row"); // before changes are made to the queen.row
        queen.setRow(toRow);
        scoreDirector.afterVariableChanged(queen, "row"); // after changes are made to the queen.row
    }

You need to call the scoreDirector.beforeVariableChanged(Object, String) and scoreDirector.afterVariableChanged(Object, String) methods directly before and after modifying the entity.

Planner automatically filters out non doable moves by calling the isMoveDoable(ScoreDirector) method on a move. A non doable move is:

In the n queens example, a move which moves the queen from its current row to the same row isn’t doable:

    public boolean isMoveDoable(ScoreDirector scoreDirector) {
        return !ObjectUtils.equals(queen.getRow(), toRow);
    }

Because we won’t generate a move which can move a queen outside the board limits, we don’t need to check it. A move that is currently not doable could become doable on the working Solution of a later step.

Each move has an undo move: a move (normally of the same type) which does the exact opposite. In the example above the undo move of C0 to C2 would be the move C2 to C0. An undo move is created from a Move, before the Move has been done on the current solution.

    public Move createUndoMove(ScoreDirector scoreDirector) {
        return new RowChangeMove(queen, queen.getRow());
    }

Notice that if C0 would have already been moved to C2, the undo move would create the move C2 to C2, instead of the move C2 to C0.

A solver phase might do and undo the same Move more than once. In fact, many solver phases will iteratively do and undo a number of moves to evaluate them, before selecting one of those and doing that move again (without undoing it this time).

A Move must implement the getPlanningEntities() and getPlanningValues() methods. They are used by entity tabu and value tabu respectively. When they are called, the Move has already been done.

    public List<? extends Object> getPlanningEntities() {
        return Collections.singletonList(queen);
    }

    public Collection<? extends Object> getPlanningValues() {
        return Collections.singletonList(toRow);
    }

If your Move changes multiple planning entities, return all of them in getPlanningEntities() and return all their values (to which they are changing) in getPlanningValues().

    public Collection<? extends Object> getPlanningEntities() {
        return Arrays.asList(leftCloudProcess, rightCloudProcess);
    }

    public Collection<? extends Object> getPlanningValues() {
        return Arrays.asList(leftCloudProcess.getComputer(), rightCloudProcess.getComputer());
    }

A Move must implement the equals() and hashCode() methods. 2 moves which make the same change on a solution, should be equal.

    public boolean equals(Object o) {
        if (this == o) {
            return true;
        } else if (o instanceof RowChangeMove) {
            RowChangeMove other = (RowChangeMove) o;
            return new EqualsBuilder()
                    .append(queen, other.queen)
                    .append(toRow, other.toRow)
                    .isEquals();
        } else {
            return false;
        }
    }

    public int hashCode() {
        return new HashCodeBuilder()
                .append(queen)
                .append(toRow)
                .toHashCode();
    }

Notice that it checks if the other move is an instance of the same move type. This instanceof check is important because a move will be compared to a move with another move type if you’re using more than 1 move type.

Implement the toString() method to keep Planner’s logs readable:

    public String toString() {
        return queen + " {" + queen.getRow() + " -> " + toRow + "}";
    }

Now that we can implement a single custom Move, let’s take a look at generating such custom moves.

The easiest way to generate custom moves is by implementing the interface MoveListFactory:

public interface MoveListFactory<S extends Solution> {

    List<Move> createMoveList(S solution);

}

For example:

public class RowChangeMoveFactory implements MoveListFactory<NQueens> {

    public List<Move> createMoveList(NQueens nQueens) {
        List<Move> moveList = new ArrayList<Move>();
        for (Queen queen : nQueens.getQueenList()) {
            for (Row toRow : nQueens.getRowList()) {
                moveList.add(new RowChangeMove(queen, toRow));
            }
        }
        return moveList;
    }

}

Simple configuration (which can be nested in a unionMoveSelector just like any other MoveSelector):

    <moveListFactory>
      <moveListFactoryClass>org.optaplanner.examples.nqueens.solver.move.factory.RowChangeMoveFactory</moveListFactoryClass>
    </moveListFactory>

Advanced configuration:

    <moveListFactory>
      ... <!-- Normal moveSelector properties -->
      <moveListFactoryClass>org.optaplanner.examples.nqueens.solver.move.factory.RowChangeMoveFactory</moveListFactoryClass>
    </moveListFactory>

Because the MoveListFactory generates all moves at once in a List<Move>, it does not support cacheType JUST_IN_TIME. Therefore, moveListFactory uses cacheType STEP by default and it scales badly in memory footprint.

Use this advanced form to generate custom moves by implementing the MoveIteratorFactory interface:

public interface MoveIteratorFactory {

    long getSize(ScoreDirector scoreDirector);

    Iterator<Move> createOriginalMoveIterator(ScoreDirector scoreDirector);

    Iterator<Move> createRandomMoveIterator(ScoreDirector scoreDirector, Random workingRandom);

}

The getSize() method must give an estimation of the size. It doesn’t need to be correct. The createOriginalMoveIterator method is called if the selectionOrder is ORIGINAL or if it is cached. The createRandomMoveIterator method is called for selectionOrder RANDOM combined with cacheType JUST_IN_TIME.

Simple configuration (which can be nested in a unionMoveSelector just like any other MoveSelector):

    <moveIteratorFactory>
      <moveIteratorFactoryClass>...</moveIteratorFactoryClass>
    </moveIteratorFactory>

Advanced configuration:

    <moveIteratorFactory>
      ... <!-- Normal moveSelector properties -->
      <moveIteratorFactoryClass>...</moveIteratorFactoryClass>
    </moveIteratorFactory>

The Brute Force algorithm creates and evaluates every possible solution.

Notice that it creates a search tree that explodes exponentially as the problem size increases, so it hits a scalability wall.

Simplest configuration of Brute Force:

<solver>
  ...
  <exhaustiveSearch>
    <exhaustiveSearchType>BRUTE_FORCE</exhaustiveSearchType>
  </exhaustiveSearch>
</solver>

Branch And Bound also explores nodes in an exponential search tree, but it investigates more promising nodes first and prunes away worthless nodes.

For each node, Branch And Bound calculates the optimistic bound: the best possible score to which that node can lead to. If the optimistic bound of a node is lower or equal to the global pessimistic bound, then it prunes away that node (including the entire branch of all its subnodes).

For example: at index 14, it sets the global pessimistic bound to -2. Because all solutions reachable from the node visited at index 11 will have a score lower or equal to -2 (the node’s optimistic bound), they can be pruned away.

Notice that Branch And Bound (much like Brute Force) creates a search tree that explodes exponentially as the problem size increases. So it hits the same scalability wall, only a little bit later.

Simplest configuration of Branch And Bound:

<solver>
  ...
  <exhaustiveSearch>
    <exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
  </exhaustiveSearch>
</solver>

Advanced configuration:

  <exhaustiveSearch>
    <exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
    <nodeExplorationType>DEPTH_FIRST</nodeExplorationType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </exhaustiveSearch>

The nodeExplorationType options are:

The entitySorterManner options are:

The valueSorterManner options are:

The First Fit algorithm cycles through all the planning entities (in default order), initializing 1 planning entity at a time. It assigns the planning entity to the best available planning value, taking the already initialized planning entities into account. It terminates when all planning entities have been initialized. It never changes a planning entity after it has been assigned.

Notice that it starts with putting Queen A into row 0 (and never moving it later), which makes it impossible to reach the optimal solution. Suffixing this construction heuristic with metaheuristics can remedy that.

Configure this solver phase:

  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
  </constructionHeuristic>

For advanced configuration, see Allocate Entity From Queue.

Like First Fit, but assigns the more difficult planning entities first, because they are less likely to fit in the leftovers. So it sorts the planning entities on decreasing difficulty.

Requires the model to support planning entity difficulty comparison.

Configure this solver phase:

  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>

For advanced configuration, see Allocate Entity From Queue.

Like First Fit, but uses the weaker planning values first, because the strong planning values are more likely to be able to accommodate later planning entities. So it sorts the planning values on increasing strength.

Requires the model to support planning value strength comparison.

Configure this solver phase:

  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_FIT</constructionHeuristicType>
  </constructionHeuristic>

For advanced configuration, see Allocate Entity From Queue.

Combines First Fit Decreasing and Weakest Fit. So it sorts the planning entities on decreasing difficulty and the planning values on increasing strength.

Requires the model to support planning entity difficulty comparison and planning value strength comparison.

Configure this solver phase:

  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>

For advanced configuration, see Allocate Entity From Queue.

Like First Fit, but uses the strong planning values first, because the strong planning values are more likely to have a lower soft cost to use. So it sorts the planning values on decreasing strength.

Requires the model to support planning value strength comparison.

Configure this solver phase:

  <constructionHeuristic>
    <constructionHeuristicType>STRONGEST_FIT</constructionHeuristicType>
  </constructionHeuristic>

For advanced configuration, see Allocate Entity From Queue.

Combines First Fit Decreasing and Strongest Fit. So it sorts the planning entities on decreasing difficulty and the planning values on decreasing strength.

Requires the model to support planning entity difficulty comparison and planning value strength comparison.

Configure this solver phase:

  <constructionHeuristic>
    <constructionHeuristicType>STRONGEST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>

For advanced configuration, see Allocate Entity From Queue.

Allocate Entity From Queue is a versatile, generic form of First Fit, First Fit Decreasing, Weakest Fit and Weakest Fit Decreasing. It works like this:

Simple configuration:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_ENTITY_FROM_QUEUE</constructionHeuristicType>
  </constructionHeuristic>

Verbose simple configuration:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_ENTITY_FROM_QUEUE</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>

The entitySorterManner options are:

The valueSorterManner options are:

Advanced detailed configuration. For example, a Weakest Fit Decreasing configuration for a single entity class with a single variable:

  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <cacheType>PHASE</cacheType>
        <selectionOrder>SORTED</selectionOrder>
        <sorterManner>DECREASING_DIFFICULTY</sorterManner>
      </entitySelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
        <valueSelector>
          <cacheType>PHASE</cacheType>
          <selectionOrder>SORTED</selectionOrder>
          <sorterManner>INCREASING_STRENGTH</sorterManner>
        </valueSelector>
      </changeMoveSelector>
    </queuedEntityPlacer>
  </constructionHeuristic>

Per step, the QueuedEntityPlacer selects 1 uninitialized entity from the EntitySelector and applies the winning Move (out of all the moves for that entity generated by the MoveSelector). The mimic selection ensures that the winning Move changes (only) the selected entity.

To customize the entity or value sorting, see sorted selection. Other Selector customization (such as filtering and limiting) is supported too.

There are 2 ways to deal with multiple variables, depending on how their ChangeMoves are combined:

For example, presume a course scheduling example with 200 rooms and 40 periods.

This First Fit configuration for a single entity class with 2 variables, using a cartesian product of their ChangeMoves, will select 8000 moves per entity:

  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <cacheType>PHASE</cacheType>
      </entitySelector>
      <cartesianProductMoveSelector>
        <changeMoveSelector>
          <entitySelector mimicSelectorRef="placerEntitySelector"/>
          <valueSelector>
            <variableName>room</variableName>
          </valueSelector>
        </changeMoveSelector>
        <changeMoveSelector>
          <entitySelector mimicSelectorRef="placerEntitySelector"/>
          <valueSelector>
            <variableName>period</variableName>
          </valueSelector>
        </changeMoveSelector>
      </cartesianProductMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>

This First Fit configuration for a single entity class with 2 variables, using sequential ChangeMoves, will select 240 moves per entity:

  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <cacheType>PHASE</cacheType>
      </entitySelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
        <valueSelector>
          <variableName>period</variableName>
        </valueSelector>
      </changeMoveSelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
        <valueSelector>
          <variableName>room</variableName>
        </valueSelector>
      </changeMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>

With 3 or more variables, it’s possible to combine the Cartesian product and sequential techniques:

  <constructionHeuristic>
    <queuedEntityPlacer>
      ...
      <cartesianProductMoveSelector>
        <changeMoveSelector>...</changeMoveSelector>
        <changeMoveSelector>...</changeMoveSelector>
      </cartesianProductMoveSelector>
      <changeMoveSelector>...</changeMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>

The easiest way to deal with multiple entity classes is to run a separate construction heuristic for each entity class:

  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <cacheType>PHASE</cacheType>
        <entityClass>...DogEntity</entityClass>
      </entitySelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
      </changeMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>
  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <cacheType>PHASE</cacheType>
        <entityClass>...CatEntity</entityClass>
      </entitySelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
      </changeMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>

There are several pick early types for Construction Heuristics:

Allocate To Value From Queue works like this:

Simple configuration:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_TO_VALUE_FROM_QUEUE</constructionHeuristicType>
  </constructionHeuristic>

Verbose simple configuration:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_TO_VALUE_FROM_QUEUE</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>

Advanced detailed configuration. For example, a configuration for a single entity class with a single variable:

  <constructionHeuristic>
    <queuedValuePlacer>
      <valueSelector id="placerValueSelector">
        <cacheType>PHASE</cacheType>
        <selectionOrder>SORTED</selectionOrder>
        <sorterManner>INCREASING_STRENGTH</sorterManner>
      </valueSelector>
      <changeMoveSelector>
        <entitySelector>
          <cacheType>PHASE</cacheType>
          <selectionOrder>SORTED</selectionOrder>
          <sorterManner>DECREASING_DIFFICULTY</sorterManner>
        </entitySelector>
        <valueSelector mimicSelectorRef="placerValueSelector"/>
      </changeMoveSelector>
    </queuedValuePlacer>
  </constructionHeuristic>

The Cheapest Insertion algorithm cycles through all the planning values for all the planning entities, initializing 1 planning entity at a time. It assigns a planning entity to the best available planning value (out of all the planning entities and values), taking the already initialized planning entities into account. It terminates when all planning entities have been initialized. It never changes a planning entity after it has been assigned.

Simplest configuration of Cheapest Insertion:

  <constructionHeuristic>
    <constructionHeuristicType>CHEAPEST_INSERTION</constructionHeuristicType>
  </constructionHeuristic>

For advanced configuration, see Allocate from pool.

The Regret Insertion algorithm behaves like the Cheapest Insertion algorithm. It also cycles through all the planning values for all the planning entities, initializing 1 planning entity at a time. But instead of picking the entity-value combination with the best score, it picks the entity which has the largest score loss between its best and second best value assignment. It then assigns that entity to its best value, to avoid regretting not having done that.

This algorithm has not been implemented yet.

Allocate From Pool is a versatile, generic form of Cheapest Insertion and Regret Insertion. It works like this:

Simple configuration:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_FROM_POOL</constructionHeuristicType>
  </constructionHeuristic>

Verbose simple configuration:

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_FROM_POOL</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>

The entitySorterManner and valueSorterManner options are described in Allocate Entity From Queue.

Advanced detailed configuration. For example, a Cheapest Insertion configuration for a single entity class with a single variable:

  <constructionHeuristic>
    <pooledEntityPlacer>
      <changeMoveSelector>
        <entitySelector id="placerEntitySelector">
          <cacheType>PHASE</cacheType>
          <selectionOrder>SORTED</selectionOrder>
          <sorterManner>DECREASING_DIFFICULTY</sorterManner>
        </entitySelector>
        <valueSelector>
          <cacheType>PHASE</cacheType>
          <selectionOrder>SORTED</selectionOrder>
          <sorterManner>INCREASING_STRENGTH</sorterManner>
        </valueSelector>
      </changeMoveSelector>
    </pooledEntityPlacer>
  </constructionHeuristic>

Per step, the PooledEntityPlacer applies the winning Move (out of all the moves for that entity generated by the MoveSelector).

To customize the entity or value sorting, see sorted selection. Other Selector customization (such as filtering and limiting) is supported too.

A step is the winning Move. Local Search tries a number of moves on the current solution and picks the best accepted move as the step:

Figure 10.1. Decide the next step at step 0 (4 queens example)

Because the move B0 to B3 has the highest score (-3), it is picked as the next step. If multiple moves have the same highest score, one is picked randomly, in this case B0 to B3. Note that C0 to C3 (not shown) could also have been picked because it also has the score -3.

The step is applied to the solution. From that new solution, Local Search tries every move again, to decide the next step after that. It continually does this in a loop, and we get something like this:

Figure 10.2. All steps (4 queens example)

Notice that Local Search doesn’t use a search tree, but a search path. The search path is highlighted by the green arrows. At each step it tries all selected moves, but unless it’s the step, it doesn’t investigate that solution further. This is one of the reasons why Local Search is very scalable.

As shown above, Local Search solves the 4 queens problem by starting with the starting solution and make the following steps sequentially:

Turn on debug logging for the category org.optaplanner to show those steps in the log:

INFO  Solving started: time spent (0), best score (-6), random (JDK with seed 0).
DEBUG     LS step (0), time spent (20), score (-3), new best score (-3), accepted/selected move count (12/12), picked move (Queen-1 {Row-0 -> Row-3}).
DEBUG     LS step (1), time spent (31), score (-1), new best score (-1), accepted/selected move count (12/12), picked move (Queen-3 {Row-0 -> Row-2}).
DEBUG     LS step (2), time spent (40), score (0), new best score (0), accepted/selected move count (12/12), picked move (Queen-0 {Row-0 -> Row-1}).
INFO  Local Search phase (0) ended: step total (3), time spent (41), best score (0).
INFO  Solving ended: time spent (41), best score (0), average calculate count per second (1780).

Notice that a log message includes the toString() method of the Move implementation which returns for example Queen-1 {Row-0 -> Row-3}.

A naive Local Search configuration solves the 4 queens problem in 3 steps, by evaluating only 37 possible solutions (3 steps with 12 moves each + 1 starting solution), which is only fraction of all 256 possible solutions. It solves 16 queens in 31 steps, by evaluating only 7441 out of 18446744073709551616 possible solutions. By using a Construction Heuristics phase first, it’s even a lot more efficient.

Local Search decides the next step with the aid of 3 configurable components:

The solver phase configuration looks like this:

  <localSearch>
    <unionMoveSelector>
      ...
    </unionMoveSelector>
    <acceptor>
      ...
    </acceptor>
    <forager>
      ...
    </forager>
  </localSearch>

In the example below, the MoveSelector generated the moves shown with the blue lines, the Acceptor accepted all of them and the Forager picked the move B0 to B3.

Turn on trace logging to show the decision making in the log:

INFO  Solver started: time spent (0), score (-6), new best score (-6), random (JDK with seed 0).
TRACE         Move index (0) not doable, ignoring move (Queen-0 {Row-0 -> Row-0}).
TRACE         Move index (1), score (-4), accepted (true), move (Queen-0 {Row-0 -> Row-1}).
TRACE         Move index (2), score (-4), accepted (true), move (Queen-0 {Row-0 -> Row-2}).
TRACE         Move index (3), score (-4), accepted (true), move (Queen-0 {Row-0 -> Row-3}).
...
TRACE         Move index (6), score (-3), accepted (true), move (Queen-1 {Row-0 -> Row-3}).
...
TRACE         Move index (9), score (-3), accepted (true), move (Queen-2 {Row-0 -> Row-3}).
...
TRACE         Move index (12), score (-4), accepted (true), move (Queen-3 {Row-0 -> Row-3}).
DEBUG     LS step (0), time spent (6), score (-3), new best score (-3), accepted/selected move count (12/12), picked move (Queen-1 {Row-0 -> Row-3}).
...

Because the last solution can degrade (for example in Tabu Search), the Solver remembers the best solution it has encountered through the entire search path. Each time the current solution is better than the last best solution, the current solution is cloned and referenced as the new best solution.

An Acceptor is used (together with a Forager) to activate Tabu Search, Simulated Annealing, Late Acceptance, …​ For each move it checks whether it is accepted or not.

By changing a few lines of configuration, you can easily switch from Tabu Search to Simulated Annealing or Late Acceptance and back.

You can implement your own Acceptor, but the built-in acceptors should suffice for most needs. You can also combine multiple acceptors.

A Forager gathers all accepted moves and picks the move which is the next step. Normally it picks the accepted move with the highest score. If several accepted moves have the highest score, one is picked randomly to break the tie. Breaking ties randomly leads to better results.

DEBUG     LS step (0), time spent (20), score (-3), new best score (-3), ...

Hill Climbing tries all selected moves and then takes the best move, which is the move which leads to the solution with the highest score. That best move is called the step move. From that new solution, it again tries all selected moves and takes the best move and continues like that iteratively. If multiple selected moves tie for the best move, one of them is randomly chosen as the best move.

Notice that once a queen has moved, it can be moved again later. This is a good thing, because in an NP-complete problem it’s impossible to predict what will be the optimal final value for a planning variable.

Hill Climbing always takes improving moves. This may seem like a good thing, but it’s not: Hill Climbing can easily get stuck in a local optimum. This happens when it reaches a solution for which all the moves deteriorate the score. Even if it picks one of those moves, the next step might go back to the original solution and which case chasing its own tail:

Improvements upon Hill Climbing (such as Tabu Search, Simulated Annealing and Late Acceptance) address the problem of being stuck in local optima. Therefore, it’s recommend to never use Hill Climbing, unless you’re absolutely sure there are no local optima in your planning problem.

Simplest configuration:

  <localSearch>
    <localSearchType>HILL_CLIMBING</localSearchType>
  </localSearch>

Advanced configuration:

  <localSearch>
    ...
    <acceptor>
      <acceptorType>HILL_CLIMBING</acceptorType>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

Tabu Search works like Hill Climbing, but it maintains a tabu list to avoid getting stuck in local optima. The tabu list holds recently used objects that are taboo to use for now. Moves that involve an object in the tabu list, are not accepted. The tabu list objects can be anything related to the move, such as the planning entity, planning value, move, solution, …​ Here’s an example with entity tabu for 4 queens, so the queens are put in the tabu list:

Scientific paper: Tabu Search - Part 1 and Part 2 by Fred Glover (1989 - 1990)

Simplest configuration:

  <localSearch>
    <localSearchType>TABU_SEARCH</localSearchType>
  </localSearch>

When Tabu Search takes steps it creates one or more tabus. For a number of steps, it does not accept a move if that move breaks tabu. That number of steps is the tabu size. Advanced configuration:

  <localSearch>
    ...
    <acceptor>
      <entityTabuSize>7</entityTabuSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1000</acceptedCountLimit>
    </forager>
  </localSearch>

Planner implements several tabu types:

Sometimes it’s useful to combine tabu types:

    <acceptor>
      <entityTabuSize>7</entityTabuSize>
      <valueTabuSize>3</valueTabuSize>
    </acceptor>

If the tabu size is too small, the solver can still get stuck in a local optimum. On the other hand, if the tabu size is too large, the solver can be inefficient by bouncing off the walls. Use the Benchmarker to fine tweak your configuration.

Simulated Annealing evaluates only a few moves per step, so it steps quickly. In the classic implementation, the first accepted move is the winning step. A move is accepted if it doesn’t decrease the score or—​in case it does decrease the score—​it passes a random check. The chance that a decreasing move passes the random check decreases relative to the size of the score decrement and the time the phase has been running (which is represented as the temperature).

Simulated Annealing does not always pick the move with the highest score, neither does it evaluate many moves per step. At least at first. Instead, it gives non improving moves also a chance to be picked, depending on its score and the time gradient of the Termination. In the end, it gradually turns into Hill Climbing, only accepting improving moves.

Start with a simulatedAnnealingStartingTemperature set to the maximum score delta a single move can cause. Use the Benchmarker to tweak the value. Advanced configuration:

  <localSearch>
    ...
    <acceptor>
      <simulatedAnnealingStartingTemperature>2hard/100soft</simulatedAnnealingStartingTemperature>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

Simulated Annealing should use a low acceptedCountLimit. The classic algorithm uses an acceptedCountLimit of 1, but often 4 performs better.

Simulated Annealing can be combined with a tabu acceptor at the same time. That gives Simulated Annealing salted with a bit of Tabu. Use a lower tabu size than in a pure Tabu Search configuration.

  <localSearch>
    ...
    <acceptor>
      <simulatedAnnealingStartingTemperature>2hard/100soft</simulatedAnnealingStartingTemperature>
      <entityTabuSize>5</entityTabuSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

Late Acceptance (also known as Late Acceptance Hill Climbing) also evaluates only a few moves per step. A move is accepted if it does not decrease the score, or if it leads to a score that is at least the late score (which is the winning score of a fixed number of steps ago).

Scientific paper: The Late Acceptance Hill-Climbing Heuristic by Edmund K. Burke, Yuri Bykov (2012)

Simplest configuration:

  <localSearch>
    <localSearchType>LATE_ACCEPTANCE</localSearchType>
  </localSearch>

Late Acceptance accepts any move that has a score which is higher than the best score of a number of steps ago. That number of steps is the lateAcceptanceSize. Advanced configuration:

  <localSearch>
    ...
    <acceptor>
      <lateAcceptanceSize>400</lateAcceptanceSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

Late Acceptance should use a low acceptedCountLimit.

Late Acceptance can be combined with a tabu acceptor at the same time. That gives Late Acceptance salted with a bit of Tabu. Use a lower tabu size than in a pure Tabu Search configuration.

  <localSearch>
    ...
    <acceptor>
      <lateAcceptanceSize>400</lateAcceptanceSize>
      <entityTabuSize>5</entityTabuSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

Step Counting Hill Climbing also evaluates only a few moves per step. For a number of steps, it keeps the step score as a threshold. A move is accepted if it does not decrease the score, or if it leads to a score that is at least the threshold score.

Scientific paper: An initial study of a novel Step Counting Hill Climbing heuristic applied to timetabling problems by Yuri Bykov, Sanja Petrovic (2013)

Step Counting Hill Climbing accepts any move that has a score which is higher than a threshold score. Every number of steps (specified by stepCountingHillClimbingSize), the threshold score is set to the step score.

  <localSearch>
    ...
    <acceptor>
      <stepCountingHillClimbingSize>400</stepCountingHillClimbingSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1</acceptedCountLimit>
    </forager>
  </localSearch>

Step Counting Hill Climbing should use a low acceptedCountLimit.

Step Counting Hill Climbing can be combined with a tabu acceptor at the same time, similar as shown in the Late Acceptance section.

Strategic Oscillation is an add-on, which works especially well with Tabu Search. Instead of picking the accepted move with the highest score, it employs a different mechanism: If there’s an improving move, it picks it. If there’s no improving move however, it prefers moves which improve a softer score level, over moves which break a harder score level less.

Configure a finalistPodiumType, for example in a Tabu Search configuration:

  <localSearch>
    ...
    <acceptor>
      <entityTabuSize>7</entityTabuSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>1000</acceptedCountLimit>
      <finalistPodiumType>STRATEGIC_OSCILLATION</finalistPodiumType>
    </forager>
  </localSearch>

The following finalistPodiumTypes are supported:

The benchmarker is in a separate artifact called optaplanner-benchmark.

If you use Maven, add a dependency in your pom.xml file:

    <dependency>
      <groupId>org.optaplanner</groupId>
      <artifactId>optaplanner-benchmark</artifactId>
    </dependency>

This is similar for Gradle, Ivy and Buildr. The version must be exactly the same as the optaplanner-core version used (which is automatically the case if you import optaplanner-bom).

If you use Ant, you’ve probably already copied the required JARs from the downloaded ZIP’s binaries directory.

Build a PlannerBenchmark instance with a PlannerBenchmarkFactory. Configure it with a benchmark configuration XML file, provided as a classpath resource:

        PlannerBenchmarkFactory plannerBenchmarkFactory = PlannerBenchmarkFactory.createFromXmlResource(
                "org/optaplanner/examples/nqueens/benchmark/nqueensBenchmarkConfig.xml");
        PlannerBenchmark plannerBenchmark = plannerBenchmarkFactory.buildPlannerBenchmark();
        plannerBenchmark.benchmark();

A benchmark configuration file looks like this:

<?xml version="1.0" encoding="UTF-8"?>
<plannerBenchmark>
  <benchmarkDirectory>local/data/nqueens</benchmarkDirectory>

  <inheritedSolverBenchmark>
    <problemBenchmarks>
      ...
      <inputSolutionFile>data/nqueens/unsolved/32queens.xml</inputSolutionFile>
      <inputSolutionFile>data/nqueens/unsolved/64queens.xml</inputSolutionFile>
    </problemBenchmarks>
    <solver>
      ...<!-- Common solver configuration -->
    </solver>
  </inheritedSolverBenchmark>

  <solverBenchmark>
    <name>Tabu Search</name>
    <solver>
      ...<!-- Tabu Search specific solver configuration -->
    </solver>
  </solverBenchmark>
  <solverBenchmark>
    <name>Simulated Annealing</name>
    <solver>
      ...<!-- Simulated Annealing specific solver configuration -->
    </solver>
  </solverBenchmark>
  <solverBenchmark>
    <name>Late Acceptance</name>
    <solver>
      ...<!-- Late Acceptance specific solver configuration -->
    </solver>
  </solverBenchmark>
</plannerBenchmark>

This PlannerBenchmark will try 3 configurations (Tabu Search, Simulated Annealing and Late Acceptance) on 2 data sets (32queens and 64queens), so it will run 6 solvers.

Every <solverBenchmark> element contains a solver configuration and one or more <inputSolutionFile> elements. It will run the solver configuration on each of those unsolved solution files. The element name is optional, because it is generated if absent. The inputSolutionFile is read by a SolutionFileIO (relative to the working directory).

The benchmark report will be written in the directory specified the <benchmarkDirectory> element (relative to the working directory).

If an Exception or Error occurs in a single benchmark, the entire Benchmarker will not fail-fast (unlike everything else in Planner). Instead, the Benchmarker will continue to run all other benchmarks, write the benchmark report and then fail (if there is at least 1 failing single benchmark). The failing benchmarks will be clearly marked as such in the benchmark report.

Without a warm up, the results of the first (or first few) benchmarks are not reliable, because they will have lost CPU time on HotSpot JIT compilation (and possibly DRL compilation too).

To avoid that distortion, the benchmarker can run some of the benchmarks for a specified amount of time, before running the real benchmarks. Generally, a warm up of 30 seconds suffices:

<plannerBenchmark>
  ...
  <warmUpSecondsSpentLimit>30</warmUpSecondsSpentLimit>
  ...
</plannerBenchmark>

To quickly configure and run a benchmark for typical solver configs, use a solverBenchmarkBluePrint instead of solverBenchmarks:

<?xml version="1.0" encoding="UTF-8"?>
<plannerBenchmark>
  <benchmarkDirectory>local/data/nqueens</benchmarkDirectory>
  <warmUpSecondsSpentLimit>30</warmUpSecondsSpentLimit>

  <inheritedSolverBenchmark>
    <problemBenchmarks>
      <xStreamAnnotatedClass>org.optaplanner.examples.nqueens.domain.NQueens</xStreamAnnotatedClass>
      <inputSolutionFile>data/nqueens/unsolved/32queens.xml</inputSolutionFile>
      <inputSolutionFile>data/nqueens/unsolved/64queens.xml</inputSolutionFile>
      <problemStatisticType>BEST_SCORE</problemStatisticType>
    </problemBenchmarks>
    <solver>
      <scanAnnotatedClasses/>
      <scoreDirectorFactory>
        <scoreDefinitionType>SIMPLE</scoreDefinitionType>
        <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
        <initializingScoreTrend>ONLY_DOWN</initializingScoreTrend>
      </scoreDirectorFactory>
      <termination>
        <minutesSpentLimit>1</minutesSpentLimit>
      </termination>
    </solver>
  </inheritedSolverBenchmark>

  <solverBenchmarkBluePrint>
    <solverBenchmarkBluePrintType>EVERY_CONSTRUCTION_HEURISTIC_TYPE_WITH_EVERY_LOCAL_SEARCH_TYPE</solverBenchmarkBluePrintType>
  </solverBenchmarkBluePrint>
</plannerBenchmark>

The following SolverBenchmarkBluePrintTypes are supported:

The best solution of each benchmark run can be written in the benchmarkDirectory. By default, this is disabled, because the files are rarely used and considered bloat. Also, on large datasets, writing the best solution of each single benchmark can take quite some time and memory (causing an OutOfMemoryError), especially in a verbose format like XStream XML.

To write those solutions in the benchmarkDirectory, enable writeOutputSolutionEnabled:

    <problemBenchmarks>
      ...
      <writeOutputSolutionEnabled>true</writeOutputSolutionEnabled>
      ...
    </problemBenchmarks>

Benchmark logging is configured like the Solver logging.

To separate the log messages of each single benchmark run into a separate file, use the MDC with key singleBenchmark.name in a sifting appender. For example with Logback in logback.xml:

  <appender name="fileAppender" class="ch.qos.logback.classic.sift.SiftingAppender">
    <discriminator>
      <key>singleBenchmark.name</key>
      <defaultValue>app</defaultValue>
    </discriminator>
    <sift>
      <appender name="fileAppender.${singleBenchmark.name}" class="...FileAppender">
        <file>local/log/optaplannerBenchmark-${singleBenchmark.name}.log</file>
        ...
      </appender>
    </sift>
  </appender>

After running a benchmark, an HTML report will be written in the benchmarkDirectory with the index.html filename. Open it in your browser. It has a nice overview of your benchmark including:

The HTML report will use your default locale to format numbers. If you share the benchmark report with people from another country, consider overwriting the locale accordingly:

<plannerBenchmark>
  ...
  <benchmarkReport>
    <locale>en_US</locale>
  </benchmarkReport>
  ...
</plannerBenchmark>

The benchmark report automatically ranks the solvers. The Solver with rank 0 is called the favorite Solver: it performs best overall, but it might not be the best on every problem. It’s recommended to use that favorite Solver in production.

However, there are different ways of ranking the solvers. Configure it like this:

<plannerBenchmark>
  ...
  <benchmarkReport>
    <solverRankingType>TOTAL_SCORE</solverRankingType>
  </benchmarkReport>
  ...
</plannerBenchmark>

The following solverRankingTypes are supported:

Solvers with at least one failed single benchmark do not get a ranking. Solvers with not fully initialized solutions are ranked worse.

You can also use a custom ranking, by implementing a Comparator:

  <benchmarkReport>
    <solverRankingComparatorClass>...TotalScoreSolverRankingComparator</solverRankingComparatorClass>
  </benchmarkReport>

Or by implementing a SolverRankingWeightFactory:

  <benchmarkReport>
    <solverRankingWeightFactoryClass>...TotalRankSolverRankingWeightFactory</solverRankingWeightFactoryClass>
  </benchmarkReport>

Shows the best score per inputSolutionFile for each solver configuration.

Useful for visualizing the best solver configuration.

Figure 14.1. Best Score Summary Statistic

Shows the best score per problem scale for each solver configuration.

Useful for visualizing the scalability of each solver configuration.

Shows the best score distribution per inputSolutionFile for each solver configuration.

Useful for visualizing the reliability of each solver configuration.

Figure 14.2. Best Score Distribution Summary Statistic

Enable statistical benchmarking to use this summary.

Shows the winning score difference per inputSolutionFile for each solver configuration. The winning score difference is the score difference with the score of the winning solver configuration for that particular inputSolutionFile.

Useful for zooming in on the results of the best score summary.

Shows the return on investment (ROI) per inputSolutionFile for each solver configuration if you’d upgrade from the worst solver configuration for that particular inputSolutionFile.

Useful for visualizing the return on investment (ROI) to decision makers.

Shows the score calculation speed: the average calculation count per second per problem scale for each solver configuration.

Useful for comparing different score calculators and/or score rule implementations (presuming that the solver configurations do not differ otherwise). Also useful to measure the scalability cost of an extra constraint.

Shows the time spent per inputSolutionFile for each solver configuration. This is pointless if it’s benchmarking against a fixed time limit.

Useful for visualizing the performance of construction heuristics (presuming that no other solver phases are configured).

Shows the time spent per problem scale for each solver configuration. This is pointless if it’s benchmarking against a fixed time limit.

Useful for extrapolating the scalability of construction heuristics (presuming that no other solver phases are configured).

Shows the best score per time spent for each solver configuration. This is pointless if it’s benchmarking against a fixed time limit.

Useful for visualizing trade-off between the best score versus the time spent for construction heuristics (presuming that no other solver phases are configured).

The benchmarker supports outputting problem statistics as graphs and CSV (comma separated values) files to the benchmarkDirectory. To configure one, add a problemStatisticType line:

<plannerBenchmark>
  <benchmarkDirectory>local/data/nqueens/solved</benchmarkDirectory>
  <inheritedSolverBenchmark>
    <problemBenchmarks>
      ...
      <problemStatisticType>BEST_SCORE</problemStatisticType>
      <problemStatisticType>CALCULATE_COUNT_PER_SECOND</problemStatisticType>
    </problemBenchmarks>
    ...
  </inheritedSolverBenchmark>
  ...
</plannerBenchmark>

Multiple problemStatisticType elements are allowed.

The following types are supported:

To see how the best score evolves over time, add:

    <problemBenchmarks>
      ...
      <problemStatisticType>BEST_SCORE</problemStatisticType>
    </problemBenchmarks>

Figure 14.3. Best Score Over Time Statistic

The best score over time statistic is very useful to detect abnormalities, such as a potential score trap which gets the solver temporarily stuck in a local optimum.

To see how the step score evolves over time, add:

    <problemBenchmarks>
      ...
      <problemStatisticType>STEP_SCORE</problemStatisticType>
    </problemBenchmarks>

Figure 14.4. Step Score Over Time Statistic

Compare the step score statistic with the best score statistic (especially on parts for which the best score flatlines). If it hits a local optimum, the solver should take deteriorating steps to escape it. But it shouldn’t deteriorate too much either.

To see how fast the scores are calculated, add:

    <problemBenchmarks>
      ...
      <problemStatisticType>CALCULATE_COUNT_PER_SECOND</problemStatisticType>
    </problemBenchmarks>

Figure 14.5. Calculate Count Per Second Statistic

To see how much each new best solution differs from the previous best solution, by counting the number of planning variables which have a different value (not including the variables that have changed multiple times but still end up with the same value), add:

    <problemBenchmarks>
      ...
      <problemStatisticType>BEST_SOLUTION_MUTATION</problemStatisticType>
    </problemBenchmarks>

Figure 14.6. Best Solution Mutation Over Time Statistic

Use Tabu Search—​an algorithm that behaves like a human—​to get an estimation on how difficult it would be for a human to improve the previous best solution to that new best solution.

To see how the selected and accepted move count per step evolves over time, add:

    <problemBenchmarks>
      ...
      <problemStatisticType>MOVE_COUNT_PER_STEP</problemStatisticType>
    </problemBenchmarks>

Figure 14.7. Move Count Per Step Statistic

To see how much memory is used, add:

    <problemBenchmarks>
      ...
      <problemStatisticType>MEMORY_USE</problemStatisticType>
    </problemBenchmarks>

Figure 14.8. Memory Use Statistic

A single statistic is a statistic for 1 dataset for 1 solver configuration. Unlike a problem statistic, it does not aggregate over solver configurations.

The benchmarker supports outputting single statistics as graphs and CSV (comma separated values) files to the benchmarkDirectory. To configure one, add a singleStatisticType line:

<plannerBenchmark>
  <benchmarkDirectory>local/data/nqueens/solved</benchmarkDirectory>
  <inheritedSolverBenchmark>
    <problemBenchmarks>
      ...
      <problemStatisticType>...</problemStatisticType>
      <singleStatisticType>PICKED_MOVE_TYPE_BEST_SCORE_DIFF</singleStatisticType>
    </problemBenchmarks>
    ...
  </inheritedSolverBenchmark>
  ...
</plannerBenchmark>

Multiple singleStatisticType elements are allowed.

The following types are supported:

To see which constraints are matched in the best score (and how much) over time, add:

    <problemBenchmarks>
      ...
      <singleStatisticType>CONSTRAINT_MATCH_TOTAL_BEST_SCORE</singleStatisticType>
    </problemBenchmarks>

Figure 14.9. Constraint Match Total Best Score Diff Over Time Statistic

Requires the score calculation to support constraint matches. Drools score calculation supports constraint matches automatically, but incremental Java score calculation requires more work.

To see which constraints are matched in the step score (and how much) over time, add:

    <problemBenchmarks>
      ...
      <singleStatisticType>CONSTRAINT_MATCH_TOTAL_STEP_SCORE</singleStatisticType>
    </problemBenchmarks>

Figure 14.10. Constraint Match Total Step Score Diff Over Time Statistic

Requires the score calculation to support constraint matches. Drools score calculation supports constraint matches automatically, but incremental Java score calculation requires more work.

To see which move types improve the best score (and how much) over time, add:

    <problemBenchmarks>
      ...
      <singleStatisticType>PICKED_MOVE_TYPE_BEST_SCORE_DIFF</singleStatisticType>
    </problemBenchmarks>

Figure 14.11. Picked Move Type Best Score Diff Over Time Statistic

To see how much each winning step affects the step score over time, add:

    <problemBenchmarks>
      ...
      <singleStatisticType>PICKED_MOVE_TYPE_STEP_SCORE_DIFF</singleStatisticType>
    </problemBenchmarks>

Figure 14.12. Picked Move Type Step Score Diff Over Time Statistic

To minimize the influence of your environment and the Random Number Generator on the benchmark results, configure the number of times each single benchmark run is repeated. The results of those runs are statistically aggregated. Each individual result is also visible in the report, as well as plotted in the best score distribution summary.

Just add a <subSingleCount> element to an <inheritedSolverBenchmark> element or in a <solverBenchmark> element:

<?xml version="1.0" encoding="UTF-8"?>
<plannerBenchmark>
  ...
  <inheritedSolverBenchmark>
    ...
    <solver>
      ...
    </solver>
    <subSingleCount>10<subSingleCount>
  </inheritedSolverBenchmark>
  ...
</plannerBenchmark>

The subSingleCount defaults to 1 (so no statistical benchmarking).

Matrix benchmarking is benchmarking a combination of value sets. For example: benchmark 4 entityTabuSize values (5, 7, 11 and 13) combined with 3 acceptedCountLimit values (500, 1000 and 2000), resulting in 12 solver configurations.

To reduce the verbosity of such a benchmark configuration, you can use a FreeMarker template for the benchmark configuration instead:

<plannerBenchmark>
  ...

  <inheritedSolverBenchmark>
    ...
  </inheritedSolverBenchmark>

<#list [5, 7, 11, 13] as entityTabuSize>
<#list [500, 1000, 2000] as acceptedCountLimit>
  <solverBenchmark>
    <name>entityTabuSize ${entityTabuSize} acceptedCountLimit ${acceptedCountLimit}</name>
    <solver>
      <localSearch>
        <unionMoveSelector>
          <changeMoveSelector/>
          <swapMoveSelector/>
        </unionMoveSelector>
        <acceptor>
          <entityTabuSize>${entityTabuSize}</entityTabuSize>
        </acceptor>
        <forager>
          <acceptedCountLimit>${acceptedCountLimit}</acceptedCountLimit>
        </forager>
      </localSearch>
    </solver>
  </solverBenchmark>
</#list>
</#list>
</plannerBenchmark>

And build it with the class PlannerBenchmarkFactory:

        PlannerBenchmarkFactory plannerBenchmarkFactory = PlannerBenchmarkFactory.createFromFreemarkerXmlResource(
                "org/optaplanner/examples/cloudbalancing/benchmark/cloudBalancingBenchmarkConfigTemplate.xml.ftl");
        PlannerBenchmark plannerBenchmark = plannerBenchmarkFactory.buildPlannerBenchmark();

The BenchmarkAggregator takes 1 or more existing benchmarks and merges them into new benchmark report, without actually running the benchmarks again.

This is useful to:

To use it, provide a PlannerBenchmarkFactory to the BenchmarkAggregatorFrame to display the GUI:

    public static void main(String[] args) {
        PlannerBenchmarkFactory plannerBenchmarkFactory = PlannerBenchmarkFactory.createFromXmlResource(
                "org/optaplanner/examples/nqueens/benchmark/nqueensBenchmarkConfig.xml");
        BenchmarkAggregatorFrame.createAndDisplay(plannerBenchmarkFactory);
    }

In the GUI, select the interesting benchmarks and click the button to generate the report.

To make some planning entities immovable, simply add an entity SelectionFilter that returns true if an entity is movable and false if it is immovable.

public class MovableShiftAssignmentSelectionFilter implements SelectionFilter<ShiftAssignment> {

    public boolean accept(ScoreDirector scoreDirector, ShiftAssignment shiftAssignment) {
        ShiftDate shiftDate = shiftAssignment.getShift().getShiftDate();
        NurseRoster nurseRoster = (NurseRoster) scoreDirector.getWorkingSolution();
        return nurseRoster.getNurseRosterInfo().isInPlanningWindow(shiftDate);
    }

}

And configure it like this:

@PlanningEntity(movableEntitySelectionFilter = MovableShiftAssignmentSelectionFilter.class)
public class ShiftAssignment {
    ...
}

Replanning an existing plan can be very disruptive on the plan. If the plan affects humans (such as employees, drivers, …​), very disruptive changes are often undesirable. In such cases, nonvolatile replanning helps: the gain of changing a plan must be higher than the disruption it causes.

For example, in the Machine Reassignment example, the entity has both the planning variable machine and its original value originalMachine:

@PlanningEntity(...)
public class ProcessAssignment {

    private MrProcess process;
    private Machine originalMachine;
    private Machine machine;

    public Machine getOriginalMachine() {...}

    @PlanningVariable(...)
    public Machine getMachine() {...}

    public boolean isMoved() {
        return originalMachine != null && originalMachine != machine;
    }

    ...
}

During planning, the planning variable machine changes. By comparing it with the originalMachine, a change in plan can be penalized:

rule "processMoved"
    when
        ProcessAssignment(moved == true)
    then
        scoreHolder.addSoftConstraintMatch(kcontext, -1000);
end

The soft penalty of -1000 means that a better solution is only accepted if it improves the soft score for at least 1000 points per variable changed (or if it improves the hard score).

While the Solver is solving, an outside event might want to change one of the problem facts, for example an airplane is delayed and needs the runway at a later time. Do not change the problem fact instances used by the Solver while it is solving (from another thread or even in the same thread), as that will corrupt it. Instead, add a ProblemFactChange to the Solver which it will execute in the solver thread as soon as possible.

public interface Solver {

    ...

    boolean addProblemFactChange(ProblemFactChange problemFactChange);

    boolean isEveryProblemFactChangeProcessed();

    ...

}

public interface ProblemFactChange {

    void doChange(ScoreDirector scoreDirector);

}

Here’s an example:

    public void deleteComputer(final CloudComputer computer) {
        solver.addProblemFactChange(new ProblemFactChange() {
            public void doChange(ScoreDirector scoreDirector) {
                CloudBalance cloudBalance = (CloudBalance) scoreDirector.getWorkingSolution();
                // First remove the problem fact from all planning entities that use it
                for (CloudProcess process : cloudBalance.getProcessList()) {
                    if (ObjectUtils.equals(process.getComputer(), computer)) {
                        scoreDirector.beforeVariableChanged(process, "computer");
                        process.setComputer(null);
                        scoreDirector.afterVariableChanged(process, "computer");
                    }
                }
                // A SolutionCloner does not clone problem fact lists (such as computerList)
                // Shallow clone the computerList so only workingSolution is affected, not bestSolution or guiSolution
                cloudBalance.setComputerList(new ArrayList<CloudComputer>(cloudBalance.getComputerList()));
                // Next remove it the problem fact itself
                for (Iterator<CloudComputer> it = cloudBalance.getComputerList().iterator(); it.hasNext(); ) {
                    CloudComputer workingComputer = it.next();
                    if (ObjectUtils.equals(workingComputer, computer)) {
                        scoreDirector.beforeProblemFactRemoved(workingComputer);
                        it.remove(); // remove from list
                        scoreDirector.afterProblemFactRemoved(workingComputer);
                        break;
                    }
                }
            }
        });
    }