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 assigned.

Notice that it starts with putting `Queen` A into row 0 (and never moving it later), which 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 assigns the more difficult planning entities first, because they are less likely to fit in the leftovers. So it sorts the planning entities on decreasing difficulty.

Requires the model to support planning entity difficulty comparison.

## Note

One would expect that this algorithm always performs better than `First Fit`. That's not always the case, but usually is.

### 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 uses the weaker planning values first, because the strong planning values are more likely to be able to accomodate later planning entities. So it sorts the planning values on increasing strength.

Requires the model to support planning value strength comparison.

## Note

One would expect that this algorithm always performs better than `First Fit`. That's not always the case.

### 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

Combines `First Fit Decreasing` and `Best Fit`. So it sorts the planning entities on decreasing difficulty and the planning values on increasing strength.

Requires the model to support planning entity difficulty comparison and planning value strength comparison.

## Note

One would expect that this algorithm always performs better than `First Fit`, `First Fit Decreasing` and `Best Fit`. That's not always the case.

### 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