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

90 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. I can see that you a an expert at ur field! I am launching a website soon, and your information will be very useful for me.. Thanks for all your help and wishing you all the success in your business. cctv camera installation

    ReplyDelete
  56. I admit, I have not been on this web page in a long time... however it was another joy to see It is such an important topic and ignored by so many, even professionals. I thank you to help making people more aware of possible issues. Industrial Concrete Coating

    ReplyDelete
  57. 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.
    fetish girl sex

    ReplyDelete
  58. Thanks meant for sharing this type of satisfying opinion, written piece is fastidious, that’s why I’ve read it completely.
    more info here

    ReplyDelete
  59. 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
    big boobs girls sex

    ReplyDelete
  60. 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.
    porn hair sex

    ReplyDelete
  61. The quality of your blogs and conjointly the articles and price appreciating.
    anal sex and cumshot

    ReplyDelete
  62. I hope you will share such type of impressive contents again with us so that we can utilize it and get more advantage.
    top home security systems

    ReplyDelete
  63. I wanna thanks to a great extent for providing such informative and qualitative material therefore often.
    anal sex with hot girl

    ReplyDelete
  64. If somebody wants expert take on the main topic of blogging next I advise him/her to go to this site, continue the fussy job.
    chausa mango online

    ReplyDelete
  65. This is one of the most important blogs that I have seen, keep it up!
    hero tower hyderabad

    ReplyDelete
  66. Great blog. Having a patio and patio cover is essential for the San Antonio homeowner. Residents need a way to relax outdoors and share time with friends and family. For the best Custom deck builders you have to visit on rivercitydeckandpatio.com.

    ReplyDelete
  67. Hi to everybody, here everyone is sharing such knowledge, so it’s fastidious to see this site, and I used to visit this blog daily.
    anal sex with hot girl

    ReplyDelete
  68. Though i have learned about it but after read your articles, i just realized the amount of knowledge that i missed. Thank for your shared.Jav Streaming

    ReplyDelete
  69. Really suprised with these things, i have thought it would be different. Thanks for useful informationJav Hot

    ReplyDelete
  70. Thank you and thank for your shared, i will introduce to my friend to visit your website more oftenJav Free

    ReplyDelete
  71. It is extremely nice to see the greatest details presented in an easy and understanding manner.
    guy anal fucking

    ReplyDelete
  72. Your contents are too straightforward to browse and easy to understand.
    erotica sex

    ReplyDelete
  73. Easily, the article is actually the best topic on this registry related issue. I fit in with your conclusions and will eagerly look forward to your next updates. demolition

    ReplyDelete
  74. Hey nice post man! Thanks for incredible info.
    big boobs girls sex

    ReplyDelete
  75. Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. STEBRO MOLD

    ReplyDelete
  76. Great post! We will be linking to this particularly great article on our website. Keep up the great writing. gogoanime

    ReplyDelete
  77. Wow, What a Excellent post. I really found this to much informatics. It is what i was searching for.I would like to suggest you that please keep sharing such type of info.Thanks roofing companies Indianapolis

    ReplyDelete
  78. The complete blogs are really inconceivable and definitely everyone will share this information
    Free Live Adult Webcam Chat Rooms

    ReplyDelete
  79. Well, one factor that is behind the trend is the growing awareness about the suitability of sandstone as a paving solution. Paving Colorado Springs CO

    ReplyDelete
  80. Construction projects are major endeavors that involve a lot of equipment - those heavy machinery used to transport and move large materials, and a lot people - the construction workers. The larger the construction project, the greater the number of equipment and people is needed. roofing company

    ReplyDelete
  81. Security Hand Gloves are utilized to ensure hands. There are different kinds of hand gloves produced using various materials utilized for various purposes. Disposal bin rental Alliston

    ReplyDelete
  82. Very informative post! There is a lot of information here that can help any business get started with a successful social networking campaign. מערכות גילוי אש אשדוד

    ReplyDelete
  83. I have learnt various good stuff right here, and I’m sure everyone will get advantage of it.
    Live Sex Chat

    ReplyDelete
  84. Your website is for sure worth bookmarking.
    Live Sex Chat

    ReplyDelete
  85. These are the great blogs; I assure you that I really enjoyed a lot in reading.
    Live Cam

    ReplyDelete
  86. I am hoping the same best effort from you in the future as well. In fact your creative writing skills has inspired me. Préstamos particulares

    ReplyDelete