JBoss.orgCommunity Documentation

Chapter 13. Benchmarking and tweaking

13.1. Finding the best Solver configuration
13.2. Doing a benchmark
13.2.1. Adding a dependency on optaplanner-benchmark
13.2.2. Building and running a PlannerBenchmark
13.2.3. Benchmark blueprint: a predefined configuration
13.2.4. SolutionFileIO: input and output of Solution files
13.2.5. Warming up the HotSpot compiler
13.2.6. Writing the output solution of the benchmark runs
13.3. Benchmark report
13.3.1. HTML report
13.3.2. Ranking the Solvers
13.4. Summary statistics
13.4.1. Best score summary (graph and table)
13.4.2. Best score scalability summary (graph)
13.4.3. Winning score difference summary (graph and table)
13.4.4. Worst score difference percentage (ROI) summary (graph and table)
13.4.5. Average calculation count summary (graph and table)
13.4.6. Time spent summary (graph and table)
13.4.7. Time spent scalability summary (graph)
13.4.8. Best score per time spent summary (graph)
13.5. Statistic per dataset (graph and CSV)
13.5.1. Enabling a problem statistic
13.5.2. Best score over time statistic (graph and CSV)
13.5.3. Step score over time statistic (graph and CSV)
13.5.4. Calculate count per second statistic (graph and CSV)
13.5.5. Best solution mutation over time statistic (graph and CSV)
13.5.6. Move count per step statistic (graph and CSV)
13.5.7. Memory use statistic (graph and CSV)
13.6. Statistic per single benchmark (graph and CSV)
13.6.1. Enabling a single statistic
13.6.2. Picked move type best score diff over time statistic (graph and CSV)
13.6.3. Picked move type step score diff over time statistic (graph and CSV)
13.7. Advanced benchmarking
13.7.1. Benchmarking performance tricks
13.7.2. Template based benchmarking and matrix benchmarking
13.7.3. Benchmark report aggregation

OptaPlanner supports several optimization algorithms, but 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, so you can pick the best configuration for your planning problem.

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 = benchmarkFactory.buildPlannerBenchmark();
        plannerBenchmark.benchmark();

A basic benchmark configuration file looks something like this:


<?xml version="1.0" encoding="UTF-8"?>
<plannerBenchmark>
  <benchmarkDirectory>local/data/nqueens</benchmarkDirectory>
  <!--<parallelBenchmarkCount>AUTO</parallelBenchmarkCount>-->
  <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>
      <solutionClass>org.optaplanner.examples.nqueens.domain.NQueens</solutionClass>
      <entityClass>org.optaplanner.examples.nqueens.domain.Queen</entityClass>
      <scoreDirectorFactory>
        <scoreDefinitionType>SIMPLE</scoreDefinitionType>
        <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
        <initializingScoreTrend>ONLY_DOWN</initializingScoreTrend>
      </scoreDirectorFactory>
      <termination>
        <secondsSpentLimit>20</secondsSpentLimit>
      </termination>
      <constructionHeuristic>
        <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
      </constructionHeuristic>
    </solver>
  </inheritedSolverBenchmark>

  <solverBenchmark>
    <name>Entity tabu</name>
    <solver>
      <localSearch>
        <changeMoveSelector>
          <selectionOrder>ORIGINAL</selectionOrder>
        </changeMoveSelector>
        <acceptor>
          <entityTabuSize>5</entityTabuSize>
        </acceptor>
        <forager>
          <pickEarlyType>NEVER</pickEarlyType>
        </forager>
      </localSearch>
    </solver>
  </solverBenchmark>
  <solverBenchmark>
    <name>Value tabu</name>
    <solver>
      <localSearch>
        <changeMoveSelector>
          <selectionOrder>ORIGINAL</selectionOrder>
        </changeMoveSelector>
        <acceptor>
          <valueTabuSize>5</valueTabuSize>
        </acceptor>
        <forager>
          <pickEarlyType>NEVER</pickEarlyType>
        </forager>
      </localSearch>
    </solver>
  </solverBenchmark>
  <solverBenchmark>
    <name>Move tabu</name>
    <solver>
      <localSearch>
        <changeMoveSelector>
          <selectionOrder>ORIGINAL</selectionOrder>
        </changeMoveSelector>
        <acceptor>
          <moveTabuSize>5</moveTabuSize>
        </acceptor>
        <forager>
          <pickEarlyType>NEVER</pickEarlyType>
        </forager>
      </localSearch>
    </solver>
  </solverBenchmark>
</plannerBenchmark>

This PlannerBenchmark will try 3 configurations (1 move tabu, 1 entity tabu and 1 value tabu) on 2 data sets (32 and 64 queens), so it will run 6 solvers.

Every <solverBenchmark> element contains a solver configuration (for example with a local search solver phase) 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.

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.

To lower verbosity, the common part of multiple <solverBenchmark> elements can be extracted to the <inheritedSolverBenchmark> element. Yet, 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.

You need to specify a <benchmarkDirectory> element (relative to the working directory). A benchmark report will be written in that directory.

Note

It's recommended that the benchmarkDirectory is a directory 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 build. Usually that directory is called local.

If an Exception or Error occurs in a single benchmark, the entire Benchmarker will not fail-fast (unlike everything else in OptaPlanner). 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 in the benchmark report.

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>
      <solutionClass>org.optaplanner.examples.nqueens.domain.NQueens</solutionClass>
      <entityClass>org.optaplanner.examples.nqueens.domain.Queen</entityClass>
      <scoreDirectorFactory>
        <scoreDefinitionType>SIMPLE</scoreDefinitionType>
        <scoreDrl>org/optaplanner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
        <initializingScoreTrend>ONLY_DOWN</initializingScoreTrend>
      </scoreDirectorFactory>
    </solver>
  </inheritedSolverBenchmark>

  <solverBenchmarkBluePrint>
    <solverBenchmarkBluePrintType>ALL_CONSTRUCTION_HEURISTIC_TYPES</solverBenchmarkBluePrintType>
  </solverBenchmarkBluePrint>
</plannerBenchmark>

The following SolverBenchmarkBluePrintTypes are supported:

After the running a benchmark, a HTML report will be written in the benchmarkDirectory with the filename index.html. 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>

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


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

The best score over time statistic is very useful to detect abnormalities, such as a potential score trap.

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 Annealing, what you see is what you'd get.

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 = benchmarkFactory.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 generate a:

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.