[rules-users] Finding Multiple Solutions using Drools Planner

[Geoffrey De Smet]

Hi Steve,

 > I need is to find all of the ideal solutions to my planning problem.

This is impossible with a metaheuristic algorithm, such as tabu search 
and simulated annealing. So this is currently impossible with Drools 
Planner.

I have a couple issues to implement exact algorithms on top of the rule 
engine based score calculation in Drools Planner:
- brute force
- branch and bound
Even though branch and bound is a lot faster and more scalable than 
brute force, it's still enormously slower and less scalable than 
metaheuristics.
For most real world datasets, exact algorithms are mostly useless due to 
the sheer size of the possible solution set. They have bigO notations 
such as n^n.


What you can do of course, is extend the BestSolutionRecaller to recall 
the first 10 best solution (someone else has done this too, but didn't 
provide a patch, but feel free to make an issue).
Combine that with a good max timemillisspend or unimproved step count.

With kind regards,
Geoffrey De Smet

Op 18-09-10 22:03, Steve Ronderos schreef:
>
> Hello Drools Users,
>
> I've been investigating Drools Planner for a few weeks and can't figure
> out how to accomplish a crucial requirement.
>
> In my application I need to have Planner return multiple solutions for
> one planning problem. More specifically I need is to find all of the
> ideal solutions to my planning problem. My problem is similar to the
> n-queens problem in that there exist ideal solutions. It is however
> somewhat simpler because the number of ideal solutions is fairly small
> (maybe a max of 10 or so).
>
> I've looked through the mailing list archives for similar requests and
> the best I could find was:
>
> http://drools-java-rules-engine.46999.n3.nabble.com/the-n-best-solutions-on-a-very-simple-test-case-td60618.html
>
> I took the advice of the poster in that thread and extended
> BestSolutionRecaller. I'm running into some problems getting Planner to
> continue after an optimal solution is found.
>
> My question is this. Is extending the BestSolutionRecaller the best way
> to achieve my goal? Or do you think it would be simpler to do this
> another way? Perhaps running Planner multiple times with already
> discovered solutions provided as input.
>
> Any advice would be appreciated.
>
> Thanks,
> Steve
>
>
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users