12:02 p.m.
Is there a way to describe how the solutions found in planner compare to the
true optimum solutions?
In chapter 6
<http://docs.jboss.org/drools/release/5.5.0.Final/drools-planner-docs/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?
--
View this message in context:
http://drools.46999.n3.nabble.com/Found-solution-vs-actual-optimum-tp4022...
Sent from the Drools: User forum mailing list archive at Nabble.com.
9:35 a.m.
New subject: Found solution vs actual optimum [planner]
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/9ae1b72020b9b3be44321...
In chapter 6
<http://docs.jboss.org/drools/release/5.5.0.Final/drools-planner-docs/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...
If the line flatlines, it's good.
--
View this message in context:
http://drools.46999.n3.nabble.com/Found-solution-vs-actual-optimum-tp4022...
Sent from the Drools: User forum mailing list archive at Nabble.com.
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
9:25 p.m.
New subject: Found solution vs actual optimum [planner]
Thanks. If the "Best score over time" line doesn't flatline, does that mean
it needs more time or that the configuration isn't ever going to produce a
good solution?
--
View this message in context:
http://drools.46999.n3.nabble.com/Found-solution-vs-actual-optimum-tp4022...
Sent from the Drools: User forum mailing list archive at Nabble.com.
2:17 a.m.
New subject: Found solution vs actual optimum [planner]
Op 05-02-13 04:25, john poole schreef:
Thanks. If the "Best score over time" line doesn't
flatline, does that mean
it needs more time or that the configuration isn't ever going to produce a
good solution?
Define "good" solution :)
- Close to optimal: impossible to know the optimal for most realistic
problems (and extrapolating quality from easier, smaller problems is broken)
- Better than other algorithms: that's why planner has the benchmarker.
My advice is to use the benchmarker and configure different algo's (see
the examples *SolverBenchmark.xml) and a distinct set of datasets.
Then a bad solution should stick out like a sore thumb in the benchmark
report.
--
View this message in context:
http://drools.46999.n3.nabble.com/Found-solution-vs-actual-optimum-tp4022...
Sent from the Drools: User forum mailing list archive at Nabble.com.
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
10:24 a.m.
New subject: Found solution vs actual optimum [planner]
Better than other algorithms is what I'm after.
The output from the sample data sets is excellent. So easy to scan through
and understand all the results immediately. Anyone that hasn't used it
should give it a try.
I'm running the benchmarker on my inputs and rules now. I'm just using the
Nurse Rostering example with different inputs and a few more rules, but it's
been taking me around 6 hours to get the score I expect.
I'm also using planner to try and show cases where an acceptable solution
can't be found, and I'll be more confident knowing I'm tried all the
methods.
Thanks.
--
View this message in context:
http://drools.46999.n3.nabble.com/Found-solution-vs-actual-optimum-tp4022...
Sent from the Drools: User forum mailing list archive at Nabble.com.
11:05 a.m.
New subject: Found solution vs actual optimum [planner]
Op 05-02-13 17:24, john poole schreef:
Better than other algorithms is what I'm after.
The output from the sample data sets is excellent. So easy to scan through
and understand all the results immediately. Anyone that hasn't used it
should give it a try.
Thanks for the kind words :)
I'm running the benchmarker on my inputs and rules now. I'm just using the
Nurse Rostering example with different inputs and a few more rules, but it's
been taking me around 6 hours to get the score I expect.
That's long indeed.
Could be the difficulty of your dataset. Or could be
the performance of your score rules.
What's your average calculate count per second (see log or benchmarker
report).
It should be 2 000 - 10 000 at least.
I'm also using planner to try and show cases where an acceptable solution
can't be found, and I'll be more confident knowing I'm tried all the
methods.
Thanks.
--
View this message in context:
http://drools.46999.n3.nabble.com/Found-solution-vs-actual-optimum-tp4022...
Sent from the Drools: User forum mailing list archive at Nabble.com.
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
4:27 p.m.
New subject: Found solution vs actual optimum [planner]
I ran the benchmarker and it's showing that I should be using simulated
annealing. So that's useful info.
I'm only getting 525-650 for the average calculate count per second though.
(I didn't realize I could get it without the benchmarker until reading the
docs again)
I'm going through "Score calculation performance tricks" now, but I
didn't
see anything about the hardware used for the expected "1000" value. If my
older laptop is sort of crappy( a Pentium(R)2.2GHz), that would explain the
difference, correct?
--
View this message in context:
http://drools.46999.n3.nabble.com/Found-solution-vs-actual-optimum-tp4022...
Sent from the Drools: User forum mailing list archive at Nabble.com.
4:15 a.m.
New subject: Found solution vs actual optimum [planner]
Op 08-02-13 23:27, john poole schreef:
I ran the benchmarker and it's showing that I should be using
simulated
annealing. So that's useful info.
I'm only getting 525-650 for the average calculate count per second though.
(I didn't realize I could get it without the benchmarker until reading the
docs again)
I'm going through "Score calculation performance tricks" now, but I
didn't
see anything about the hardware used for the expected "1000" value. If my
older laptop is sort of crappy( a Pentium(R)2.2GHz), that would explain the
difference, correct?
It's still a sign to check if none of the score rules are
a bottleneck.
The way I do that, is to create a stepLimit benchmark (see docs howto)
and then comment out 1 rule at a time to see the impact of adding that rule.
--
View this message in context:
http://drools.46999.n3.nabble.com/Found-solution-vs-actual-optimum-tp4022...
Sent from the Drools: User forum mailing list archive at Nabble.com.
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
5:18 p.m.
New subject: Found solution vs actual optimum [planner]
I went through and ran some stepLimit benchmarks, commenting out single rules
at a time, or groups of rules that were dependent on each other. "average
calculate count per second" stayed fairly consistent at around 825 to 850,
except for the "consecutive working day" rules.( Which were already in the
drl file before I added mine, but do apply to the schedules I'm working on)
I commented out the group, then uncommented them in sequence.
Everything below a score is commented out:
1487(entire group commented out)
rule "insertEmployeeConsecutiveAssignmentStart"
1308
rule "insertEmployeeConsecutiveAssignmentEnd"
1244
rule "insertEmployeeWorkSequence"
1054
rule "minimumConsecutiveWorkingDays"
1081
rule "maximumConsecutiveWorkingDays"
988
rule "insertEmployeeFreeSequence"
994
rule "insertFirstEmployeeFreeSequence"
902
rule "insertLastEmployeeFreeSequence"
854
rule "insertEntireEmployeeFreeSequence"
938
rule "minimumConsecutiveFreeDays"
895
rule "maximumConsecutiveFreeDays"
851 (nothing commented out)
--
View this message in context:
http://drools.46999.n3.nabble.com/Found-solution-vs-actual-optimum-tp4022...
Sent from the Drools: User forum mailing list archive at Nabble.com.
2:28 a.m.
New subject: Found solution vs actual optimum [planner]
Looks normal, no big bottleneck apparently.
It's probably time to blame the hardware :)
http://www.cpubenchmark.net/high_end_cpus.html
Mine's around 4k there.
Keep in mind that: better hardware will give you the same solution twice
as fast,
but not necessarily a much better solution in the same time (which
better algorithms do tend to do).
Op 12-02-13 00:18, john poole schreef:
I went through and ran some stepLimit benchmarks, commenting out
single rules
at a time, or groups of rules that were dependent on each other. "average
calculate count per second" stayed fairly consistent at around 825 to 850,
except for the "consecutive working day" rules.( Which were already in the
drl file before I added mine, but do apply to the schedules I'm working on)
I commented out the group, then uncommented them in sequence.
Everything below a score is commented out:
1487(entire group commented out)
rule "insertEmployeeConsecutiveAssignmentStart"
1308
rule "insertEmployeeConsecutiveAssignmentEnd"
1244
rule "insertEmployeeWorkSequence"
1054
rule "minimumConsecutiveWorkingDays"
1081
rule "maximumConsecutiveWorkingDays"
988
rule "insertEmployeeFreeSequence"
994
rule "insertFirstEmployeeFreeSequence"
902
rule "insertLastEmployeeFreeSequence"
854
rule "insertEntireEmployeeFreeSequence"
938
rule "minimumConsecutiveFreeDays"
895
rule "maximumConsecutiveFreeDays"
851 (nothing commented out)
--
View this message in context:
http://drools.46999.n3.nabble.com/Found-solution-vs-actual-optimum-tp4022...
Sent from the Drools: User forum mailing list archive at Nabble.com.
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
4389
days inactive
4398
days old
9 comments
2 participants
participants (2)
-
Geoffrey De Smet -
john poole