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 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 initialized.
Notice that putting Queen A into row 0 (and never moving it later) makes it impossible
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: -->
<!-- <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.
Like First Fit, but sorts the planning entities on decreasing difficulty.
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>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>Like First Fit, but sorts the planning entities on decreasing difficulty and the planning
values on increasing strength.
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>