Dieser Inhalt ist in der von Ihnen ausgewählten Sprache nicht verfügbar.
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:
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 Link kopierenLink in die Zwischenablage kopiert!
Use the solver to solve a planning problem.
Prerequisites
-
A
Solverbuilt from a solver configuration -
An
@PlanningSolutionannotation 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);
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.
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)
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.
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 Link kopierenLink in die Zwischenablage kopiert!
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>
<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_ASSERTmode 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 methodcalculateScore()more frequently than a non-assert mode. TheFULL_ASSERTmode is very slow because it does not rely on incremental score calculation.
-
NON_INTRUSIVE_FULL_ASSERTmode 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 methodcalculateScore()more frequently than a non assert mode. TheNON_INTRUSIVE_FULL_ASSERTmode is very slow because it does not rely on incremental score calculation.
-
FAST_ASSERTmode 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 methodcalculateScore()more frequently than a non-assert mode. TheFAST_ASSERTmode is slow. Write a test case that does a short run of your planning problem with theFAST_ASSERTmode on.
REPRODUCIBLEmode 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.NoteDespite using
REPRODCIBLEmode, your application might still not be fully reproducible for the following reasons:-
Use of
HashSetor anotherCollectionwhich 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 withLinkedHashSet. - 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.
-
Use of
-
REPRODUCIBLEmode can be slightly slower thanNON_REPRODUCIBLEmode. If your production environment can benefit from reproducibility, use this mode in production. In practice,REPRODUCIBLEmode uses the default fixed random seed if no seed is specified and it also disables certain concurrency optimizations such as work stealing.
-
NON_REPRODUCIBLEmode can be slightly faster thanREPRODUCIBLEmode. Avoid using it during development because it makes debugging and bug fixing difficult. If reproducibility isn’t important in your production environment, useNON_REPRODUCIBLEmode in production. In practice, this mode uses no fixed random seed if no seed is specified.
8.3. Changing the OptaPlanner solver logging level Link kopierenLink in die Zwischenablage kopiert!
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
RuntimeExceptionwith 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 thatRuntimeException, aThread’s default `ExceptionHandlerwill 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
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:
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 Link kopierenLink in die Zwischenablage kopiert!
Logback is the recommended logging frameworkd to use with OptaPlanner. Use Logback to log OptaPlanner solver activity.
Prerequisites
- You have an OptaPlanner project.
Procedure
Add the following Maven dependency to your OptaPlanner project’s
pom.xmlfile:NoteYou do not need to add an extra bridge dependency.
<dependency> <groupId>ch.qos.logback</groupId> <artifactId>logback-classic</artifactId> <version>1.x</version> </dependency><dependency> <groupId>ch.qos.logback</groupId> <artifactId>logback-classic</artifactId> <version>1.x</version> </dependency>Copy to Clipboard Copied! Toggle word wrap Toggle overflow Configure the logging level on the
org.optaplannerpackage in yourlogback.xmlfile as shown in the following example where<LEVEL>is a logging level listed in Section 8.4, “Using Logback to log OptaPlanner solver activity”.Copy to Clipboard Copied! Toggle word wrap Toggle overflow Optional: If you have a multitenant application where multiple
Solverinstances might be running at the same time, separate the logging of each instance into separate files:Surround the
solve()call with Mapped Diagnostic Context (MDC):MDC.put("tenant.name",tenantName); MySolution bestSolution = solver.solve(problem); MDC.remove("tenant.name");MDC.put("tenant.name",tenantName); MySolution bestSolution = solver.solve(problem); MDC.remove("tenant.name");Copy to Clipboard Copied! Toggle word wrap Toggle overflow Configure your logger to use different files for each
${tenant.name}. For example, use aSiftingAppenderin thelogback.xmlfile:Copy to Clipboard Copied! Toggle word wrap Toggle overflow NoteWhen running multiple solvers or one multithreaded solve, most appenders, including the console, cause congestion with
debugandtracelogging. Switch to an async appender to avoid this problem or turn offdebuglogging.
-
If OptaPlanner doesn’t recognize the new level, temporarily add the system property
-Dlogback.LEVEL=trueto troubleshoot.
8.5. Using Log4J to log OptaPlanner solver activity Link kopierenLink in die Zwischenablage kopiert!
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
Add the bridge dependency to the project
pom.xmlfile:<dependency> <groupId>org.slf4j</groupId> <artifactId>slf4j-log4j12</artifactId> <version>1.x</version> </dependency><dependency> <groupId>org.slf4j</groupId> <artifactId>slf4j-log4j12</artifactId> <version>1.x</version> </dependency>Copy to Clipboard Copied! Toggle word wrap Toggle overflow Configure the logging level on the package
org.optaplannerin yourlog4j.xmlfile as shown in the following example, where<LEVEL>is a logging level listed in Section 8.4, “Using Logback to log OptaPlanner solver activity”.Copy to Clipboard Copied! Toggle word wrap Toggle overflow Optional: If you have a multitenant application where multiple
Solverinstances might be running at the same time, separate the logging of each instance into separate files:Surround the
solve()call with Mapped Diagnostic Context (MDC):MDC.put("tenant.name",tenantName); MySolution bestSolution = solver.solve(problem); MDC.remove("tenant.name");MDC.put("tenant.name",tenantName); MySolution bestSolution = solver.solve(problem); MDC.remove("tenant.name");Copy to Clipboard Copied! Toggle word wrap Toggle overflow Configure your logger to use different files for each
${tenant.name}. For example, use aSiftingAppenderin thelogback.xmlfile:Copy to Clipboard Copied! Toggle word wrap Toggle overflow NoteWhen running multiple solvers or one multithreaded solve, most appenders, including the console, cause congestion with
debugandtracelogging. Switch to an async appender to avoid this problem or turn offdebuglogging.
8.6. Monitoring the solver Link kopierenLink in die Zwischenablage kopiert!
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 Link kopierenLink in die Zwischenablage kopiert!
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
Add the following dependency to your application’s
pom.xmlfile where<MONITORING_SYSTEM>is a monitoring system supported by Micrometer and Quarkus:NotePrometheus is currently the only monitoring system supported by Quarkus.
<dependency> <groupId>io.quarkus</groupId> <artifactId>quarkus-micrometer-registry-<MONITORING_SYSTEM></artifactId> </dependency>
<dependency> <groupId>io.quarkus</groupId> <artifactId>quarkus-micrometer-registry-<MONITORING_SYSTEM></artifactId> </dependency>Copy to Clipboard Copied! Toggle word wrap Toggle overflow To run the application in development mode, enter the following command:
mvn compile quarkus:dev
mvn compile quarkus:devCopy to Clipboard Copied! Toggle word wrap Toggle overflow To view metrics for your application, enter the following URL in a browser:
http://localhost:8080/q/metrics
http://localhost:8080/q/metricsCopy to Clipboard Copied! Toggle word wrap Toggle overflow
8.6.2. Configuring a Spring Boot OptaPlanner application for Micrometer Link kopierenLink in die Zwischenablage kopiert!
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
Add the following dependency to your application’s
pom.xmlfile where<MONITORING_SYSTEM>is a monitoring system supported by Micrometer and Spring Boot:Copy to Clipboard Copied! Toggle word wrap Toggle overflow -
Add configuration information to the application’s
application.propertiesfile. For information, see the Micrometer web site. To run the application, enter the following command:
mvn spring-boot:run
mvn spring-boot:runCopy to Clipboard Copied! Toggle word wrap Toggle overflow To view metrics for your application, enter the following URL in a browser:
http://localhost:8080/actuator/metrics
NoteUse the following URL as the Prometheus scraper path:
http://localhost:8080/actuator/prometheus
8.6.3. Configuring a plain Java OptaPlanner application for Micrometer Link kopierenLink in die Zwischenablage kopiert!
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
Add the following dependencies to your application’s
pom.xmlfile where<MONITORING_SYSTEM>is a monitoring system that is configured with Micrometer and<VERSION>is the version of Micrometer that you are using:Copy to Clipboard Copied! Toggle word wrap Toggle overflow -
Add Micrometer configuration information for your monitoring system to the beginning of your project’s
pom.xmlfile. For information, see the Micrometer web site. Add the following line below the configuration information, where
<MONITORING_SYSTEM>is the monitoring system that you added:Metrics.addRegistry(<MONITORING_SYSTEM>);
Metrics.addRegistry(<MONITORING_SYSTEM>);Copy to Clipboard Copied! Toggle word wrap Toggle overflow The following example shows how to add the Prometheus monitoring system:
Copy to Clipboard Copied! Toggle word wrap Toggle overflow Open your monitoring system to view the metrics for your OptaPlanner project. The following metrics are exposed:
NoteThe 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.6.4. Additional Metrics Link kopierenLink in die Zwischenablage kopiert!
For more detailed monitoring, you can configure OptaPlanner in the solver configuration to monitor additional metrics at a performance cost. The following example uses the BEST_SCORE and SCORE_CALCULATION_COUNT metric :
You can enable the following metrics in this configuration:
-
SOLVE_DURATION(enabled by default, Micrometer meter ID:optaplanner.solver.solve.duration): Measures the duration of solving for the longest active solver, the number of active solvers, and the cumulative duration of all active solvers. -
ERROR_COUNT(enabled by default, Micrometer meter ID:optaplanner.solver.errors): Measures the number of errors that occurred while solving. -
SCORE_CALCULATION_COUNT(enabled by default, Micrometer meter ID:optaplanner.solver.score.calculation.count): Measures the number of score calculations the OptaPlanner performed. -
BEST_SCORE(Micrometer meter ID:optaplanner.solver.best.score.*): Measures the score of the best solution that OptaPlanner has found so far. There are separate meters for each level of the score. For instance, for aHardSoftScore, there areoptaplanner.solver.best.score.hard.scoreandoptaplanner.solver.best.score.soft.scoremeters. -
STEP_SCORE(Micrometer meter ID:optaplanner.solver.step.score.*): Measures the score of each step that OptaPlanner takes. There are separate meters for each level of the score. For instance, for aHardSoftScore, there areoptaplanner.solver.step.score.hard.scoreandoptaplanner.solver.step.score.soft.scoremeters. -
BEST_SOLUTION_MUTATION(Micrometer meter ID:optaplanner.solver.best.solution.mutation): Measures the number of changed planning variables between consecutive best solutions. -
MOVE_COUNT_PER_STEP(Micrometer meter ID:optaplanner.solver.step.move.count): Measures the number of moves evaluated in a step. -
MEMORY_USE(Micrometer meter ID:jvm.memory.used): Measures the amount of memory used across the JVM. This metric does not measure the amount of memory used by a solver; two solvers on the same JVM will report the same value for this metric. -
CONSTRAINT_MATCH_TOTAL_BEST_SCORE(Micrometer meter ID:optaplanner.solver.constraint.match.best.score.*): Measures the score impact of each constraint on the best solution that OptaPlanner has found so far. There are separate meters for each level of the score, with tags for each constraint. For instance, for aHardSoftScorefor a constraint "Minimize Cost" in package "com.example", there areoptaplanner.solver.constraint.match.best.score.hard.scoreandoptaplanner.solver.constraint.match.best.score.soft.scoremeters with tags "constraint.package=com.example" and "constraint.name=Minimize Cost". -
CONSTRAINT_MATCH_TOTAL_STEP_SCORE(Micrometer meter ID:optaplanner.solver.constraint.match.step.score.*): Measures the score impact of each constraint on the current step. There are separate meters for each level of the score, with tags for each constraint. For instance, for aHardSoftScorefor a constraint "Minimize Cost" in package "com.example", there areoptaplanner.solver.constraint.match.step.score.hard.scoreandoptaplanner.solver.constraint.match.step.score.soft.scoremeters with tags "constraint.package=com.example" and "constraint.name=Minimize Cost". -
PICKED_MOVE_TYPE_BEST_SCORE_DIFF(Micrometer meter ID:optaplanner.solver.move.type.best.score.diff.*): Measures how much a particular move type improves the best solution. There are separate meters for each level of the score, with a tag for the move type. For instance, for aHardSoftScoreand aChangeMovefor the computer of a process, there areoptaplanner.solver.move.type.best.score.diff.hard.scoreandoptaplanner.solver.move.type.best.score.diff.soft.scoremeters with the tagmove.type=ChangeMove(Process.computer). -
PICKED_MOVE_TYPE_STEP_SCORE_DIFF(Micrometer meter ID:optaplanner.solver.move.type.step.score.diff.*): Measures how much a particular move type improves the best solution. There are separate meters for each level of the score, with a tag for the move type. For instance, for aHardSoftScoreand aChangeMovefor the computer of a process, there areoptaplanner.solver.move.type.step.score.diff.hard.scoreandoptaplanner.solver.move.type.step.score.diff.soft.scoremeters with the tagmove.type=ChangeMove(Process.computer).
8.7. Configuring the random number generator Link kopierenLink in die Zwischenablage kopiert!
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
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><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>Copy to Clipboard Copied! Toggle word wrap Toggle overflow Optional: To change the pseudorandom number generator implementation, specify a value for the
randomTypeproperty 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><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>Copy to Clipboard Copied! Toggle word wrap Toggle overflow 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,WELL44497AandWELL44497B: 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.