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