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

57 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
  30. All construction firms are extraordinary (planners, developers, M&E and so forth) however there are promoting choices that each can use.הזזת ספרינקלרים

    ReplyDelete
  31. Quickly this site will indisputably be famous among all blogging people, because of its fastidious articles or reviews.
    Scott Lanzon Knoxville

    ReplyDelete
  32. You guys present there are performing an excellent job.
    Healthiest Lives

    ReplyDelete
  33. Whether somebody pursuit of his vital thing, hence he or she desires to be accessible that at length, hence that thing is maintained over here.
    Muscle Strain

    ReplyDelete
  34. I actually have some fans on a facebook page related to this stuff. I'll share your post with them and see what they have to say. I'm sure they'll love it though.
    Blackjack

    ReplyDelete
  35. Superb way of explaining, and great blog to get wonderful information.
    TABLE GAMES

    ReplyDelete
  36. It is truly a well-researched content.. ICF walls

    ReplyDelete
  37. I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. Air Conditioning Repair

    ReplyDelete
  38. nice post, keep up with this interesting work. It really is good to know that this topic is being covered also on this web site so cheers for taking time to discuss this! Georgetown crane rental

    ReplyDelete
  39. Your post is very helpful to get some effective tips to reduce weight properly. You have shared various nice photos of the same. I would like to thank you for sharing these tips. Surely I will try this at home. Keep updating more simple tips like this. property for sale in gozo

    ReplyDelete
  40. 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.
    10 yard dumpster company new york

    ReplyDelete
  41. Thankyou for sharing the data which is beneficial for me and others likewise to see. Washington DC Commercial Contractor

    ReplyDelete
  42. Hi I was searching for the blogs for many times, now I have reached at the right place. have a peek at these guys

    ReplyDelete
  43. Your articles and contents are encouraging. Petey Cruiser

    ReplyDelete
  44. This written piece gives fastidious understanding yet.
    click for more info

    ReplyDelete
  45. I was pinning away for such type of blogs, thanks for posting this for us.
    home security

    ReplyDelete
  46. This article is actually remarkable one it helps many new users that desire to read always the best stuff.
    Select My Shaver

    ReplyDelete
  47. I'm impressed, I must say. Very rarely do I come across a blog thats both informative and entertaining, and let me tell you, you ve hit the nail on the head. Your blog is important.. barn conversion London

    ReplyDelete
  48. Awesome work! That is quite appreciated. I hope you’ll get more success.
    20yarddumpstercompanynewyork

    ReplyDelete
  49. 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.
    visit

    ReplyDelete
  50. This is an incredible rousing article.I am basically satisfied with your great work.You put truly exceptionally accommodating data...  home inspectors fayetteville nc

    ReplyDelete
  51. I'm also visiting this site regularly, this web site is really nice and the users are genuinely sharing good thoughts.mu online

    ReplyDelete
  52. This post is very simple to read and appreciate without leaving any details out. Great work! creative garden edging ideas

    ReplyDelete
  53. Quickly this site will indisputably be famous among all blogging people, because of its fastidious articles or reviews.
    constructiondumpsterHoover

    ReplyDelete
  54. Nice post mate, keep up the great work, just shared this with my friendz vibro stone columns

    ReplyDelete
  55. Quickly this site will indisputably be famous among all blogging people, because of its fastidious articles or reviews.
    20 yard dumpster company atlanta

    ReplyDelete
  56. It’s really such nice information to get advantage from.
    carpenter benistar

    ReplyDelete