////
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements.  See the NOTICE file
distributed with this work for additional information
regarding copyright ownership.  The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License.  You may obtain a copy of the License at

  http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
KIND, either express or implied.  See the License for the
specific language governing permissions and limitations
under the License.
////

[[constructionHeuristics]]
= Construction heuristics
:doctype: book
:sectnums:
:icons: font


[[constructionHeuristicsOverview]]
== 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 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.


[[firstFit]]
== First fit


[[firstFitAlgorithm]]
=== Algorithm description

The First Fit algorithm cycles through all the planning entities (in default order), initializing one 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.

image::construction-heuristics/firstFitNQueens04.png[align="center"]

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.


[[firstFitConfiguration]]
=== Configuration

Simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
  </constructionHeuristic>
----

Advanced configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
    <...MoveSelector/>
    <...MoveSelector/>
    ...
  </constructionHeuristic>
----

For scaling out, see <<scalingConstructionHeuristics,scaling construction heuristics>>.
For a very advanced configuration, see <<allocateEntityFromQueue,Allocate Entity From Queue>>.


[[firstFitDecreasing]]
== First fit decreasing


[[firstFitDecreasingAlgorithm]]
=== Algorithm description

Like <<firstFit,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.

image::construction-heuristics/firstFitDecreasingNQueens04.png[align="center"]

Requires the model to support xref:planner-configuration/planner-configuration.adoc#planningEntityDifficulty[planning entity difficulty comparison].

[NOTE]
====
One would expect that this algorithm has better results than First Fit.
That's usually the case, but not always.
====


[[firstFitDecreasingConfiguration]]
=== Configuration

Simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>
----

Advanced configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
    <...MoveSelector/>
    <...MoveSelector/>
    ...
  </constructionHeuristic>
----

For scaling out, see <<scalingConstructionHeuristics,scaling construction heuristics>>.
For a very advanced configuration, see <<allocateEntityFromQueue,Allocate Entity From Queue>>.


[[weakestFit]]
== Weakest fit


[[weakestFitAlgorithm]]
=== 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 xref:planner-configuration/planner-configuration.adoc#planningValueStrength[planning value strength comparison].

[NOTE]
====
Do not presume that this algorithm has better results than First Fit.
That's often not the case.
====


[[weakestFitConfiguration]]
=== Configuration

Simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_FIT</constructionHeuristicType>
  </constructionHeuristic>
----

Advanced configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_FIT</constructionHeuristicType>
    <...MoveSelector/>
    <...MoveSelector/>
    ...
  </constructionHeuristic>
----

For scaling out, see <<scalingConstructionHeuristics,scaling construction heuristics>>.
For a very advanced configuration, see <<allocateEntityFromQueue,Allocate Entity From Queue>>.


[[weakestFitDecreasing]]
== Weakest fit decreasing


[[weakestFitDecreasingAlgorithm]]
=== Algorithm description

Combines First Fit Decreasing and Weakest Fit.
So it sorts the planning entities on decreasing difficulty and the planning values on increasing strength.

Requires the model to support xref:planner-configuration/planner-configuration.adoc#planningEntityDifficulty[planning entity difficulty comparison]
and xref:planner-configuration/planner-configuration.adoc#planningValueStrength[planning value strength comparison].

[NOTE]
====
Do not presume that this algorithm has better results than First Fit Decreasing.
That's often not the case.
However, it is usually better than Weakest Fit.
====


[[weakestFitDecreasingConfiguration]]
=== Configuration

Simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>
----

Advanced configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_FIT_DECREASING</constructionHeuristicType>
    <...MoveSelector/>
    <...MoveSelector/>
    ...
  </constructionHeuristic>
----

For scaling out, see <<scalingConstructionHeuristics,scaling construction heuristics>>.
For a very advanced configuration, see <<allocateEntityFromQueue,Allocate Entity From Queue>>.


[[strongestFit]]
== Strongest fit


[[strongestFitAlgorithm]]
=== Algorithm description

Like First Fit, but uses the strong planning values first, because the strong planning values are more likely to have a lower soft cost to use.
So it sorts the planning values on decreasing strength.

Requires the model to support xref:planner-configuration/planner-configuration.adoc#planningValueStrength[planning value strength comparison].

[NOTE]
====
Do not presume that this algorithm has better results than First Fit or Weakest Fit.
That's often not the case.
====


