JBoss.org Community Documentation

- Prev
- Next

## Chapter 6. Exact methods

## 6.1. Overview

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

## 6.2. Brute Force

### 6.2.1. Algorithm description

The brute force algorithm creates and evaluates every possible solution.

Notice that it creates a search tree that explodes as the problem size increases. Brute force is mostly unusable for a real-world problem due to time limitations.

### 6.2.2. Configuration

Using the brute force algorithm is easy:

    <solver>
      ...
      <bruteForce>
      </bruteForce>
    </solver>

## 6.3. Branch and bound

### 6.3.1. Algorithm description

Branch and bound is an improvement over brute force, as it prunes away subsets of solutions which cannot have a better solution than the best solution already found at that point.

Notice that it (like brute force) creates a search tree that explodes (but less than brute force) as the problem size increases. Branch and bound is mostly unusable for a real-world problem due to time limitations.

It can determine a lower bound of problem. A lower bound is a score which is proven to be higher than the optimal score of a problem. So it gives an indication of the quality of any best solution found for that problem: the closer to best score is to the lower bound, the better.

### 6.3.2. Configuration

Branch and bound is not yet implemented in Drools Planner. Patches welcome.

- PrevChapter 5. Optimization algorithms
- Top of page
- Front page
- NextChapter 7. Construction heuristics