JBoss.org Community Documentation

- Prev
- Next

## Chapter 7. Construction heuristics

## 7.1. Overview

A construction heuristic builds a pretty good initial solution in a finite length of time. Its solution isn't always feasible, but it finds it fast and metaheuristics can finish the job.

Construction heuristics terminate automatically, so there's usually no need to configure a `Termination` on the construction heuristic phase specifically.

## 7.2. First Fit

### 7.2.1. Algorithm description

The First Fit algorithm cycles through all the planning entity (in default order), initializing 1 planning entity at a time. It assigns the planning entity to the best available planning value, taking the already initialized planning entities into account. It terminates when all planning entities have been initialized. It never changes a planning entity after it has been initialized.

Notice that putting `Queen` A into row 0 (and never moving it later) makes it impossible reach the optimal solution. Suffixing this construction heuristic with metaheurstics can remedy that.

### 7.2.2. Configuration

Configure this `SolverPhase`:

      <constructionHeuristic>
        <constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
        <!-- Speedup that can be applied to most, but not all use cases: -->
        <!-- <constructionHeuristicPickEarlyType>FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING</constructionHeuristicPickEarlyType> -->
      </constructionHeuristic>

## Note

The `constructionHeuristicPickEarlyType` of `FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING` is a big speedup, which should be applied when initializing a planning entity can only make the score lower or equal. So if:

- There are no positive constraints.

- There is no negative constraint that can stop been broken by adding a planning entity (except if another negative constraint gets broken which outweighs it the first negative constraint).

If that is not the case, then it can still be good to apply it in some cases, but not in most cases. Use the `Benchmarker` to decide.

## 7.3. First Fit Decreasing

### 7.3.1. Algorithm description

Like `First Fit`, but sorts the planning entities on decreasing difficulty.

### 7.3.2. Configuration

Configure this `SolverPhase`:

      <constructionHeuristic>
        <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
        <!-- Speedup that can be applied to most, but not all use cases: -->
        <!-- <constructionHeuristicPickEarlyType>FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING</constructionHeuristicPickEarlyType> -->
      </constructionHeuristic>

## 7.4. Best Fit

### 7.4.1. Algorithm description

Like `First Fit`, but sorts the planning values on increasing strength.

### 7.4.2. Configuration

Configure this `SolverPhase`:

      <constructionHeuristic>
        <constructionHeuristicType>BEST_FIT</constructionHeuristicType>
        <!-- Speedup that can be applied to most, but not all use cases: -->
        <!-- <constructionHeuristicPickEarlyType>FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING</constructionHeuristicPickEarlyType> -->
      </constructionHeuristic>

## 7.5. Best Fit Decreasing

### 7.5.1. Algorithm description

Like `First Fit`, but sorts the planning entities on decreasing difficulty and the planning values on increasing strength.

### 7.5.2. Configuration

Configure this `SolverPhase`:

      <constructionHeuristic>
        <constructionHeuristicType>BEST_FIT_DECREASING</constructionHeuristicType>
        <!-- Speedup that can be applied to most, but not all use cases: -->
        <!-- <constructionHeuristicPickEarlyType>FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING</constructionHeuristicPickEarlyType> -->
      </constructionHeuristic>

## 7.6. Cheapest insertion

### 7.6.1. Algorithm description

TODO

### 7.6.2. Configuration

TODO Not implemented yet.

- PrevChapter 6. Exact methods
- Top of page
- Front page
- NextChapter 8. Local search solver