[[strongestFitConfiguration]]
=== Configuration

Simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>STRONGEST_FIT</constructionHeuristicType>
  </constructionHeuristic>
----

Advanced configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>STRONGEST_FIT</constructionHeuristicType>
    <...MoveSelector/>
    <...MoveSelector/>
    ...
  </constructionHeuristic>
----

For scaling out, see <<scalingConstructionHeuristics,scaling construction heuristics>>.
For a very advanced configuration, see <<allocateEntityFromQueue,Allocate Entity From Queue>>.


[[strongestFitDecreasing]]
== Strongest fit decreasing


[[strongestFitDecreasingAlgorithm]]
=== Algorithm description

Combines First Fit Decreasing and Strongest Fit.
So it sorts the planning entities on decreasing difficulty and the planning values on decreasing strength.

Requires the model to support xref:planner-configuration/planner-configuration.adoc#planningEntityDifficulty[planning entity difficulty comparison]
and xref:planner-configuration/planner-configuration.adoc#planningValueStrength[planning value strength comparison].

[NOTE]
====
Do not presume that this algorithm has better results than First Fit Decreasing or Weakest Fit Decreasing.
That's often not the case.
However, it is usually better than Strongest Fit.
====


[[strongestFitDecreasingConfiguration]]
=== Configuration

Simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>STRONGEST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>
----

Advanced configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>STRONGEST_FIT_DECREASING</constructionHeuristicType>
    <...MoveSelector/>
    <...MoveSelector/>
    ...
  </constructionHeuristic>
----

For scaling out, see <<scalingConstructionHeuristics,scaling construction heuristics>>.
For a very advanced configuration, see <<allocateEntityFromQueue,Allocate Entity From Queue>>.


[[allocateEntityFromQueue]]
== Allocate entity from queue


[[allocateEntityFromQueueAlgorithm]]
=== Algorithm description

Allocate Entity From Queue is a versatile, generic form of <<firstFit,First Fit>>, <<firstFitDecreasing,First Fit Decreasing>>,
<<weakestFit,Weakest Fit>>, <<weakestFitDecreasing,Weakest Fit Decreasing>>,
<<strongestFit,Strongest Fit>> and <<strongestFitDecreasing,Strongest Fit Decreasing>>.
It works like this:

. Put all entities in a queue.
. Assign the first entity (from that queue) to the best value.
. Repeat until all entities are assigned.


[[allocateEntityFromQueueConfiguration]]
=== Configuration

Simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_ENTITY_FROM_QUEUE</constructionHeuristicType>
  </constructionHeuristic>
----

Verbose simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_ENTITY_FROM_QUEUE</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>
----

The `entitySorterManner` options are:

* ``DECREASING_DIFFICULTY``: Initialize the more difficult planning entities first.
This usually increases pruning (and therefore improves scalability).
Requires the model to support xref:planner-configuration/planner-configuration.adoc#planningEntityDifficulty[planning entity difficulty comparison].
* `DECREASING_DIFFICULTY_IF_AVAILABLE` (default): If the model supports xref:planner-configuration/planner-configuration.adoc#planningEntityDifficulty[planning entity difficulty comparison], behave like ``DECREASING_DIFFICULTY``, else like ``NONE``.
* ``NONE``: Initialize the planning entities in original order.

The `valueSorterManner` options are:

* ``INCREASING_STRENGTH``: Evaluate the planning values in increasing strength.
Requires the model to support xref:planner-configuration/planner-configuration.adoc#planningValueStrength[planning value strength comparison].
* `INCREASING_STRENGTH_IF_AVAILABLE` (default): If the model supports xref:planner-configuration/planner-configuration.adoc#planningValueStrength[planning value strength comparison], behave like ``INCREASING_STRENGTH``, else like ``NONE``.
* ``DECREASING_STRENGTH``: Evaluate the planning values in decreasing strength.
Requires the model to support xref:planner-configuration/planner-configuration.adoc#planningValueStrength[planning value strength comparison].
* ``DECREASING_STRENGTH_IF_AVAILABLE``: If the model supports xref:planner-configuration/planner-configuration.adoc#planningValueStrength[planning value strength comparison], behave like ``DECREASING_STRENGTH``, else like ``NONE``.
* ``NONE``: Try the planning values in original order.

Advanced configuration with <<weakestFitDecreasing,Weakest Fit Decreasing>> for a single entity class with one variable:

