[rules-users] Found solution vs actual optimum [planner]

[Geoffrey De Smet]

Op 03-02-13 19:02, john poole schreef:
> Is there a way to describe how the solutions found in planner compare to the
> true optimum solutions?
Although you can configure a solver that does just <bruteForce/> (and in 
later versions more scalable algorithms such as branchAndBound),
it's unlikely that any of those algorithms will scale to a medium/large 
dataset with a realistic number of constraints - even if you'd give it 
years to run.

And - from my experience - the quality of a solution of a dataset of size n,
can predict nothing about the quality of a solution of a dataset of size 
2*n.
I've seen exact algorithms that work perfectly on 1 dataset, totally 
miss it on a slightly bigger dataset.

Because this is a re-occuring question, I 've added a section in the 
manual: "Does Planner find the optimal solution?"
https://github.com/droolsjbpm/drools-planner/commit/9ae1b72020b9b3be4432188e947333ad8ffa99a3

>
> In  chapter 6
> <http://docs.jboss.org/drools/release/5.5.0.Final/drools-planner-docs/html/optimizationAlgorithms.html>
> of the docs it rates the methods used as "4/5" for finding an optimal
> solution. Does that mean:  a) it will do a good job of finding the optimum,
> or b) that the solution it finds will be close to an optimum?
Depends on the size of the problem, size of the constraints and the 
amount of time given.
Metaheuristics do not recognize the optimal solution as optimal when 
they find it.
But realistic competitions prove that usually do the best job. (see new 
section Examples Overview in manual)

To get an idea how "good" the result is, use the benchmarker and enable 
the Best score over time statistic
http://docs.jboss.org/drools/release/5.5.0.Final/drools-planner-docs/html_single/index.html#d0e7101
If the line flatlines, it's good.
>
>
>
> --
> View this message in context: http://drools.46999.n3.nabble.com/Found-solution-vs-actual-optimum-tp4022027.html
> Sent from the Drools: User forum mailing list archive at Nabble.com.
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>