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

Tabu Search renaissance

XMLWordPrintable

    • Icon: Feature Request Feature Request
    • Resolution: Unresolved
    • Icon: Critical Critical
    • None
    • 6.2.0.CR2
    • optaplanner-core

      1) Instead of distincting every Move's entity/value collection in Move.getPlanningEntities/Values(),
      do it only once, in AbstractTabuAcceptor.
      So remove the HashSet stuff in CompositeMove (= unneeded performance loss).

      2) EntityTabu: If we pick a step moving an entity for variable alpha,
      then we should tabu that entity for variable alpha,
      but NOT for variable beta.
      VariableTabu: If we pick a step moving an entity for variable alpha to a value,
      then we should tabu that value for variable alpha,
      but NOT for variable beta.
      Similar for movetabu, etc

      3) If everything gets tabu'ed, then Tabu Search gets stuck.
      https://issues.jboss.org/browse/PLANNER-237
      https://issues.jboss.org/browse/PLANNER-41
      Idea's:
      A) In the tabu list, release the oldest steps until at least 1 entity/value/... is no longer tabu.
      Note: a step is released all together, so multiple might be released together
      EntityTabu: the number of entities is known and the tabu list is distinct 1), so no problem.
      ValueTabu: problems with entity independent value ranges
      B) If it gets stuck (requires flatline detection), reheat (similar to Late Acceptance, SA, ...)
      by reducing the tabu list size (and increase it back afterwards).
      Reheating will probably require configuration... and it feels like a hack.

      4) Tabu ratio does not take into account that multiple entities/values can be tabu'ed per step.
      A tabu ratio of 0.2+ with moves that contain 5+ entities, can still tabu everything.
      A tabu ratio of 0.5+ with moves that contain swap moves (2 entities), can still tabu everything.

      5) custom tabu properties, as requested by customer

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

                Created:
                Updated: