JBoss.orgCommunity Documentation

Chapter 9. Construction heuristics

9.1. Overview
9.2. First Fit
9.2.1. Algorithm description
9.2.2. Configuration
9.3. First Fit Decreasing
9.3.1. Algorithm description
9.3.2. Configuration
9.4. Weakest Fit
9.4.1. Algorithm description
9.4.2. Configuration
9.5. Weakest Fit Decreasing
9.5.1. Algorithm description
9.5.2. Configuration
9.6. Allocate Entity From Queue
9.6.1. Algorithm description
9.6.2. Configuration
9.6.3. Multiple variables
9.6.4. Multiple entity classes
9.6.5. Pick early type
9.7. Allocate To Value From Queue
9.7.1. Algorithm description
9.7.2. Configuration
9.8. Cheapest Insertion
9.8.1. Algorithm description
9.8.2. Configuration
9.9. Regret Insertion
9.9.1. Algorithm description
9.9.2. Configuration
9.10. Allocate From Pool
9.10.1. Algorithm description
9.10.2. Configuration

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.

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 Allocate Entity From Queue.

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 Allocate Entity From Queue.

Configure this solver phase:


  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_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 Allocate Entity From Queue.

Configure this solver phase:


  <constructionHeuristic>
    <constructionHeuristicType>WEAKEST_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 Allocate Entity From Queue.

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.

Simple configuration:


  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_ENTITY_FROM_QUEUE</constructionHeuristicType>
  </constructionHeuristic>

Verbose simple configuration:


  <constructionHeuristic>
    <constructionHeuristicType>ALLOCATE_ENTITY_FROM_QUEUE</constructionHeuristicType>
    <entitySorterManner>DECREASING_DIFFICULTY_IF_AVAILABLE</entitySorterManner>
    <valueSorterManner>INCREASING_STRENGTH_IF_AVAILABLE</valueSorterManner>
  </constructionHeuristic>

The entitySorterManner options are:

The valueSorterManner options are:

Advanced detailed configuration. For example, a Best 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>

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:

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>

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

    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>

    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>

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 Allocate from pool.

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.