Chapter 8. The OptaPlanner Solver

A solver finds the best and optimal solution to your planning problem. A solver can only solve one planning problem instance at a time. Solvers are built with the SolverFactory method: 

public interface Solver<Solution_> {

    Solution_ solve(Solution_ problem);

    ...
}

A solver should only be accessed from a single thread, except for the methods that are specifically documented in javadoc as being thread-safe. The solve() method hogs the current thread. Hogging the thread can cause HTTP timeouts for REST services and it requires extra code to solve multiple data sets in parallel. To avoid such issues, use a SolverManager instead.

8.1. Solving a problem

Use the solver to solve a planning problem.

Prerequisites

  • A Solver built from a solver configuration
  • An @PlanningSolution annotation that represents the planning problem instance

Procedure

Provide the planning problem as an argument to the solve() method. The solver will return the best solution found.

The following example solves the NQueens problem: 

    NQueens problem = ...;
    NQueens bestSolution = solver.solve(problem);

In this example, the solve() method will return an NQueens instance with every Queen assigned to a Row.

Note

The solution instance given to the solve(Solution) method can be partially or fully initialized, which is often the case in repeated planning.

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

solvedNQueens04

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

Note

The solution instance given to the method solve(Solution) is changed by the Solver, but do not mistake it for the best solution.

The solution instance returned by the methods solve(Solution) or getBestSolution() is most likely a planning clone of the instance given to the method solve(Solution), which implies it is a different instance.

8.2. Solver environment mode

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

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

You can set the environment mode in the solver configuration XML file. The following example sets the FAST_ASSERT mode: 

<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <environmentMode>FAST_ASSERT</environmentMode>
  ...
</solver>

The following list describes the environment modes that you can use in the solver configuration file:

  • FULL_ASSERT mode turns on all assertions, for example the assertion that the incremental score calculation is uncorrupted for each move, to fail-fast on a bug in a Move implementation, a constraint, the engine itself, and so on. This mode is reproducible. It is also intrusive because it calls the method calculateScore() more frequently than a non-assert mode. The FULL_ASSERT mode is very slow because it does not rely on incremental score calculation.
  • NON_INTRUSIVE_FULL_ASSERT mode turns on several assertions to fail-fast on a bug in a Move implementation, a constraint, the engine itself, and so on. This mode is reproducible. It is non-intrusive because it does not call the method calculateScore() more frequently than a non assert mode. The NON_INTRUSIVE_FULL_ASSERT mode is very slow because it does not rely on incremental score calculation.
  • FAST_ASSERT mode turns on most assertions, such as the assertions that an undoMove’s score is the same as before the Move, to fail-fast on a bug in a Move implementation, a constraint, the engine itself, and so on. This mode is reproducible. It is also intrusive because it calls the method calculateScore() more frequently than a non-assert mode. The FAST_ASSERT mode is slow. Write a test case that does a short run of your planning problem with the FAST_ASSERT mode on.

  • REPRODUCIBLE mode is the default mode because it is recommended during development. In this mode, two runs in the same OptaPlanner version execute the same code in the same order. Those two runs have the same result at every step, except if the following note applies. This enables you to reproduce bugs consistently. It also enables you to benchmark certain refactorings, such as a score constraint performance optimization, fairly across runs.

    Note

    Despite using REPRODCIBLE mode, your application might still not be fully reproducible for the following reasons:

    • Use of HashSet or another Collection which has an inconsistent order between JVM runs for collections of planning entities or planning values but not normal problem facts, especially in the solution implementation. Replace it with LinkedHashSet.
    • Combining a time gradient dependent algorithm, most notably the Simulated Annealing algorithm, together with time spent termination. A sufficiently large difference in allocated CPU time will influence the time gradient values. Replace the Simulated Annealing algorithms with the Late Acceptance algorithm, or replace time spent termination with step count termination.
  • REPRODUCIBLE mode can be slightly slower than NON_REPRODUCIBLE mode. If your production environment can benefit from reproducibility, use this mode in production. In practice, REPRODUCIBLE mode uses the default fixed random seed if no seed is specified and it also disables certain concurrency optimizations such as work stealing.
  • NON_REPRODUCIBLE mode can be slightly faster than REPRODUCIBLE mode. Avoid using it during development because it makes debugging and bug fixing difficult. If reproducibility isn’t important in your production environment, use NON_REPRODUCIBLE mode in production. In practice, this mode uses no fixed random seed if no seed is specified.

8.3. Changing the OptaPlanner solver logging level

