JBoss.orgCommunity Documentation

Chapter 8. Exhaustive search

8.1. Overview
8.2. Brute Force
8.2.1. Algorithm description
8.2.2. Configuration
8.3. Branch And Bound
8.3.1. Algorithm description
8.3.2. Configuration
8.4. Scalability of Exhaustive Search

Exact methods will always find the global optimum and recognize it too. That being said, they don't scale (not even beyond toy data sets) and are therefore mostly useless.

Simplest configuration of Branch And Bound:


<solver>
  ...
  <exhaustiveSearch>
    <exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
  </exhaustiveSearch>
</solver>

Important

For the pruning to work with the default ScoreBounder, the InitializingScoreTrend should be set. Especially an InitializingScoreTrend of ONLY_DOWN (or at least has ONLY_DOWN in the leading score levels) prunes a lot.

Advanced configuration:


  <exhaustiveSearch>
    <exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
    <nodeExplorationType>DEPTH_FIRST</nodeExplorationType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </exhaustiveSearch>

The nodeExplorationType options are:

  • DEPTH_FIRST (default): Explore deeper nodes first (and then a better score and then a better optimistic bound). Deeper nodes (especially leaf nodes) often improve the pessimistic bound. A better pessimistic bound allows pruning more nodes to reduce the search space.

    
      <exhaustiveSearch>
        <exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
        <nodeExplorationType>DEPTH_FIRST</nodeExplorationType>
      </exhaustiveSearch>
  • BREADTH_FIRST (not recommended): Explore nodes layer by layer (and then a better score and then a better optimistic bound). Scales terribly in memory (and usually in performance too).

    
      <exhaustiveSearch>
        <exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
        <nodeExplorationType>BREADTH_FIRST</nodeExplorationType>
      </exhaustiveSearch>
  • SCORE_FIRST: Explore nodes with a better score first (and then a better optimistic bound and then deeper nodes first). Might scale as terribly as BREADTH_FIRST in some cases.

    
      <exhaustiveSearch>
        <exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
        <nodeExplorationType>SCORE_FIRST</nodeExplorationType>
      </exhaustiveSearch>
  • OPTIMISTIC_BOUND_FIRST: Explore nodes with a better optimistic bound first (and then a better score and then deeper nodes first). Might scale as terribly as BREADTH_FIRST in some cases.

    
      <exhaustiveSearch>
        <exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
        <nodeExplorationType>OPTIMISTIC_BOUND_FIRST</nodeExplorationType>
      </exhaustiveSearch>

The entitySorterManner options are:

  • DECREASING_DIFFICULTY: Initialize the more difficult planning entities first. This usually increases pruning (and therefore improves scalability). Requires the model to support planning entity difficulty comparison.

  • DECREASING_DIFFICULTY_IF_AVAILABLE (default): If the model supports planning entity difficulty comparison, behave like DECREASING_DIFFICULTY, else like NONE.

  • NONE: Initialize the planning entities in original order.

The valueSorterManner options are:

Exhaustive Search variants suffer from 2 big scalability issues:

As shown in these time spent graphs from the Benchmarker, Brute Force and Branch And Bound both hit a performance scalability wall. For example, on N queens it hits wall at a few dozen queens:

In most use cases, such as Cloud Balancing, the wall appears out of thin air:

Exhaustive Search hits this wall on small datasets already, so in production these optimizations algorithms are mostly useless. Use Construction Heuristics with Local Search instead: those can handle thousands of queens/computers easily.

Note

Throwing hardware at these scalability issues has no noticeable impact. Newer and more hardware are just a drop in the ocean. Moore's law cannot win against the onslaught of a few more planning entities in the dataset.