JBoss.org Community Documentation

- Prev
- Next

## Chapter 8. Construction heuristics

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

## 8.2. First Fit

### 8.2.1. Algorithm description

The First Fit algorithm cycles through all the planning entities (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 to reach the optimal solution. Suffixing this construction heuristic with metaheurstics can remedy that.

### 8.2.2. Configuration

Configure this `SolverPhase`:

      <constructionHeuristic>

        <constructionHeuristicType>FIRST_FIT</constructionHeuristicType>

        <!-- Speedup that can be applied to most, but not all use cases: -->

        <!--forager-->

          <!-- <pickEarlyType>FIRST_NON_DETERIORATING_SCORE</pickEarlyType> -->

        <!--/forager-->

      </constructionHeuristic>

## Note

The `pickEarlyType` of `FIRST_NON_DETERIORATING_SCORE` is a big speedup: for an entity, it picks the first move for which the score does not deteriorate the last step score, ignoring all subsequent moves. It should be applied when initializing a planning entity cannot improve the last step score: it can only make the score lower or equal. So if:

- There are no positive constraints.

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

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

## 8.3. First Fit Decreasing

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

### 8.3.2. Configuration

Configure this `SolverPhase`:

      <constructionHeuristic>

        <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>

        <!-- Speedup that can be applied to most, but not all use cases: -->

        <!--forager-->

          <!-- <pickEarlyType>FIRST_NON_DETERIORATING_SCORE</pickEarlyType> -->

        <!--/forager-->

      </constructionHeuristic>

## 8.4. Best Fit

### 8.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 accommodate 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.

### 8.4.2. Configuration

Configure this `SolverPhase`:

      <constructionHeuristic>

        <constructionHeuristicType>BEST_FIT</constructionHeuristicType>

        <!-- Speedup that can be applied to most, but not all use cases: -->

        <!--forager-->

          <!-- <pickEarlyType>FIRST_NON_DETERIORATING_SCORE</pickEarlyType> -->

        <!--/forager-->

      </constructionHeuristic>

## 8.5. Best Fit Decreasing

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

### 8.5.2. Configuration

Configure this `SolverPhase`:

      <constructionHeuristic>

        <constructionHeuristicType>BEST_FIT_DECREASING</constructionHeuristicType>

        <!-- Speedup that can be applied to most, but not all use cases: -->

        <!--forager-->

          <!-- <pickEarlyType>FIRST_NON_DETERIORATING_SCORE</pickEarlyType> -->

        <!--/forager-->

      </constructionHeuristic>

## 8.6. Cheapest insertion

### 8.6.1. Algorithm description

TODO

### 8.6.2. Configuration

TODO Not implemented yet.

## 8.7. Regret insertion

### 8.7.1. Algorithm description

TODO

### 8.7.2. Configuration

TODO Not implemented yet.

- PrevChapter 7. Move and neighborhood selection
- Top of page
- Front page
- NextChapter 9. Local search