You can change the logging level in an OptaPlanner solver to review solver activity. The following list describes the different logging levels:

  • error: Logs errors, except those that are thrown to the calling code as a RuntimeException.

    If an error occurs, OptaPlanner normally fails fast. It throws a subclass of RuntimeException with a detailed message to the calling code. To avoid duplicate log messages, it does not log it as an error. Unless the calling code explicitly catches and eliminates that RuntimeException, a Thread’s default `ExceptionHandler will log it as an error anyway. Meanwhile, the code is disrupted from doing further harm or obfuscating the error.

  • warn: Logs suspicious circumstances
  • info: Logs every phase and the solver itself
  • debug: Logs every step of every phase
  • trace: Logs every move of every step of every phase
Note

Specifying trace logging will slow down performance considerably. However, trace logging is invaluable during development to discover a bottleneck.

Even debug logging can slow down performance considerably for fast stepping algorithms such as Late Acceptance and Simulated Annealing, but not for slow stepping algorithms such as Tabu Search.

Both trace` and debug logging cause congestion in multithreaded solving with most appenders.

In Eclipse, debug logging to the console tends to cause congestion with score calculation speeds above 10000 per second. Neither IntelliJ or the Maven command line suffer from this problem.

Procedure

Set the logging level to debug logging to see when the phases end and how fast steps are taken.

The following example shows output from debug logging: 

