JBoss.orgCommunity Documentation

Chapter 12. Benchmarking and tweaking

12.1. Finding the best Solver configuration
12.2. Doing a benchmark
12.2.1. Adding the extra dependency
12.2.2. Building and running a PlannerBenchmark
12.2.3. ProblemIO: input and output of Solution files
12.2.4. Writing the output solution of the benchmark runs
12.2.5. Warming up the HotSpot compiler
12.3. Benchmark report
12.3.1. HTML report
12.3.2. Summary statistics
12.3.3. Statistic per data set (graph and CSV)
12.3.4. Ranking the Solvers
12.4. Advanced benchmarking
12.4.1. Benchmarking performance tricks
12.4.2. Template based benchmarking and matrix benchmarking

Drools Planner 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, Drools Planner 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.

You can build a PlannerBenchmark instance with the XmlPlannerBenchmarkFactory. Configure it with a benchmark configuration xml file:

    XmlPlannerBenchmarkFactory plannerBenchmarkFactory = new XmlPlannerBenchmarkFactory();

    plannerBenchmarkFactory.configure("/org/drools/planner/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>-->
  <warmUpSecondsSpend>30</warmUpSecondsSpend>

  <inheritedSolverBenchmark>
    <problemBenchmarks>
      <xstreamAnnotatedClass>org.drools.planner.examples.nqueens.domain.NQueens</xstreamAnnotatedClass>
      <inputSolutionFile>data/nqueens/unsolved/unsolvedNQueens32.xml</inputSolutionFile>
      <inputSolutionFile>data/nqueens/unsolved/unsolvedNQueens64.xml</inputSolutionFile>
      <problemStatisticType>BEST_SOLUTION_CHANGED</problemStatisticType>
    </problemBenchmarks>
    <solver>
      <solutionClass>org.drools.planner.examples.nqueens.domain.NQueens</solutionClass>
      <planningEntityClass>org.drools.planner.examples.nqueens.domain.Queen</planningEntityClass>
      <scoreDirectorFactory>
        <scoreDefinitionType>SIMPLE</scoreDefinitionType>
        <scoreDrl>/org/drools/planner/examples/nqueens/solver/nQueensScoreRules.drl</scoreDrl>
      </scoreDirectorFactory>
      <termination>
        <maximumSecondsSpend>20</maximumSecondsSpend>
      </termination>
      <constructionHeuristic>
        <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
        <constructionHeuristicPickEarlyType>FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING</constructionHeuristicPickEarlyType>
      </constructionHeuristic>
    </solver>
  </inheritedSolverBenchmark>

  <solverBenchmark>
    <name>Entity tabu</name>
    <solver>
      <localSearch>
        <changeMoveSelector>
          <selectionOrder>ORIGINAL</selectionOrder>
        </changeMoveSelector>
        <acceptor>
          <planningEntityTabuSize>5</planningEntityTabuSize>
        </acceptor>
        <forager>
          <pickEarlyType>NEVER</pickEarlyType>
        </forager>
      </localSearch>
    </solver>
  </solverBenchmark>
  <solverBenchmark>
    <name>Value tabu</name>
    <solver>
      <localSearch>
        <changeMoveSelector>
          <selectionOrder>ORIGINAL</selectionOrder>
        </changeMoveSelector>
        <acceptor>
          <planningValueTabuSize>5</planningValueTabuSize>
        </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 ProblemIO.

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

Matrix benchmarking is benchmarking a combination of value sets. For example: benchmark 4 planningEntityTabuSize values (5, 7, 11 and 13) combined with 3 minimalAcceptedSelection 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 planningEntityTabuSize>
<#list [500, 1000, 2000] as minimalAcceptedSelection>
  <solverBenchmark>
    <name>entityTabu ${planningEntityTabuSize} acceptedSelection ${minimalAcceptedSelection}</name>
    <solver>
      <localSearch>
        <unionMoveSelector>
          <changeMoveSelector/>
          <swapMoveSelector/>
        </unionMoveSelector>
        <acceptor>
          <planningEntityTabuSize>${planningEntityTabuSize}</planningEntityTabuSize>
        </acceptor>
        <forager>
          <minimalAcceptedSelection>${minimalAcceptedSelection}</minimalAcceptedSelection>
        </forager>
      </localSearch>
    </solver>
  </solverBenchmark>
</#list>
</#list>
</plannerBenchmark>

And configure it with the method configureFromTemplate:

    XmlPlannerBenchmarkFactory plannerBenchmarkFactory = new XmlPlannerBenchmarkFactory();

    plannerBenchmarkFactory.configureFromTemplate("/org/drools/planner/examples/cloudbalancing/benchmark/cloudBalancingBenchmarkConfigTemplate.xml.ftl");
    PlannerBenchmark plannerBenchmark = benchmarkFactory.buildPlannerBenchmark();