[source,xml,options="nowrap"]
----
  <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 one uninitialized entity from the `EntitySelector`
and applies the winning `Move` (out of all the moves for that entity generated by the ``MoveSelector``).
The xref:move-and-neighborhood-selection/move-and-neighborhood-selection.adoc#mimicSelection[mimic selection] ensures that the winning `Move` changes only the selected entity.

To customize the entity or value sorting, see xref:move-and-neighborhood-selection/move-and-neighborhood-selection.adoc#sortedSelection[sorted selection].
For scaling out, see <<scalingConstructionHeuristics,scaling construction heuristics>>.

If there are multiple planning variables, there's one `ChangeMoveSelector` per planning variable,
which are either in a cartesian product or in sequential steps,
similar to <<scalingMultiplePlanningVariablesInConstructionHeuristics,the less verbose configuration>>.


[[allocateEntityFromQueueMultipleEntityClasses]]
=== Multiple entity classes

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

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <entityClass>...DogEntity</entityClass>
        <cacheType>PHASE</cacheType>
      </entitySelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
      </changeMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>
  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <entityClass>...CatEntity</entityClass>
        <cacheType>PHASE</cacheType>
      </entitySelector>
      <changeMoveSelector>
        <entitySelector mimicSelectorRef="placerEntitySelector"/>
      </changeMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>
----


[[constructionHeuristicsPickEarlyType]]
=== Pick early type

There are several pick early types for Construction Heuristics:

* ``NEVER``: Evaluate all the selected moves to initialize the variable(s).
This is the default if the xref:score-calculation/score-calculation.adoc#initializingScoreTrend[InitializingScoreTrend] is not ``ONLY_DOWN``.
+
[source,xml,options="nowrap"]
----
  <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 xref:score-calculation/score-calculation.adoc#initializingScoreTrend[InitializingScoreTrend] is ``ONLY_DOWN``.
