Uploaded image for project: 'OptaPlanner'
  1. OptaPlanner
  2. PLANNER-485

Memory friendly nearby selection by caching only the n nearest entities (optionally adhering to some filter)

    XMLWordPrintable

Details

    • Feature Request
    • Resolution: Done
    • Major
    • 6.4.0.Beta1
    • 6.3.0.Final
    • optaplanner-core
    • None
    • NEW
    • NEW

    Description

      Up to a few days ago I was convinced that nearby selection needs to cache all distance combinations.
      But as that would make solving 100k VRP impossible on my machine (100k * 100k uses 38GB RAM), I've been looking at alternatives:

      • Simply limited nearby till the n nearest isn't possible for CH's (as those 100 nearest might not be initialized).
      • However, for CH's we can limit nearby to the n nearest initialized entities.
        This splits up the nearby implementation, based on being used in LS or CH.
        I 'll also allow a "shared" way, for small cases, where the entire nearby distance matrix can be cached.

      Attachments

        1. Selection_085.png
          403 kB
          Geoffrey De Smet

        Issue Links

          is duplicated by

          Bug - A problem that impairs or prevents the functions of the product. PLANNER-362 Nearby Selection on VRP with 10k+ locations grabs a lot of memory for Local Search

          • Critical - To be worked on immediately following BLOCKER issues.
          • Resolved
          is related to

          Feature Request - Feature requests from customers and/or users PLANNER-491 Partitioned Search

          • Blocker - To be worked above all other priorities. This term is chosen when the severity of the issue is very high, has no workaround, or the effort for the change is comparatively low. Issues that may be very publicly visible and could generate significant media attention may also drive a higher priority.
          • Resolved

          Feature Request - Feature requests from customers and/or users PLANNER-499 Use k-d tree for VRP: a more efficient datastructure to calculate nearby distances

          • Major - To be worked after higher priority work items are addressed. When the severity is high and the effort to change it is low to moderate, this term is chosen. Issues in this category likely have an existing workaround but implementation or execution may be non-trivial.
          • Open
          relates to

          Enhancement - An enhancement to or refactoring of existing functionality that is not configurable by an end user (typically a change made by an internal team that affects users) PLANNER-495 Multiple nearby selectors should share their distance matrix

          • Major - To be worked after higher priority work items are addressed. When the severity is high and the effort to change it is low to moderate, this term is chosen. Issues in this category likely have an existing workaround but implementation or execution may be non-trivial.
          • Resolved

          Activity

            People

              gdesmet@redhat.com Geoffrey De Smet (Inactive)
              gdesmet@redhat.com Geoffrey De Smet (Inactive)
              Votes:
              0 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: