[[benchmarker]]
= Benchmarking and tweaking
:doctype: book
:imagesdir: ..
:sectnums:
:toc: left
:icons: font
:experimental:


[[findTheBestSolverConfiguration]]
== Find the best solver configuration

OptaPlanner supports several optimization algorithms, so you're probably wondering which is the best one?
Although some optimization algorithms generally perform better than others, it really depends on your problem domain.
Most solver phases have parameters which can be tweaked.
Those parameters can influence the results a lot, even though most solver phases work pretty well out-of-the-box.

Luckily, OptaPlanner includes a benchmarker, which allows you to play out different solver phases with different settings
against each other in development, so you can use the best configuration for your planning problem in production.

image::BenchmarkingAndTweaking/benchmarkOverview.png[align="center"]


[[benchmarkConfiguration]]
== Benchmark configuration


[[addADependencyOnBenchmarkJar]]
=== Add a dependency on `optaplanner-benchmark`

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

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

[source,xml,options="nowrap"]
----
    <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 download zip's [path]_binaries_
 directory.

[[runASimpleBenchmark]]
=== Run a simple benchmark

To quickly setup a benchmark, create a `PlannerBenchmarkFactory` from your solver configuration XML,
load a few datasets and benchmark them. For example, with 3 datasets:

[source,java,options="nowrap"]
----
PlannerBenchmarkFactory benchmarkFactory = PlannerBenchmarkFactory.createFromSolverConfigXmlResource(
        "org/optaplanner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml");

CloudBalance dataset1 = ...;
CloudBalance dataset2 = ...;
CloudBalance dataset3 = ...;
PlannerBenchmark benchmark = benchmarkFactory.buildPlannerBenchmark(
        dataset1, dataset2, dataset3);
benchmark.benchmarkAndShowReportInBrowser();
----

This generates a benchmark report in `local/benchmarkReport` and shows it in your browser when it's finished.
The ``SolverFactory``'s solver configuration needs a termination to limit how long each dataset runs.
To configure a different benchmark directory, pass a `File` parameter to `createFromSolverConfigXmlResource()`.

The generated benchmark report already contains interesting information,
but it doesn't compare solver configurations to find the best algorithm.
To do that, set up an explicit benchmark configuration:

[[buildAndRunAPlannerBenchmark]]
=== Configure and run an advanced benchmark

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

[source,java,options="nowrap"]
----
PlannerBenchmarkFactory benchmarkFactory = PlannerBenchmarkFactory.createFromXmlResource(
        "org/optaplanner/examples/cloudbalancing/benchmark/cloudBalancingBenchmarkConfig.xml");
PlannerBenchmark benchmark = benchmarkFactory.buildPlannerBenchmark();
benchmark.benchmarkAndShowReportInBrowser();
----

Alternatively, create a `PlannerBenchmarkFactory` programmatically from a `PlannerBenchmarkConfig`.

A benchmark configuration XML file looks like this:

[source,xml,options="nowrap"]
----
<?xml version="1.0" encoding="UTF-8"?>
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  <benchmarkDirectory>local/data/nqueens</benchmarkDirectory>

  <inheritedSolverBenchmark>
    <problemBenchmarks>
      ...
      <inputSolutionFile>data/cloudbalancing/unsolved/100computers-300processes.xml</inputSolutionFile>
      <inputSolutionFile>data/cloudbalancing/unsolved/200computers-600processes.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` tries three configurations (Tabu Search, Simulated Annealing and Late Acceptance)
on two data sets (``100computers-300processes`` and ``200computers-600processes``), so it runs six solvers.

Every `<solverBenchmark>` element contains a solver configuration and one or more `<inputSolutionFile>` elements.
It runs 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,SolutionFileIO>>, relative to the working directory.

[NOTE]
====
Use a forward slash (``/``) as the file separator (for example in the element ``<inputSolutionFile>``). That will work on any platform (including Windows).

Do not use backslash (``\``) as the file separator: that breaks portability because it does not work on Linux and Mac.
====

The benchmark report is written in the directory specified by the `<benchmarkDirectory>` element (relative to the working directory).

[NOTE]
====
It's recommended that the `benchmarkDirectory` is a directory that is ignored for source control and not cleaned by your build system.
This way the generated files are not bloating your source control and they aren't lost when doing a clean build.
For example in git, it should be added to ``.gitignore``. Usually that directory is called ``local``.
====

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


[[inheritedSolverBenchmark]]
==== Inherited solver benchmark

To lower verbosity, the common parts of multiple `<solverBenchmark>` elements are extracted to the `<inheritedSolverBenchmark>` element.
Every property can still be overwritten per `<solverBenchmark>` element.
Note that inherited solver phases such as `<constructionHeuristic>` or `<localSearch>` are not overwritten
but instead are added to the tail of the solver phases list.


[[solutionFileIO]]
=== `SolutionFileIO`: input and output of solution files


[[solutionFileIOInterface]]
==== `SolutionFileIO` interface

The benchmarker needs to be able to read the input files to load a problem.
Also, it optionally writes the best solution of each benchmark to an output file.
It does that through the `SolutionFileIO` interface which has a read and write method:

[source,java,options="nowrap"]
----
public interface SolutionFileIO<Solution_> {
    ...

    Solution_ read(File inputSolutionFile);
    void write(Solution_ solution, File outputSolutionFile);

}
----

The `SolutionFileIO` interface is in the `optaplanner-persistence-common` jar (which is a dependency of the `optaplanner-benchmark` jar).
There are several ways to serialize a solution:


[[xStreamSolutionFileIO]]
==== `XStreamSolutionFileIO`: serialize to and from an XML format

To read and write solutions in the XML format via XStream, extend the `XStreamSolutionFileIO`:

[source,java,options="nowrap"]
----
public class NQueensXmlSolutionFileIO extends XStreamSolutionFileIO<NQueens> {
    public NQueensXmlSolutionFileIO() {
        // NQueens is the @PlanningSolution class.
        super(NQueens.class);
    }
}
----

and use it in the benchmark configuration:

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      <solutionFileIOClass>org.optaplanner.examples.nqueens.persistence.NQueensXmlSolutionFileIO</solutionFileIOClass>
      <inputSolutionFile>data/nqueens/unsolved/32queens.xml</inputSolutionFile>
      ...
    </problemBenchmarks>
----

Those input files need to have been written with the same `SolutionFileIO` class that uses or extends the
`XStreamSolutionFileIO`, not just any `XStream` instance, because the `XStreamSolutionFileIO` uses a customized `XStream`
instance.

[IMPORTANT]
====
The `inputSolutionFile` needs to come from a trusted source:
if it contains malicious data, it can be exploited.
The `XStreamSolutionFileIO` disables the `XStream` security framework, so it just works out of the box.

If you expose benchmarking in production, use `XStreamSolutionFileIO.getXStream()`
to enable the security framework and explicitly allow all marshalled classes.
====

Add XStream annotations (such as ``@XStreamAlias``) on your domain classes to use a less verbose XML format.
Regardless, XML is still a very verbose format.
Reading or writing large datasets in this format can cause an `OutOfMemoryError`, `StackOverflowError`
or large performance degradation.

[[JacksonSolutionFileIO]]
==== `JacksonSolutionFileIO`: serialize to and from an JSON format

To read and write solutions in JSON format via Jackson, extend the `JacksonSolutionFileIO`:

[source,java,options="nowrap"]
----
public class NQueensJsonSolutionFileIO extends JacksonSolutionFileIO<NQueens> {
    public NQueensJsonSolutionFileIO() {
        // NQueens is the @PlanningSolution class.
        super(NQueens.class);
    }
}
----

If the JSON file requires specific Jackson modules and features to be enabled/disabled.
You could create your desired object mapper as a dependency to the JacksonSolutionFileIO as follows:

