Red Hat Summit Red Hat SummitSupportKonsoleEntwicklerDemo startenKontakt

Dieser Inhalt ist in der von Ihnen ausgewählten Sprache nicht verfügbar.

Chapter 9. Construction Heuristics

9.1. Overview
Link kopieren

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.

9.2. First Fit
Link kopieren

9.2.1. Algorithm Description
Link kopieren

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.

firstFitNQueens04
View larger image
firstFitNQueens04

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.

9.2.2. Configuration
Link kopieren

Configure this solver phase: 

  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap
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 Allocate Entity From Queue.

9.3. First Fit Decreasing
Link kopieren

9.3.1. Algorithm Description
Link kopieren

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.

firstFitDecreasingNQueens04
View larger image
firstFitDecreasingNQueens04
Note

One would expect that this algorithm has better results than First Fit. That’s usually the case, but not always.

9.3.2. Configuration
Link kopieren

Configure this solver phase: 

  <constructionHeuristic>
    <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap
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 Allocate Entity From Queue.

9.4. Weakest Fit
Link kopieren

9.4.1. Algorithm Description
Link kopieren

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

Do not presume that this algorithm has better results than First Fit. That’s often not the case.

9.4.2. Configuration
Link kopieren

Configure this solver phase: 

  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_FIT</constructionHeuristicType>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap
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 Allocate Entity From Queue.

9.5. Weakest Fit Decreasing
Link kopieren

9.5.1. Algorithm Description
Link kopieren

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 planning entity difficulty comparison and 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.

9.5.2. Configuration
Link kopieren

Configure this solver phase: 

  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap
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 Allocate Entity From Queue.

9.6. Strongest Fit
Link kopieren

9.6.1. Algorithm Description
Link kopieren

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

9.6.2. Configuration
Link kopieren

Configure this solver phase: 

  <constructionHeuristic>
    <constructionHeuristicType>STRONGEST_FIT</constructionHeuristicType>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap
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 Allocate Entity From Queue.

9.7. Strongest Fit Decreasing
Link kopieren

9.7.1. Algorithm Description
Link kopieren

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 planning entity difficulty comparison and 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.

9.7.2. Configuration
Link kopieren

Configure this solver phase: 

  <constructionHeuristic>
    <constructionHeuristicType>STRONGEST_FIT_DECREASING</constructionHeuristicType>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap
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 Allocate Entity From Queue.

9.8. Allocate Entity From Queue
Link kopieren

9.8.1. Algorithm Description
Link kopieren

Allocate Entity From Queue is a versatile, generic form of First Fit, First Fit Decreasing, Weakest Fit and Weakest Fit Decreasing. It works like this:

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

9.8.2. Configuration
Link kopieren

Simple configuration: 

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_ENTITY_FROM_QUEUE</constructionHeuristicType>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap

Verbose simple configuration: 

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_ENTITY_FROM_QUEUE</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap

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 planning entity difficulty comparison.
  • DECREASING_DIFFICULTY_IF_AVAILABLE (default): If the model supports planning entity difficulty comparison, behave like DECREASING_DIFFICULTY, else like NONE.
  • NONE: Initialize the planning entities in original order.

The valueSorterManner options are:

Advanced detailed configuration. For example, a Weakest Fit Decreasing configuration for a single entity class with a single variable: 

  <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>
Copy to Clipboard Toggle word wrap

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.

9.8.3. Multiple Variables
Link kopieren

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>
Copy to Clipboard Toggle word wrap
Warning

With 3 variables of 1000 values each, a Cartesian product selects 1 000 000 000 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>
Copy to Clipboard Toggle word wrap
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>
Copy to Clipboard Toggle word wrap

9.8.4. Multiple Entity Classes
Link kopieren

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>
Copy to Clipboard Toggle word wrap

