## Chapter 8. Construction heuristics

8.1. Overview
8.2. First Fit
8.2.1. Algorithm description
8.2.2. Configuration
8.3. First Fit Decreasing
8.3.1. Algorithm description
8.3.2. Configuration
8.4. Best Fit
8.4.1. Algorithm description
8.4.2. Configuration
8.5. Best Fit Decreasing
8.5.1. Algorithm description
8.5.2. Configuration
8.6.1. Algorithm description
8.6.2. Configuration
8.6.3. Multiple variables
8.6.4. Multiple entity classes
8.6.5. Pick early type
8.7. Cheapest insertion
8.7.1. Algorithm description
8.7.2. Configuration
8.8. Regret insertion
8.8.1. Algorithm description
8.8.2. Configuration

## 8.2. First Fit

### 8.2.2. Configuration

Configure this `SolverPhase`:

```
<constructionHeuristic>
<constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
</constructionHeuristic>
```

## Note

If the InitializingScoreTrend is `ONLY_DOWN`, this algorithm is faster: for an entity, it picks the first move for which the score does not deteriorate the last step score, ignoring all subsequent moves.

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

## Note

One would expect that this algorithm has better results 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>
</constructionHeuristic>
```

## Note

If the InitializingScoreTrend is `ONLY_DOWN`, this algorithm is faster: for an entity, it picks the first move for which the score does not deteriorate the last step score, ignoring all subsequent moves.

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

## Note

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

### 8.4.2. Configuration

Configure this `SolverPhase`:

```
<constructionHeuristic>
<constructionHeuristicType>BEST_FIT</constructionHeuristicType>
</constructionHeuristic>
```

## Note

If the InitializingScoreTrend is `ONLY_DOWN`, this algorithm is faster: for an entity, it picks the first move for which the score does not deteriorate the last step score, ignoring all subsequent moves.

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

## Note

One would expect that this algorithm has better results 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>
</constructionHeuristic>
```

## Note

If the InitializingScoreTrend is `ONLY_DOWN`, this algorithm is faster: for an entity, it picks the first move for which the score does not deteriorate the last step score, ignoring all subsequent moves.

### 8.6.2. Configuration

A Best Fit Decreasing configuration for a single entity class with a single variable (which is the verbose version of the simple `constructionHeuristicType` `BEST_FIT_DECREASING` configuration):

```
<constructionHeuristic>
<queuedEntityPlacer>
<entitySelector id="placerEntitySelector">
<cacheType>PHASE</cacheType>
<selectionOrder>SORTED</selectionOrder>
<sorterManner>DECREASING_DIFFICULTY</sorterManner>
</entitySelector>
<changeMoveSelector>
<entitySelector mimicSelectorRef="placerEntitySelector"/>
<valueSelector>
<cacheType>PHASE</cacheType>
<selectionOrder>SORTED</selectionOrder>
<sorterManner>INCREASING_STRENGTH</sorterManner>
</valueSelector>
</changeMoveSelector>
</queuedEntityPlacer>
</constructionHeuristic>
```

Per step, the `QueuedEntityPlacer` selects 1 uninitialized entity from the `EntitySelector` and applies the winning `Move` (out of all the moves for that entity generated by the `MoveSelector`). The mimic selection ensures that the winning `Move` changes (only) the selected entity.

To customize the entity or value sorting, see sorted selection. Other `Selector` customization (such as filtering and limiting) is supported too.

### 8.6.3. Multiple variables

There are 2 ways to deal with multiple variables, depending on how their `ChangeMove`s are combined:

For example, presume a course scheduling example with 200 rooms and 40 periods.

This First Fit configuration for a single entity class with 2 variables, using a cartesian product of their `ChangeMove`s, will select 8000 moves per entity:

```
<constructionHeuristic>
<queuedEntityPlacer>
<entitySelector id="placerEntitySelector">
<cacheType>PHASE</cacheType>
</entitySelector>
<cartesianProductMoveSelector>
<changeMoveSelector>
<entitySelector mimicSelectorRef="placerEntitySelector"/>
<valueSelector>
<variableName>room</variableName>
</valueSelector>
</changeMoveSelector>
<changeMoveSelector>
<entitySelector mimicSelectorRef="placerEntitySelector"/>
<valueSelector>
<variableName>period</variableName>
</valueSelector>
</changeMoveSelector>
</cartesianProductMoveSelector>
</queuedEntityPlacer>
...
</constructionHeuristic>
```

## Warning

With 3 variables of 1000 values each, a cartesian product selects 1000000000 values per entity, which will take far too long.

This First Fit configuration for a single entity class with 2 variables, using sequential `ChangeMove`s, will select 240 moves per entity:

```
<constructionHeuristic>
<queuedEntityPlacer>
<entitySelector id="placerEntitySelector">
<cacheType>PHASE</cacheType>
</entitySelector>
<changeMoveSelector>
<entitySelector mimicSelectorRef="placerEntitySelector"/>
<valueSelector>
<variableName>period</variableName>
</valueSelector>
</changeMoveSelector>
<changeMoveSelector>
<entitySelector mimicSelectorRef="placerEntitySelector"/>
<valueSelector>
<variableName>room</variableName>
</valueSelector>
</changeMoveSelector>
</queuedEntityPlacer>
...
</constructionHeuristic>
```

## Important

Especially for sequential `ChangeMove`s, the order of the variables is important. In the example above, it's better to select the period first (instead of the other way around), because there are more hard constraints that do not involve the room (for example: no teacher should teach 2 lectures at the same time). Let the Benchmarker guide you.

With 3 or more variables, it's possible to combine the cartesian product and sequential techniques:

```
<constructionHeuristic>
<queuedEntityPlacer>
...
<cartesianProductMoveSelector>
<changeMoveSelector>...</changeMoveSelector>
<changeMoveSelector>...</changeMoveSelector>
</cartesianProductMoveSelector>
<changeMoveSelector>...</changeMoveSelector>
</queuedEntityPlacer>
...
</constructionHeuristic>
```

### 8.6.4. Multiple entity classes

The easiest way to deal with multiple entity classes is to run a separate construction heuristic for each entity class:

```
<constructionHeuristic>
<queuedEntityPlacer>
<entitySelector id="placerEntitySelector">
<cacheType>PHASE</cacheType>
<entityClass>...DogEntity</entityClass>
</entitySelector>
<changeMoveSelector>
<entitySelector mimicSelectorRef="placerEntitySelector"/>
</changeMoveSelector>
</queuedEntityPlacer>
...
</constructionHeuristic>
<constructionHeuristic>
<queuedEntityPlacer>
<entitySelector id="placerEntitySelector">
<cacheType>PHASE</cacheType>
<entityClass>...CatEntity</entityClass>
</entitySelector>
<changeMoveSelector>
<entitySelector mimicSelectorRef="placerEntitySelector"/>
</changeMoveSelector>
</queuedEntityPlacer>
...
</constructionHeuristic>
```

### 8.6.5. Pick early type

There are 2 pick early types for Construction Heuristics:

• ```
<constructionHeuristic>
...
<forager>
<pickEarlyType>NEVER</pickEarlyType>
</forager>
</constructionHeuristic>
```
• `FIRST_NON_DETERIORATING_SCORE`: Initialize the variable(s) with the first move that doesn't deteriorate the score, ignore the remaining selected moves. This is the default if the InitializingScoreTrend is `ONLY_DOWN`.

```
<constructionHeuristic>
...
<forager>
<pickEarlyType>FIRST_NON_DETERIORATING_SCORE</pickEarlyType>
</forager>
</constructionHeuristic>
```

If there are only negative constraints, but the InitializingScoreTrend is strictly not `ONLY_DOWN`, it can make sense to apply FIRST_NON_DETERIORATING_SCORE. Use the Benchmarker to decide if the score quality loss is worth the time gain.

## 8.7. Cheapest insertion

TODO

### 8.7.2. Configuration

TODO Not implemented yet.

## 8.8. Regret insertion

TODO

### 8.8.2. Configuration

TODO Not implemented yet.