Quantcast

Finding Multiple Solutions using Drools Planner

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Finding Multiple Solutions using Drools Planner

SteveR685

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
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Finding Multiple Solutions using Drools Planner

ge0ffrey
Administrator
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
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users

_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Finding Multiple Solutions using Drools Planner

ge0ffrey
Administrator
I created this issue:
https://jira.jboss.org/browse/JBRULES-2703
AllBestSolutionsRecaller: Drools Planner should support returning all
the solutions with the same best score found during solving, not just
the first

With kind regards,
Geoffrey De Smet

Op 19-09-10 10:08, Geoffrey De Smet schreef:

> 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
>> [hidden email]
>> https://lists.jboss.org/mailman/listinfo/rules-users
>
> _______________________________________________
> rules-users mailing list
> [hidden email]
> https://lists.jboss.org/mailman/listinfo/rules-users
>

_______________________________________________
rules-users mailing list
[hidden email]
https://lists.jboss.org/mailman/listinfo/rules-users
Loading...