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 so 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.
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 metaheuristics can
remedy that.
Configure this solver phase:
<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.
For advanced configuration, see Advanced Greedy Fit.
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 has better results than First Fit. That's not always the case, but usually is.
Configure this solver phase:
<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.
For advanced configuration, see Advanced Greedy Fit.
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 has better results than First Fit. That's not always the case.
Configure this solver phase:
<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.
For advanced configuration, see Advanced Greedy Fit.
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 has better results than First Fit, First Fit Decreasing and Best Fit. That's not always the case.
Configure this solver phase:
<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.
For advanced configuration, see Advanced Greedy Fit.
Advanced Greedy Fit is a versatile, generic form of First Fit, First Fit Decreasing, Best Fit and Best Fit Decreasing.
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.
There are 2 ways to deal with multiple variables, depending on how their ChangeMoves are
combined:
Cartesian product of the
ChangeMoves (default): All variables of the selected entity are assigned together. Has far better results (especially for timetabling use cases).Sequential
ChangeMoves: One variable is assigned at a time. Scales much better, especially for 3 or more variables.
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 ChangeMoves, 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
ChangeMoves, 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 ChangeMoves, 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>
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>
There are 2 pick early types for Construction Heuristics:
NEVER: Evaluate all the selected moves to initialize the variable(s). This is the default if the InitializingScoreTrend is notONLY_DOWN.<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 isONLY_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.
The Cheapest Insertion algorithm cycles through all the planning values for all the planning entities, initializing 1 planning entity at a time. It assigns a planning entity to the best available planning value (out of all the planning entities and values), 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.
Note
Cheapest Insertion scales considerably worse than First Fit, etc.
Simplest configuration of Cheapest Insertion:
<constructionHeuristic>
<constructionHeuristicType>CHEAPEST_INSERTION</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.
For advanced configuration, see Advanced Constructive Insertion.
Advanced Constructive Insertion is a versatile, generic form of Cheapest Insertion and Regret Insertion.