Sunday, December 25, 2011

Less boilerplate in Planner: Generic MoveFactory

The recently released Drools Planner 5.4.0.Beta1 includes 2 Generic MoveFactories. That means it's no longer required to implement  a MoveFactory and Move to use a local search optimization algorithm such as Tabu Search or Simulated Annealing.

For example, the MachineReassignment example configures Tabu Search like this:

  <localSearch>
    <selector>
      <selector>
        <moveFactoryClass>org.drools.planner.core.move.generic.GenericChangeMoveFactory</moveFactoryClass>
      </selector>
      <selector>
        <moveFactoryClass>org.drools.planner.core.move.generic.GenericSwapMoveFactory</moveFactoryClass>
      </selector>
    </selector>
    <acceptor>
      <propertyTabuSize>5</propertyTabuSize>
    </acceptor>
    <forager>
      <minimalAcceptedSelection>1000</minimalAcceptedSelection>
    </forager>
  </localSearch>

Notice that there is no MachineReassignment specific code in there whatsoever. But if I wanted to, I could easily mix in a custom MoveFactory implementation too.

Planner comes with 2 generic move factories out of the box:
  • GenericChangeMoveFactory: A GenericChangeMove changes 1 planning variable of 1 planning entity to another planning value. For example: Given course C1 in room R1 and period P1, change its room to room R2.
  • GenericSwapMoveFactory: A GenericSwapMove swaps all the planning variables of 2 planning entities. For example: Given course C1 in room R1 and period P1 and Course C2 in room R2 and period P2, put course C1 in room R2 and period P2 and put course C2 in room R1 and period P1.
They are slightly slower than a custom implementation, but equally scalable.

6 comments:

  1. I also noticed in the source that there is a pillar swap move - any specific reason for why you're not mentioning it?

    ReplyDelete
  2. @triceo I forgot about the GenericSwapPillarMove, probably due too much xmas sleep deprivation. Nice catch, Lukas :)

    The GenericSwapPillarMove swaps a set of entities with the same planning value for 1 variable with another set of entities with the same planning value for the same variable. For example Given C1, C2 and C3 in room R1 and C4 in room R4, it puts C1, C2 and C3 in room R4 and C4 in room R1.

    I tried mixing it in on the MachineReassignment problem, but it didn't work better (at least the few experiments that I ran). However, I am convinced that for other use cases it will work better though. So it's definitely worth to give it a quick spin in any use cases with the Benchmarker.

    ReplyDelete
  3. we are using planner version 5.3 on solaris 10 T6340 and making 4 and 5 gb jvm with following result

    Ok u failed it used all 4 gb of ,memory and dired at 4:10ish

    1 [main] INFO gov.ssa.asa.main.EngineMain - [Starting automated hearing scheduler]
    60 [main] INFO gov.ssa.asa.main.Context - Initializing Application Context...
    31138 [main] INFO gov.ssa.asa.service.impl.EngineServiceImpl - [starting runengine()]
    35749 [main] INFO gov.ssa.asa.service.impl.EngineServiceImpl - [got queue count]
    36068 [main] INFO gov.ssa.asa.service.impl.EngineServiceImpl - [about to configureplanner]
    55436 [main] INFO org.drools.planner.core.solver.BasicPlumbingTermination - Terminating solver early.
    55437 [main] INFO gov.ssa.asa.service.impl.EngineServiceImpl - [done configuring planner]
    55528 [main] INFO gov.ssa.asa.planner.initializer.PlannerInputInitializer - [getting cfg rules()] Tue Jan 31 13:38:15 EST 2012
    55572 [main] INFO gov.ssa.asa.planner.initializer.PlannerInputInitializer - [getting aljs] Tue Jan 31 13:38:15 EST 2012
    109890 [main] INFO gov.ssa.asa.planner.initializer.PlannerInputInitializer - [getting reps] Tue Jan 31 13:39:10 EST 2012
    109893 [main] INFO gov.ssa.asa.planner.initializer.PlannerInputInitializer - [getting rep facts] Tue Jan 31 13:39:10 EST 2012
    334443 [main] INFO gov.ssa.asa.planner.initializer.RepInitializer - [before engm rep loop] Tue Jan 31 13:42:54 EST 2012
    364814 [main] INFO gov.ssa.asa.planner.initializer.RepInitializer - [after engm rep loop] Tue Jan 31 13:43:24 EST 2012
    364814 [main] INFO gov.ssa.asa.planner.initializer.PlannerInputInitializer - [setting rep facts facts] Tue Jan 31 13:43:24 EST 2012
    364814 [main] INFO gov.ssa.asa.planner.initializer.PlannerInputInitializer - [setting rep avail] Tue Jan 31 13:43:24 EST 2012
    364815 [main] INFO gov.ssa.asa.planner.initializer.PlannerInputInitializer - [getting sites] Tue Jan 31 13:43:24 EST 2012
    385946 [main] INFO gov.ssa.asa.planner.initializer.PlannerInputInitializer - [getting experts] Tue Jan 31 13:43:46 EST 2012
    671556 [main] INFO gov.ssa.asa.planner.initializer.PlannerInputInitializer - [init planner solution] Tue Jan 31 13:48:31 EST 2012
    994194 [main] INFO gov.ssa.asa.planner.initializer.PlannerInputInitializer - 5976 cases were picked for scheduling.
    996561 [main] INFO gov.ssa.asa.service.impl.EngineServiceImpl - [The initializer took 941 seconds]
    Jan 31, 2012 2:00:07 PM ClientCommunicatorAdmin Checker-run
    WARNING: Failed to check the connection: java.net.SocketTimeoutException: Read timed out
    stephen.a.sandbank@ssa.gov

    ReplyDelete
    Replies
    1. Hi Stephan,

      You have a failure that worked before?
      That log seems to indicate that it's a network problem (java.net.SocketTimeoutException). I frequently run Planner off-line, so I don't immediately see how Planner can be responsible for it (but one never knows).

      Please provide more info (what change you made, what worked, what doesn't) and post it as a question to our user forum / mailing list, as they are better suited to solve individual problems then these blog comments.

      Delete
    2. @Stephan I think I just understood your question.

      If you mean it went OutOfMemory after that log, after the change when switching from your custom MoveFactory to these generic move factory's, then I am not surprised.
      There's a very big case at your organization (which I am more than happy to publish a blog article about if you want to write it :) that has 6 planning variables per planning entity (all other uses cases I've seen have 1 or 2 planning variables).
      The generic move factories currently generate all moves. So if you have a 3000 planning entities and a 1000 planning values per planning variable, then it generates 3000 * 1000 * 1000 * 1000 * 1000 * 1000 * 1000, which is more then 10^21 moves, which is impossible to load into a reasonable RAM.

      For now, keep using your custom MoveFactory. Here's the issue to improve planner generic move factories: https://issues.jboss.org/browse/JBRULES-3371

      Delete
    3. The memory issues for really big problems are fixed with the JIT selectors for 5.5.0.Beta1

      Delete