[source,java,options="nowrap"]
----
public class NQueensJsonSolutionFileIO extends JacksonSolutionFileIO<NQueens> {
    public NQueensJsonSolutionFileIO() {
        // NQueens is the @PlanningSolution class.
        super(NQueens.class,
                new ObjectMapper()
                        .registerModule(new JavaTimeModule())
                        .disable(SerializationFeature.WRITE_DATES_AS_TIMESTAMPS)
        );
    }

}
----

Then use it in the benchmark configuration like so:

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      <solutionFileIOClass>org.optaplanner.examples.nqueens.persistence.NQueensJsonSolutionFileIO</solutionFileIOClass>
      <inputSolutionFile>data/nqueens/unsolved/32queens.json</inputSolutionFile>
      ...
    </problemBenchmarks>
----

[[customSolutionFileIO]]
==== Custom `SolutionFileIO`: serialize to and from a custom format

Implement your own `SolutionFileIO` implementation and configure it with the `solutionFileIOClass` element to write to a custom format (such as a txt or a binary format):

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      <solutionFileIOClass>org.optaplanner.examples.machinereassignment.persistence.MachineReassignmentFileIO</solutionFileIOClass>
      <inputSolutionFile>data/machinereassignment/import/model_a1_1.txt</inputSolutionFile>
      ...
    </problemBenchmarks>
----

It's recommended that output files can be read as input files,
which implies that `getInputFileExtension()` and `getOutputFileExtension()` return the same value.

[WARNING]
====
A `SolutionFileIO` implementation must be thread-safe.
====


[[readingAnInputSolutionFromADatabase]]
==== Reading an input solution from a database or other storage

There are two options if your dataset is in a relational database or another type of repository:

* Extract the datasets from the database and serialize them to a local file (for example as XML with `XStreamSolutionFileIO` if XML isn't too verbose).
Then use those files in `<inputSolutionFile>` elements.
** The benchmarks are now more reliable because they run offline.
** Each dataset is only loaded just in time.
* Load all the datasets in advance and pass them to the `buildPlannerBenchmark()` method:
+
[source,java,options="nowrap"]
----
        PlannerBenchmark plannerBenchmark = benchmarkFactory.buildPlannerBenchmark(dataset1, dataset2, dataset3);
----


[[warmingUpTheHotSpotCompiler]]
=== Warming up the HotSpot compiler

Without a warm up, the results of the first (or first few) benchmarks are not reliable because they lose CPU time on HotSpot JIT compilation.

To avoid that distortion, the benchmarker runs some of the benchmarks for 30 seconds, before running the real benchmarks. That default warm up of 30 seconds usually suffices. Change it, for example to give it 60 seconds:

[source,xml,options="nowrap"]
----
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  ...
  <warmUpSecondsSpentLimit>60</warmUpSecondsSpentLimit>
  ...
</plannerBenchmark>
----

Turn off the warm up phase altogether by setting it to zero:

[source,xml,options="nowrap"]
----
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  ...
  <warmUpSecondsSpentLimit>0</warmUpSecondsSpentLimit>
  ...
</plannerBenchmark>
----

[NOTE]
====
The warm up time budget does not include the time it takes to load the datasets.
With large datasets, this can cause the warm up to run considerably longer than specified in the configuration.
====


[[benchmarkBlueprint]]
=== Benchmark blueprint: a predefined configuration

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

[source,xml,options="nowrap"]
----
<?xml version="1.0" encoding="UTF-8"?>
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  <benchmarkDirectory>local/data/nqueens</benchmarkDirectory>

  <inheritedSolverBenchmark>
    <problemBenchmarks>
      <solutionFileIOClass>org.optaplanner.examples.nqueens.persistence.NQueensXmlSolutionFileIO</solutionFileIOClass>
      <inputSolutionFile>data/nqueens/unsolved/32queens.xml</inputSolutionFile>
      <inputSolutionFile>data/nqueens/unsolved/64queens.xml</inputSolutionFile>
    </problemBenchmarks>
    <solver>
      <solutionClass>org.optaplanner.examples.nqueens.domain.NQueens</solutionClass>
      <entityClass>org.optaplanner.examples.nqueens.domain.Queen</entityClass>
      <scoreDirectorFactory>
        <constraintProviderClass>org.optaplanner.examples.nqueens.score.NQueensConstraintProvider</constraintProviderClass>
        <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 ``SolverBenchmarkBluePrintType``s are supported:

* ``CONSTRUCTION_HEURISTIC_WITH_AND_WITHOUT_LOCAL_SEARCH``: Run the default Construction Heuristic type with and without the default Local Search type.

* ``EVERY_CONSTRUCTION_HEURISTIC_TYPE``: Run every Construction Heuristic type (First Fit, First Fit Decreasing, Cheapest Insertion, ...).

* ``EVERY_LOCAL_SEARCH_TYPE``: Run every Local Search type (Tabu Search, Late Acceptance, ...) with the default Construction Heuristic.

* ``EVERY_CONSTRUCTION_HEURISTIC_TYPE_WITH_EVERY_LOCAL_SEARCH_TYPE``: Run every Construction Heuristic type with every Local Search type.


[[writeTheOutputSolutionOfBenchmarkRuns]]
=== Write the output solution of benchmark runs

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

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <writeOutputSolutionEnabled>true</writeOutputSolutionEnabled>
      ...
    </problemBenchmarks>
----


[[benchmarkLogging]]
=== Benchmark logging

Benchmark logging is configured like <<logging,solver logging>>.

To separate the log messages of each single benchmark run into a separate file, use the http://logback.qos.ch/manual/mdc.html[MDC] with key `singleBenchmark.name` in a sifting appender.
For example with Logback in ``logback.xml``:

[source,xml,options="nowrap"]
----
  <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>
----


[[benchmarkReport]]
== Benchmark report


[[benchmarkHtmlReport]]
=== HTML report

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:

* Summary statistics: graphs and tables
* Problem statistics per ``inputSolutionFile``: graphs and CSV
* Each solver configuration (ranked): Handy to copy and paste
* Benchmark information: settings, hardware, ...


[NOTE]
====
Graphs are generated by the excellent http://www.jfree.org/jfreechart/[JFreeChart] library.
====

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:

[source,xml,options="nowrap"]
----
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  ...
  <benchmarkReport>
    <locale>en_US</locale>
  </benchmarkReport>
  ...
</plannerBenchmark>
----


[[rankingTheSolvers]]
=== Ranking the solvers

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:

[source,xml,options="nowrap"]
----
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  ...
  <benchmarkReport>
    <solverRankingType>TOTAL_SCORE</solverRankingType>
  </benchmarkReport>
  ...
</plannerBenchmark>
----

The following ``solverRankingType``s are supported:

* `TOTAL_SCORE` (default): Maximize the overall score, so minimize the overall cost if all solutions would be executed.
* ``WORST_SCORE``: Minimize the worst case scenario.
* ``TOTAL_RANKING``: Maximize the overall ranking. Use this if your datasets differ greatly in size or difficulty, producing a difference in `Score` magnitude.

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

To use a custom ranking, implement a ``Comparator``:

[source,xml,options="nowrap"]
----
  <benchmarkReport>
    <solverRankingComparatorClass>...TotalScoreSolverRankingComparator</solverRankingComparatorClass>
  </benchmarkReport>
----

Or by implementing a weight factory:

[source,xml,options="nowrap"]
----
  <benchmarkReport>
    <solverRankingWeightFactoryClass>...TotalRankSolverRankingWeightFactory</solverRankingWeightFactoryClass>
  </benchmarkReport>
----


[[benchmarkReportSummaryStatistics]]
== Summary statistics


[[benchmarkReportBestScoreSummary]]
=== Best score summary (graph and table)

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

Useful for visualizing the best solver configuration.

.Best score summary statistic
image::BenchmarkingAndTweaking/bestScoreSummary.png[align="center"]


[[benchmarkReportBestScoreScalabilitySummary]]
=== Best score scalability summary (graph)

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

Useful for visualizing the scalability of each solver configuration.

[NOTE]
====
The problem scale will report `0` if any `@ValueRangeProvider` method signature returns ValueRange (instead of `CountableValueRange` or ``Collection``).
====


[[benchmarkReportBestScoreDistributionSummary]]
=== Best score distribution summary (graph)

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

Useful for visualizing the reliability of each solver configuration.

.Best Score Distribution Summary Statistic
image::BenchmarkingAndTweaking/bestScoreDistributionSummary.png[align="center"]

Enable <<statisticalBenchmarking,statistical benchmarking>> to use this summary.


[[benchmarkReportWinningScoreDifferenceSummary]]
=== Winning score difference summary (graph And table)

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.


[[benchmarkReportWorstScoreDifferencePercentageSummary]]
=== Worst score difference percentage (ROI) summary (graph And table)

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.


[[benchmarkReportScoreCalculationSpeedSummary]]
=== Score calculation speed summary (graph And table)

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

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


[[benchmarkReportTimeSpentSummary]]
=== Time spent summary (graph And table)

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


[[benchmarkReportTimeSpentScalabilitySummary]]
=== Time spent scalability summary (graph)

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


[[benchmarkReportBestScorePerTimeSpentSummary]]
=== Best score per time spent summary (graph)

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


[[benchmarkReportStatisticPerDataset]]
== Statistic per dataset (graph and CSV)


[[enableAProblemStatistic]]
=== Enable a problem statistic

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

[source,xml,options="nowrap"]
----
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  <benchmarkDirectory>local/data/nqueens/solved</benchmarkDirectory>
  <inheritedSolverBenchmark>
    <problemBenchmarks>
      ...
      <problemStatisticType>BEST_SCORE</problemStatisticType>
      <problemStatisticType>SCORE_CALCULATION_SPEED</problemStatisticType>
    </problemBenchmarks>
    ...
  </inheritedSolverBenchmark>
  ...
</plannerBenchmark>
----

[NOTE]
====
These problem statistics can slow down the solvers noticeably, which affects the benchmark results.
That's why they are optional and only `BEST_SCORE` is enabled by default.
To disable that one too, use `problemStatisticEnabled`:

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <problemStatisticEnabled>false</problemStatisticEnabled>
    </problemBenchmarks>
----

The summary statistics do not slow down the solver and are always generated.
====

The following types are supported:


[[benchmarkReportBestScoreOverTimeStatistic]]
=== Best score over time statistic (graph and CSV)

Shows how the best score evolves over time. It is run by default.
To run it when other statistics are configured, also add:

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <problemStatisticType>BEST_SCORE</problemStatisticType>
    </problemBenchmarks>
----

.Best Score Over Time Statistic
image::BenchmarkingAndTweaking/bestScoreStatistic.png[align="center"]

[NOTE]
====
A time gradient based algorithm (such as Simulated Annealing) will have a different statistic if it's run with a different time limit configuration.
That's because this Simulated Annealing implementation automatically determines its velocity based on the amount of time that can be spent.
On the other hand, for the Tabu Search and Late Acceptance, what you see is what you'd get.
====

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

image::BenchmarkingAndTweaking/letTheBestScoreStatisticGuideYou.png[align="center"]


[[benchmarkReportStepScoreOverTimeStatistic]]
=== Step score over time statistic (graph and CSV)

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

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <problemStatisticType>STEP_SCORE</problemStatisticType>
    </problemBenchmarks>
----

.Step Score Over Time Statistic
image::BenchmarkingAndTweaking/stepScoreStatistic.png[align="center"]

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

[WARNING]
====
The step score statistic has been seen to slow down the solver noticeably due to GC stress,
especially for fast stepping algorithms
(such as <<simulatedAnnealing,Simulated Annealing>> and <<lateAcceptance,Late Acceptance>>).
====


[[benchmarkReportScoreCalculationSpeedOverTimeStatistic]]
=== Score calculation speed over time statistic (graph and CSV)

To see how fast the scores are calculated, add:

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <problemStatisticType>SCORE_CALCULATION_SPEED</problemStatisticType>
    </problemBenchmarks>
----

.Score Calculation Speed Statistic
image::BenchmarkingAndTweaking/scoreCalculationSpeedStatistic.png[align="center"]


[NOTE]
====
The initial high calculation speed is typical during solution initialization: it's far easier to calculate the score of a solution if only a handful planning entities have been initialized, than when all the planning entities are initialized.

After those few seconds of initialization, the calculation speed is relatively stable, apart from an occasional stop-the-world garbage collector disruption.
====


[[benchmarkReportBestSolutionMutationOverTimeStatistic]]
=== Best solution mutation over time statistic (graph and CSV)

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:

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <problemStatisticType>BEST_SOLUTION_MUTATION</problemStatisticType>
    </problemBenchmarks>
----

.Best Solution Mutation Over Time Statistic
image::BenchmarkingAndTweaking/bestSolutionMutationStatistic.png[align="center"]

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.


[[benchmarkReportMoveCountPerStepStatistic]]
=== Move count per step statistic (graph and CSV)

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

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <problemStatisticType>MOVE_COUNT_PER_STEP</problemStatisticType>
    </problemBenchmarks>
----

.Move Count Per Step Statistic
image::BenchmarkingAndTweaking/moveCountPerStepStatistic.png[align="center"]


[WARNING]
====
This statistic has been seen to slow down the solver noticeably due to GC stress, especially for fast stepping algorithms (such as Simulated Annealing and Late Acceptance).
====


[[benchmarkReportMemoryUseStatistic]]
=== Memory use statistic (graph and CSV)

To see how much memory is used, add:

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <problemStatisticType>MEMORY_USE</problemStatisticType>
    </problemBenchmarks>
----

.Memory Use Statistic
image::BenchmarkingAndTweaking/memoryUseStatistic.png[align="center"]


[WARNING]
==
The memory use statistic has been seen to affect the solver noticeably.
==


[[benchmarkReportStatisticPerSingleBenchmark]]
== Statistic per single benchmark (graph and CSV)


[[enableASingleStatistic]]
=== Enable a single statistic

A single statistic is static for one dataset for one 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:

[source,xml,options="nowrap"]
----
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  <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.

[NOTE]
====
These statistic per single benchmark can slow down the solver noticeably, which affects the benchmark results.
That's why they are optional and not enabled by default.
====

The following types are supported:


[[benchmarkReportConstraintMatchTotalBestScoreOverTimeStatistic]]
=== Constraint match total best score over time statistic (graph and CSV)

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

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <singleStatisticType>CONSTRAINT_MATCH_TOTAL_BEST_SCORE</singleStatisticType>
    </problemBenchmarks>
----

.Constraint Match Total Best Score Diff Over Time Statistic
image::BenchmarkingAndTweaking/constraintMatchTotalBestScoreStatistic.png[align="center"]

Requires the score calculation to support <<explainingTheScore,constraint matches>>.
<<constraintStreams,Constraint Streams>> and <<droolsScoreCalculation,Drools score calculation>> support constraint matches automatically,
but <<incrementalJavaScoreCalculation,incremental Java score calculation>> requires more work.

[WARNING]
====
The constraint match total statistics affect the solver noticeably.
====


[[benchmarkReportConstraintMatchTotalStepScoreOverTimeStatistic]]
=== Constraint match total step score over time statistic (graph and CSV)

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

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <singleStatisticType>CONSTRAINT_MATCH_TOTAL_STEP_SCORE</singleStatisticType>
    </problemBenchmarks>
----

.Constraint Match Total Step Score Diff Over Time Statistic
image::BenchmarkingAndTweaking/constraintMatchTotalStepScoreStatistic.png[align="center"]

Also requires the score calculation to support <<explainingTheScore,constraint matches>>.

[WARNING]
====
The constraint match total statistics affect the solver noticeably.
====


[[benchmarkReportPickedMoveTypeBestScoreDiffOverTimeStatistic]]
=== Picked move type best score diff over time statistic (graph and CSV)

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

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <singleStatisticType>PICKED_MOVE_TYPE_BEST_SCORE_DIFF</singleStatisticType>
    </problemBenchmarks>
----

.Picked Move Type Best Score Diff Over Time Statistic
image::BenchmarkingAndTweaking/pickedMoveTypeBestScoreDiffStatistic.png[align="center"]


[[benchmarkReportPickedMoveTypeStepScoreDiffOverTimeStatistic]]
=== Picked move type step score diff over time statistic (graph and CSV)

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

[source,xml,options="nowrap"]
----
    <problemBenchmarks>
      ...
      <singleStatisticType>PICKED_MOVE_TYPE_STEP_SCORE_DIFF</singleStatisticType>
    </problemBenchmarks>
----

.Picked Move Type Step Score Diff Over Time Statistic
image::BenchmarkingAndTweaking/pickedMoveTypeStepScoreDiffStatistic.png[align="center"]


[[advancedBenchmarking]]
== Advanced benchmarking


[[benchmarkingPerformanceTricks]]
=== Benchmarking performance tricks


[[parallelBenchmarkingOnMultipleThreads]]
==== Parallel benchmarking on multiple threads

If you have multiple processors available on your computer, you can run multiple benchmarks in parallel on multiple threads to get your benchmarks results faster:

[source,xml,options="nowrap"]
----
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  ...
  <parallelBenchmarkCount>AUTO</parallelBenchmarkCount>
  ...
</plannerBenchmark>
----

[WARNING]
====
Running too many benchmarks in parallel will affect the results of benchmarks negatively.
Leave some processors unused for garbage collection and other processes.
====

The following ``parallelBenchmarkCount``s are supported:

* `1` (default): Run all benchmarks sequentially.
* ``AUTO``: Let OptaPlanner decide how many benchmarks to run in parallel. This formula is based on experience. It's recommended to prefer this over the other parallel enabling options.
* Static number: The number of benchmarks to run in parallel.
+
[source,xml,options="nowrap"]
----
<parallelBenchmarkCount>2</parallelBenchmarkCount>
----

[NOTE]
====
The `parallelBenchmarkCount` is always limited to the number of available processors.
If it's higher, it will be automatically decreased.
====

[NOTE]
====
If you have a computer with slow or unreliable cooling, increasing the `parallelBenchmarkCount` above one (even on ``AUTO``) may overheat your CPU.

The `sensors` command can help you detect if this is the case.
It is available in the package `lm_sensors` or `lm-sensors` in most Linux distributions.
There are several freeware tools available for Windows too.
====

The benchmarker uses a thread pool internally, but you can optionally plug in a custom `ThreadFactory`,
for example when running benchmarks on an application server or a cloud platform:

[source,xml,options="nowrap"]
----
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  ...
  <threadFactoryClass>...MyCustomThreadFactory</threadFactoryClass>
  ...
</plannerBenchmark>
----

[NOTE]
====
In the future, we will also support multi-JVM benchmarking.
This feature is independent of <<multithreadedSolving,multithreaded solving>> or multi-JVM solving.
====


[[statisticalBenchmarking]]
=== Statistical benchmarking

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 <<benchmarkReportBestScoreDistributionSummary,the best score distribution summary>>.

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

[source,xml,options="nowrap"]
----
<?xml version="1.0" encoding="UTF-8"?>
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  ...
  <inheritedSolverBenchmark>
    ...
    <solver>
      ...
    </solver>
    <subSingleCount>10</subSingleCount>
  </inheritedSolverBenchmark>
  ...
</plannerBenchmark>
----

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

[NOTE]
====
If `subSingleCount` is higher than ``1``, the benchmarker will automatically use a _different_<<randomNumberGenerator,`Random` seed>> for every sub single run, without losing reproducibility (for each sub single index) in <<environmentMode,EnvironmentMode>>``REPRODUCIBLE`` and lower.
====


[[templateBasedBenchmarking]]
=== Template-based benchmarking and matrix benchmarking

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

To reduce the verbosity of such a benchmark configuration, you can use a http://freemarker.org/[Freemarker] template for the benchmark configuration instead:

[source,xml,options="nowrap"]
----
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  ...
  <inheritedSolverBenchmark>
    ...
  </inheritedSolverBenchmark>

<#list [5, 7, 11, 13] as entityTabuSize>
<#list [500, 1000, 2000] as acceptedCountLimit>
  <solverBenchmark>
    <name>Tabu Search 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>
----

To configure Matrix Benchmarking for Simulated Annealing (or any other configuration that involves a `Score` template variable), use the `replace()` method in the solver benchmark name element:

[source,xml,options="nowrap"]
----
<plannerBenchmark xmlns="https://www.optaplanner.org/xsd/benchmark" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/benchmark https://www.optaplanner.org/xsd/benchmark/benchmark.xsd">
  ...
  <inheritedSolverBenchmark>
    ...
  </inheritedSolverBenchmark>

<#list ["1hard/10soft", "1hard/20soft", "1hard/50soft", "1hard/70soft"] as startingTemperature>
  <solverBenchmark>
    <name>Simulated Annealing startingTemperature ${startingTemperature?replace("/", "_")}</name>
    <solver>
      <localSearch>
        <acceptor>
          <simulatedAnnealingStartingTemperature>${startingTemperature}</simulatedAnnealingStartingTemperature>
        </acceptor>
      </localSearch>
    </solver>
  </solverBenchmark>
</#list>
</plannerBenchmark>
----

[NOTE]
====
A solver benchmark name doesn't allow some characters (such a ``/``) because the name is also used a file name.
====

And build it with the class ``PlannerBenchmarkFactory``:

[source,java,options="nowrap"]
----
        PlannerBenchmarkFactory benchmarkFactory = PlannerBenchmarkFactory.createFromFreemarkerXmlResource(
                "org/optaplanner/examples/cloudbalancing/optional/benchmark/cloudBalancingBenchmarkConfigTemplate.xml.ftl");
        PlannerBenchmark benchmark = benchmarkFactory.buildPlannerBenchmark();
----


[[benchmarkReportAggregation]]
=== Benchmark report aggregation

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

image::BenchmarkingAndTweaking/benchmarkAggregator.png[align="center"]

This is useful to:

* **Report on the impact of code changes**: Run the same benchmark configuration before and after the code changes, then aggregate a report.
* **Report on the impact of dependency upgrades**: Run the same benchmark configuration before and after upgrading the dependency, then aggregate a report.
* **Summarize a too verbose report**: Select only the interesting solver benchmarks from the existing report. This especially useful on template reports to make the graphs readable.
* **Partially rerun a benchmark**: Rerun part of an existing report (for example only the failed or invalid solvers), then recreate the original intended report with the new values.

Compose the aggregated report in the Benchmark aggregator UI:

image::BenchmarkingAndTweaking/benchmarkAggregatorScreenshot.png[align="center"]

To display that UI, provide a benchmark config to the `BenchmarkAggregatorFrame`:

[source,java,options="nowrap"]
----
    public static void main(String[] args) {
        BenchmarkAggregatorFrame.createAndDisplayFromXmlResource(
                "org/optaplanner/examples/cloudbalancing/benchmark/cloudBalancingBenchmarkConfig.xml");
    }
----

[NOTE]
====
Despite that it uses a benchmark configuration as input, it ignores all elements of that configuration,
except for the elements `<benchmarkDirectory>` and ``<benchmarkReport>``.
====

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

[NOTE]
====
All the input reports which are being merged should have been generated with the same OptaPlanner version (excluding hotfix differences) as the ``BenchmarkAggregator``.
Using reports from different OptaPlanner major or minor versions are not guaranteed to succeed and deliver correct information,
because the benchmark report data structure often changes.
====