+
[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    ...
    <forager>
      <pickEarlyType>FIRST_NON_DETERIORATING_SCORE</pickEarlyType>
    </forager>
  </constructionHeuristic>
----
+
[NOTE]
====
If there are only negative constraints, but the xref:score-calculation/score-calculation.adoc#initializingScoreTrend[InitializingScoreTrend] is strictly not ``ONLY_DOWN``,
it can sometimes make sense to apply FIRST_NON_DETERIORATING_SCORE.
Use the xref:benchmarking-and-tweaking/benchmarking-and-tweaking.adoc#benchmarker[Benchmarker] to decide if the score quality loss is worth the time gain.
====
* ``FIRST_FEASIBLE_SCORE``: Initialize the variable(s) with the first move that has a feasible score.
+
[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    ...
    <forager>
      <pickEarlyType>FIRST_FEASIBLE_SCORE</pickEarlyType>
    </forager>
  </constructionHeuristic>
----
+
If the xref:score-calculation/score-calculation.adoc#initializingScoreTrend[InitializingScoreTrend] is ``ONLY_DOWN``, use `FIRST_FEASIBLE_SCORE_OR_NON_DETERIORATING_HARD` instead, because that's faster without any disadvantages.
* ``FIRST_FEASIBLE_SCORE_OR_NON_DETERIORATING_HARD``: Initialize the variable(s) with the first move that doesn't deteriorate the feasibility of the score any further.
+
[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    ...
    <forager>
      <pickEarlyType>FIRST_FEASIBLE_SCORE_OR_NON_DETERIORATING_HARD</pickEarlyType>
    </forager>
  </constructionHeuristic>
----


[[allocateToValueFromQueue]]
== Allocate to value from queue


[[allocateToValueFromQueueAlgorithm]]
=== Algorithm description

Allocate To Value From Queue works like this:

. Put all values in a round-robin queue.
. Assign the best entity to the first value (from that queue).
. Repeat until all entities are assigned.


[[allocateToValueFromQueueConfiguration]]
=== Configuration

Simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_TO_VALUE_FROM_QUEUE</constructionHeuristicType>
  </constructionHeuristic>
----

Verbose simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_TO_VALUE_FROM_QUEUE</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>
----

Advanced configuration for a single entity class with a single variable:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <queuedValuePlacer>
      <valueSelector id="placerValueSelector">
        <cacheType>PHASE</cacheType>
        <selectionOrder>SORTED</selectionOrder>
        <sorterManner>INCREASING_STRENGTH</sorterManner>
      </valueSelector>
      <changeMoveSelector>
        <entitySelector>
          <cacheType>PHASE</cacheType>
          <selectionOrder>SORTED</selectionOrder>
          <sorterManner>DECREASING_DIFFICULTY</sorterManner>
        </entitySelector>
        <valueSelector mimicSelectorRef="placerValueSelector"/>
      </changeMoveSelector>
    </queuedValuePlacer>
  </constructionHeuristic>
----

For scaling out, see <<scalingConstructionHeuristics,scaling construction heuristics>>.


[[cheapestInsertion]]
== Cheapest insertion


[[cheapestInsertionAlgorithm]]
=== Algorithm description

The Cheapest Insertion algorithm cycles through all the planning values for all the planning entities, initializing one 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.

image::construction-heuristics/cheapestInsertionNQueens04.png[align="center"]


[NOTE]
====
Cheapest Insertion scales considerably worse than First Fit, etc.
====


[[cheapestInsertionConfiguration]]
=== Configuration

Simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>CHEAPEST_INSERTION</constructionHeuristicType>
  </constructionHeuristic>
----

Advanced configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>CHEAPEST_INSERTION</constructionHeuristicType>
    <...MoveSelector/>
    <...MoveSelector/>
    ...
  </constructionHeuristic>
----

For scaling out, see <<scalingConstructionHeuristics,scaling construction heuristics>>.
For a very advanced configuration, see <<allocateFromPool,Allocate from pool>>.


[[regretInsertion]]
== Regret insertion


[[regretInsertionAlgorithm]]
=== Algorithm description

The Regret Insertion algorithm behaves like the Cheapest Insertion algorithm.
It also cycles through all the planning values for all the planning entities, initializing one planning entity at a time.
But instead of picking the entity-value combination with the best score, it picks the entity which has the largest score loss between its best and second best value assignment.
It then assigns that entity to its best value, to avoid regretting not having done that.


[[regretInsertionConfiguration]]
=== Configuration

This algorithm has not been implemented yet.


[[allocateFromPool]]
== Allocate from pool


[[allocateFromPoolAlgorithm]]
=== Algorithm description

Allocate From Pool is a versatile, generic form of <<cheapestInsertion,Cheapest Insertion>> and <<regretInsertion,Regret Insertion>>.
It works like this:

. Put all entity-value combinations in a pool.
. Assign the best entity to best value.
. Repeat until all entities are assigned.


[[allocateFromPoolConfiguration]]
=== Configuration

Simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_FROM_POOL</constructionHeuristicType>
  </constructionHeuristic>
----

Verbose simple configuration:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_FROM_POOL</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>
----

The `entitySorterManner` and `valueSorterManner` options are described in <<allocateEntityFromQueue,Allocate Entity From Queue>>.

Advanced configuration with <<cheapestInsertion,Cheapest Insertion>> for a single entity class with a single variable:

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <pooledEntityPlacer>
      <changeMoveSelector>
        <entitySelector id="placerEntitySelector">
          <cacheType>PHASE</cacheType>
          <selectionOrder>SORTED</selectionOrder>
          <sorterManner>DECREASING_DIFFICULTY</sorterManner>
        </entitySelector>
        <valueSelector>
          <cacheType>PHASE</cacheType>
          <selectionOrder>SORTED</selectionOrder>
          <sorterManner>INCREASING_STRENGTH</sorterManner>
        </valueSelector>
      </changeMoveSelector>
    </pooledEntityPlacer>
  </constructionHeuristic>
----

Per step, the `PooledEntityPlacer` applies the winning `Move` (out of all the moves for that entity generated by the ``MoveSelector``).

To customize the entity or value sorting, see xref:move-and-neighborhood-selection/move-and-neighborhood-selection.adoc#sortedSelection[sorted selection].
Other `Selector` customization (such as xref:move-and-neighborhood-selection/move-and-neighborhood-selection.adoc#filteredSelection[filtering] and xref:move-and-neighborhood-selection/move-and-neighborhood-selection.adoc#limitedSelection[limiting]) is supported too.

For scaling out, see <<scalingConstructionHeuristics,scaling construction heuristics>>.


[[scalingConstructionHeuristics]]
== Scaling construction heuristics

If the Construction Heuristic takes a long time to solve and create an initial solution,
there is too little time left for xref:local-search/local-search.adoc#localSearch[Local Search] to reach a near optimal solution.

Ideally, a Construction Heuristic should take less than 20 seconds from scratch
and less than 50 milliseconds in xref:repeated-planning/repeated-planning.adoc#realTimePlanning[real-time planning],
so there is plenty of time left for xref:local-search/local-search.adoc#localSearch[Local Search].
If the xref:benchmarking-and-tweaking/benchmarking-and-tweaking.adoc#benchmarker[Benchmarker] proves that this is not the case, there's a number of improvements that can be done:


[[initializingScoreTrendShortcuts]]
=== InitializingScoreTrend shortcuts

If the xref:score-calculation/score-calculation.adoc#initializingScoreTrend[InitializingScoreTrend] is ``ONLY_DOWN``, a Construction Heuristic algorithm (such as First Fit) 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 in that step.

It can take that shortcut without reducing solution quality,
because a down trend guarantees that initializing any additional planning variable can only make the score the same or worse.
So if a move has the same score as before the planning variable was initialized, then no other move can have a better score.


[[scalingMultiplePlanningVariablesInConstructionHeuristics]]
=== Scaling multiple planning variables in construction heuristics

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

* *Cartesian product* (default): All variables of the selected entity are assigned together.
This usually results in a better solution quality, but it scales poorly because it tries every combination of variables. For example:
+
[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
    <cartesianProductMoveSelector>
      <changeMoveSelector>
        <valueSelector variableName="period"/>
      </changeMoveSelector>
      <changeMoveSelector>
        <valueSelector variableName="room"/>
      </changeMoveSelector>
    </cartesianProductMoveSelector>
  </constructionHeuristic>
----
* *Sequential*: One variable is assigned at a time.
Scales better, at the cost of solution quality. The order of the planning variables matters. For example:
+
[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
    <changeMoveSelector>
      <valueSelector variableName="period"/>
    </changeMoveSelector>
    <changeMoveSelector>
      <valueSelector variableName="room"/>
    </changeMoveSelector>
  </constructionHeuristic>
----

The second way scales better, so it can be worth to switch to it.
For example, in a course scheduling example with 200 rooms and 40 periods,
a cartesian product selects 8{nbsp}000 moves per entity (1 step per entity).
On the other hand, a sequential approach only selects 240 moves per entity (2 steps per entity),
ending the Construction Heuristic 3 times faster.
Especially for three or more planning variables, the scaling difference is huge.
For example, with three variables of 1{nbsp}000 values each,
a cartesian product selects 1{nbsp}000{nbsp}000{nbsp}000 moves per entity (1 step per entity).
A sequential approach only selects 3{nbsp}000 moves per entity (3 steps per entity),
ending the Construction Heuristic 300{nbsp}000 times faster.

image::construction-heuristics/multiVariableConstructionHeuristics.png[align="center"]

[IMPORTANT]
====
The order of the variables is important, especially in the sequential technique.
In the sequential example above, it's better to select the `period` first and the `room` second (instead of the other way around),
because there are more hard constraints that do not involve the room, such as _no teacher should teach two lectures at the same time_.

Let the xref:benchmarking-and-tweaking/benchmarking-and-tweaking.adoc#benchmarker[Benchmarker] guide you.
====

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

[source,xml,options="nowrap"]
----
  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
    <cartesianProductMoveSelector>
      <changeMoveSelector>
        <valueSelector variableName="period"/>
      </changeMoveSelector>
      <changeMoveSelector>
        <valueSelector variableName="room"/>
      </changeMoveSelector>
    </cartesianProductMoveSelector>
    <changeMoveSelector>
      <valueSelector variableName="teacher"/>
    </changeMoveSelector>
  </constructionHeuristic>
----


[[otherScalingTechniquesInConstructionHeuristics]]
=== Other scaling techniques in construction heuristics

xref:partitioned-search/partitioned-search.adoc#partitionedSearch[Partitioned Search] reduces the number of moves per step.
On top of that, it runs the Construction Heuristic on the partitions in parallel.
It is supported to only partition the Construction Heuristic phase.

Other `Selector` customizations can also reduce the number of moves generated by step:

* xref:move-and-neighborhood-selection/move-and-neighborhood-selection.adoc#filteredSelection[Filtered selection]
* xref:move-and-neighborhood-selection/move-and-neighborhood-selection.adoc#limitedSelection[Limited selection]
