Construction Heuristics with multiple variables or multiple planning variables

by Geoffrey De Smet - December 11, 2013
Optimization Article

Lately, OptaPlanner users have started asking questions how to configure the construction heuristics for multiple variables or multiple planning entities. I’ve just enriched the docs to explain that better. Until those are published, I ‘ve copied the relevant section here.

Note that this is for advanced users, for normal users the simple configuration should suffice.

8.6. Advanced Greedy Fit

8.6.1. Algorithm description

Advanced Greedy Fit is versatile, generic form of First Fit, First Fit Decreasing, Best Fit and Best Fit Decreasing.

8.6.2. Configuration

A Best Fit Decreasing configuration for a single entity class with a single variable (which is the verbose version of the simple constructionHeuristicType BEST_FIT_DECREASING configuration):

<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>
    <!–<forager>–>
      <!–<pickEarlyType>FIRST_NON_DETERIORATING_SCORE</pickEarlyType>–>
    <!–</forager>–>
</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) is supported too.

8.6.3. Multiple variables

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>

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:

8.6.4. Multiple entity classes

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>

KIE Community