9.8.5. Pick Early Type
Link kopieren

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 InitializingScoreTrend is not ONLY_DOWN. 

      <constructionHeuristic>
    ...
    <forager>
      <pickEarlyType>NEVER</pickEarlyType>
    </forager>
  </constructionHeuristic>
    Copy to Clipboard Toggle word wrap

  • 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>
    Copy to Clipboard Toggle word wrap
    Note

    If there are only negative constraints, but the InitializingScoreTrend is strictly not ONLY_DOWN, it can sometimes make sense to apply FIRST_NON_DETERIORATING_SCORE. Use the 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. 

      <constructionHeuristic>
    ...
    <forager>
      <pickEarlyType>FIRST_FEASIBLE_SCORE</pickEarlyType>
    </forager>
  </constructionHeuristic>
    Copy to Clipboard Toggle word wrap

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

      <constructionHeuristic>
    ...
    <forager>
      <pickEarlyType>FIRST_FEASIBLE_SCORE_OR_NON_DETERIORATING_HARD</pickEarlyType>
    </forager>
  </constructionHeuristic>
    Copy to Clipboard Toggle word wrap

9.9. Allocate To Value From Queue
Link kopieren

9.9.1. Algorithm Description
Link kopieren

Allocate To Value From Queue works like this:

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

9.9.2. Configuration
Link kopieren

Simple configuration: 

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_TO_VALUE_FROM_QUEUE</constructionHeuristicType>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap

Verbose simple configuration: 

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_TO_VALUE_FROM_QUEUE</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap

Advanced detailed configuration. For example, a configuration for a single entity class with a single variable: 

  <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>
Copy to Clipboard Toggle word wrap

9.10. Cheapest Insertion
Link kopieren

9.10.1. Algorithm Description
Link kopieren

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.

cheapestInsertionNQueens04
View larger image
cheapestInsertionNQueens04
Note

Cheapest Insertion scales considerably worse than First Fit, etc.

9.10.2. Configuration
Link kopieren

Simplest configuration of Cheapest Insertion: 

  <constructionHeuristic>
    <constructionHeuristicType>CHEAPEST_INSERTION</constructionHeuristicType>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap
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 Allocate from pool.

9.11. Regret Insertion
Link kopieren

9.11.1. Algorithm Description
Link kopieren

The Regret Insertion algorithm behaves like the Cheapest Insertion algorithm. It also cycles through all the planning values for all the planning entities, initializing 1 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.

9.11.2. Configuration
Link kopieren

This algorithm has not been implemented yet.

9.12. Allocate From Pool
Link kopieren

9.12.1. Algorithm Description
Link kopieren

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

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

9.12.2. Configuration
Link kopieren

Simple configuration: 

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_FROM_POOL</constructionHeuristicType>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap

Verbose simple configuration: 

  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_FROM_POOL</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>
Copy to Clipboard Toggle word wrap

The entitySorterManner and valueSorterManner options are described in Allocate Entity From Queue.

Advanced detailed configuration. For example, a Cheapest Insertion configuration for a single entity class with a single variable: 

  <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>
Copy to Clipboard Toggle word wrap

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 sorted selection. Other Selector customization (such as filtering and limiting) is supported too.

Nach oben
Red Hat logoGithubredditYoutubeTwitter

Lernen

Testen, kaufen und verkaufen

Communitys

Über Red Hat Dokumentation

Wir helfen Red Hat Benutzern, mit unseren Produkten und Diensten innovativ zu sein und ihre Ziele zu erreichen – mit Inhalten, denen sie vertrauen können. Entdecken Sie unsere neuesten Updates.

Mehr Inklusion in Open Source

Red Hat hat sich verpflichtet, problematische Sprache in unserem Code, unserer Dokumentation und unseren Web-Eigenschaften zu ersetzen. Weitere Einzelheiten finden Sie in Red Hat Blog.

Über Red Hat

Wir liefern gehärtete Lösungen, die es Unternehmen leichter machen, plattform- und umgebungsübergreifend zu arbeiten, vom zentralen Rechenzentrum bis zum Netzwerkrand.

Theme

© 2025 Red Hat