Wednesday, December 11, 2013

Construction Heuristics with multiple variables or multiple planning variables

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:


  <constructionHeuristic>
    <queuedEntityPlacer>
      ...
      <cartesianProductMoveSelector>
        <changeMoveSelector>...</changeMoveSelector>
        <changeMoveSelector>...</changeMoveSelector>
      </cartesianProductMoveSelector>
      <changeMoveSelector>...</changeMoveSelector>
    </queuedEntityPlacer>
    ...
  </constructionHeuristic>

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>

Share/Bookmark

29 comments:

  1. Your blog site is so superb. How fortunate to see everything you have created. Hope you proceed to do the job tough. I wish you possess a good health and wellbeing.

    ReplyDelete
  2. This written piece gives fastidious understanding yet. It’s amazing in support of me to truly have a web site that is valuable meant for my knowledge

    ReplyDelete
  3. Factors that pick which kind of evaluate your job may be given depend on use or occupancy in the extended distance, intricacy of proposed operate, and dollar valuation of your suggested production.Building Permit Expediter in San Francisco CA

    ReplyDelete
  4. It's not my very first time to visit this blog; I’m visiting this daily and acquire superb info from here day by day.
    england phone number format

    ReplyDelete
  5. Hi I was searching for the blogs for many times, now I have reached at the right place.
    best indian songs

    ReplyDelete
  6. Building construction is a process of adding small or big structures to land or real property. flat roof repair

    ReplyDelete
  7. Quickly this site will indisputably be famous among all blogging people, because of its fastidious articles or reviews.
    UL listed security cameras

    ReplyDelete
  8. Just saying thanks wouldn’t just be enough, for the fantastic fluency in your writing.
    self storage security

    ReplyDelete
  9. This text may be value everyone’s attention. How will I learn more?
    security camera mounts

    ReplyDelete
  10. Superb way of explaining, and great blog to get wonderful information.
    self storage security cameras

    ReplyDelete
  11. Your articles make whole sense of every topic.
    car wash camera systems

    ReplyDelete
  12. When you use a genuine service, you will be able to provide instructions, share materials and choose the formatting style. בניית בתים פרטיים

    ReplyDelete
  13. Every week-end I used to pay a fast visit this site, because I’d like enjoyment, because this web site conations certainly fussy material.
    http://www.telephonecodes.org

    ReplyDelete
  14. Every week-end I used to pay a fast visit this site, because I’d like enjoyment, because this web site conations certainly fussy material.
    telephone

    ReplyDelete
  15. Hello, this is fastidious post I actually loved reading this.
    locksmith near me

    ReplyDelete
  16. I constantly emailed this site post page to all my friends, because if prefer to read it then my all friends will too.
    telephonecodes

    ReplyDelete
  17. This is really an excellent blog as well as its content.
    telephonecodes.org

    ReplyDelete
  18. Note: This article records the fundamental synthetic compounds required for pool maintenance. visit this hyperlink

    ReplyDelete
  19. Quickly this site will indisputably be famous among all blogging people, because of its fastidious articles or reviews.
    www.mediaonlines.com

    ReplyDelete
  20. You have performed a great job on this article. It’s very precise and highly qualitative. You have even managed to make it readable and easy to read. You have some real writing talent. Thank you so much. Fencing

    ReplyDelete
  21. Wow. I am definitely going share this with a few of my friends. Very cool information.
    Scott Lanzon Knoxville

    ReplyDelete
  22. I constantly emailed this site post page to all my friends, because if prefer to read it then my all friends will too.
    Scott Lanzon Knoxville

    ReplyDelete
  23. Quickly this site will indisputably be famous among all blogging people, because of its fastidious articles or reviews.
    recycled plastic furniture

    ReplyDelete
  24. The quality of your articles and contents is great.
    crp plastics

    ReplyDelete
  25. This is extremely fascinating substance! I have completely delighted in perusing your focuses and have reached the conclusion that you are right about a hefty portion of them. You are extraordinary.  HVAC

    ReplyDelete
  26. I agree. You have made the nice blogs with the great info in the contents.
    recycled plastic furniture

    ReplyDelete
  27. Waooow!!! Magnificent blogs, this is what I wanted to search. Thanks buddy
    telephone codes

    ReplyDelete
  28. I love this blog because it is user friendly with appreciative information.
    http://www.telephonecodes.org

    ReplyDelete
  29. An interesting dialogue is price comment. I feel that it is best to write more on this matter, it may not be a taboo topic however usually individuals are not enough to talk on such topics. To the next. Cheers. Gutter contractors

    ReplyDelete