INFO  Solving started: time spent (3), best score (-4init/0), random (JDK with seed 0).
DEBUG     CH step (0), time spent (5), score (-3init/0), selected move count (1), picked move (Queen-2 {null -> Row-0}).
DEBUG     CH step (1), time spent (7), score (-2init/0), selected move count (3), picked move (Queen-1 {null -> Row-2}).
DEBUG     CH step (2), time spent (10), score (-1init/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: time spent (12), best score (-1), score calculation speed (9000/sec), step total (4).
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: time spent (24), best score (0), score calculation speed (4000/sec), step total (2).
INFO  Solving ended: time spent (24), best score (0), score calculation speed (7000/sec), phase total (2), environment mode (REPRODUCIBLE).

All time spent values are in milliseconds.

Everything is logged to SLF4J, which is a simple logging facade that 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.

8.4. Using Logback to log OptaPlanner solver activity

Logback is the recommended logging frameworkd to use with OptaPlanner. Use Logback to log OptaPlanner solver activity.

Prerequisites

  • You have an OptaPlanner project.

Procedure

  1. Add the following Maven dependency to your OptaPlanner project’s pom.xml file:

    Note

    You do not need to add an extra bridge dependency. 

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

  2. Configure the logging level on the org.optaplanner package in your logback.xml file as shown in the following example where <LEVEL> is a logging level listed in Section 8.4, “Using Logback to log OptaPlanner solver activity”. 

    <configuration>

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

  ...

</configuration>

  3. Optional: If you have a multitenant application where multiple Solver instances might be running at the same time, separate the logging of each instance into separate files:

    1. Surround the solve() call with Mapped Diagnostic Context (MDC): 

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

    2. Configure your logger to use different files for each ${tenant.name}. For example, use a SiftingAppender in the logback.xml file: 

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

      When running multiple solvers or one multithreaded solve, most appenders, including the console, cause congestion with debug and trace logging. Switch to an async appender to avoid this problem or turn off debug logging.

  4. If OptaPlanner doesn’t recognize the new level, temporarily add the system property -Dlogback.LEVEL=true to troubleshoot.

8.5. Using Log4J to log OptaPlanner solver activity

If you are already using Log4J and you do not want to switch to its faster successor, Logback, you can configure your OptaPlanner project for Log4J.

Prerequisites

  • You have an OptaPlanner project
  • You are using the Log4J logging framework

Procedure

  1. Add the bridge dependency to the project pom.xml file: 

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

  2. Configure the logging level on the package org.optaplanner in your log4j.xml file as shown in the following example, where <LEVEL> is a logging level listed in Section 8.4, “Using Logback to log OptaPlanner solver activity”. 

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

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

  ...

</log4j:configuration>

  3. Optional: If you have a multitenant application where multiple Solver instances might be running at the same time, separate the logging of each instance into separate files:

    1. Surround the solve() call with Mapped Diagnostic Context (MDC): 

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

    2. Configure your logger to use different files for each ${tenant.name}. For example, use a SiftingAppender in the logback.xml file: 

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

      When running multiple solvers or one multithreaded solve, most appenders, including the console, cause congestion with debug and trace logging. Switch to an async appender to avoid this problem or turn off debug logging.

8.6. Monitoring the solver

OptaPlanner exposes metrics through Micrometer, a metrics instrumentation library for Java applications. You can use Micrometer with popular monitoring systems to monitor the OptaPlanner solver.

8.6.1. Configuring a Quarkus OptaPlanner application for Micrometer

To configure your OptaPlanner Quarkus application to use Micrometer and a specified monitoring system, add the Micrometer dependency to the pom.xml file.

Prerequisites

  • You have a Quarkus OptaPlanner application.

Procedure

  1. Add the following dependency to your application’s pom.xml file where <MONITORING_SYSTEM> is a monitoring system supported by Micrometer and Quarkus:

    Note

    Prometheus is currently the only monitoring system supported by Quarkus. 

    <dependency>
 <groupId>io.quarkus</groupId>
 <artifactId>quarkus-micrometer-registry-<MONITORING_SYSTEM></artifactId>
</dependency>

  2. To run the application in development mode, enter the following command: 

    mvn compile quarkus:dev

  3. To view metrics for your application, enter the following URL in a browser: 

    http://localhost:8080/q/metrics

8.6.2. Configuring a Spring Boot OptaPlanner application for Micrometer

To configure your Spring Boot OptaPlanner application to use Micrometer and a specified monitoring system, add the Micrometer dependency to the pom.xml file.

Prerequisites

  • You have a Spring Boot OptaPlanner application.

Procedure

  1. Add the following dependency to your application’s pom.xml file where <MONITORING_SYSTEM> is a monitoring system supported by Micrometer and Spring Boot: 

    <dependency>
 <groupId>org.springframework.boot</groupId>
 <artifactId>spring-boot-starter-actuator</artifactId>
</dependency>
<dependency>
 <groupId>io.micrometer</groupId>
 <artifactId>micrometer-registry-<MONITORING_SYSTEM></artifactId>
</dependency>
  2. Add configuration information to the application’s application.properties file. For information, see the Micrometer web site.

  3. To run the application, enter the following command: 

    mvn spring-boot:run

  4. To view metrics for your application, enter the following URL in a browser:

    http://localhost:8080/actuator/metrics

    Note

    Use the following URL as the Prometheus scraper path: http://localhost:8080/actuator/prometheus

8.6.3. Configuring a plain Java OptaPlanner application for Micrometer

To configuring a plain Java OptaPlanner application to use Micrometer, you must add Micrometer dependencies and configuration information for your chosen monitoring system to your project’s POM.XML file.

Prerequisites

  • You have a plain Java OptaPlanner application.

Procedure

  1. Add the following dependencies to your application’s pom.xml file where <MONITORING_SYSTEM> is a monitoring system that is configured with Micrometer and <VERSION> is the version of Micrometer that you are using: 

    <dependency>
 <groupId>io.micrometer</groupId>
 <artifactId>micrometer-registry-<MONITORING_SYSTEM></artifactId>
 <version><VERSION></version>
</dependency>
<dependency>
 <groupId>io.micrometer</groupId>
 <artifactId>micrometer-core</artifactId>
 <version>`<VERSION>`</version>
</dependency>
  2. Add Micrometer configuration information for your monitoring system to the beginning of your project’s pom.xml file. For information, see the Micrometer web site.

  3. Add the following line below the configuration information, where <MONITORING_SYSTEM> is the monitoring system that you added: 

    Metrics.addRegistry(<MONITORING_SYSTEM>);

    The following example shows how to add the Prometheus monitoring system: 

    PrometheusMeterRegistry prometheusRegistry = new PrometheusMeterRegistry(PrometheusConfig.DEFAULT);
try {
    HttpServer server = HttpServer.create(new InetSocketAddress(8080), 0);
    server.createContext("/prometheus", httpExchange -> {
        String response = prometheusRegistry.scrape();
        httpExchange.sendResponseHeaders(200, response.getBytes().length);
        try (OutputStream os = httpExchange.getResponseBody()) {
            os.write(response.getBytes());
        }
    });
    new Thread(server::start).start();
} catch (IOException e) {
    throw new RuntimeException(e);
}
Metrics.addRegistry(prometheusRegistry);

  4. Open your monitoring system to view the metrics for your OptaPlanner project. The following metrics are exposed:

    Note

    The names and format of the metrics vary depending on the registry.

    • optaplanner.solver.errors.total: the total number of errors that occurred while solving since the start of the measuring.
    • optaplanner.solver.solve-length.active-count: the number of solvers currently solving.
    • optaplanner.solver.solve-length.seconds-max: run time of the longest-running currently active solver.
    • optaplanner.solver.solve-length.seconds-duration-sum: the sum of each active solver’s solve duration. For example, if there are two active solvers, one running for three minutes and the other for one minute, the total solve time is four minutes.

8.7. Configuring the random number generator

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

A random seed is a number used to initialize a pseudorandom number generator.

Procedure

  1. Optional: To change the random seed of a random instance, specify a randomSeed: 

    <solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <randomSeed>0</randomSeed>
  ...
</solver>

  2. Optional: To change the pseudorandom number generator implementation, specify a value for the randomType property listed in the solver configuration file below, where <RANDOM_NUMBER_GENERATOR> is a pseudorandom number generator: 

    <solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <randomType><RANDOM_NUMBER_GENERATOR></randomType>
  ...
</solver>

    The following pseudorandom number generators are supported:

    • JDK (default): Standard random number generator implementation (java.util.Random)
    • MERSENNE_TWISTER: Random number generator implementation by Commons Math
    • WELL512A, WELL1024A, WELL19937A, WELL19937C, WELL44497A and WELL44497B: Random number generator implementation by Commons Math

For most use cases, the value of the randomType property has no significant impact on the average quality of the best solution on multiple data sets.