This one took a bit more thinking. For the second problem, which we DO require that it be solved with a rulebase, we have an updated Ms. Manners (Miss Manners for this century) in which we have
12 tables with 12 settings (or seats)
144 guests who have 1, 2 or 3 hobbies randomly assigned from a selection of 5
Hobbies are Tennis, Golf, Motorcycles, Chess and Poker
24 are politicians,
12 Democrats
6 Democrats are female
12 Republicans
4 Republicans are female
24 doctors,
8 pediatricians
6 Pediatricians are female
8 surgeons
4 Surgeons are female
8 osteopaths
2 Osteopaths are females
24 socialites
18 socialites are female
24 sports stars
8 basketball stars
4 basketball stars are female
12 football stars
4 baseball stars
24 teachers
10 teachers are female
24 Programmers
8 Mac programmers
3 Mac programmers are female
8 Windows Programmers
6 Windows Programmers are female
8 COBOL Programmers
2 COBOL programmers are female
The objective is to put at each table
1 democrat
1 republican
2 doctors at each table but NOT two of the same kind
2 socialites at each table
2 sports stars at each table but NOT two of the same kind
2 teachers at each table
2 programmers at each table but NOT two of the same kind
Meanwhile, maintain a boy-girl-boy-girl seating arrangement
Also, each person MUST have someone (left or right) who has the same hobby.
A log should be kept for each table as it is completed. We expect that some tables will be filled and then changed as needed. If no solution exists then the rulebase should report that as well. Perhaps we need two sets of data: One that has a solution and one that does not just to see how the programmer and the rulebase deal with failure.
Data for this problem will be furnished on request so that we are all working from the same "possible" solution. It would be really nice if the participating vendors were to have some nice college intern create the data. Finally, the solution will be checked for accuracy and completeness. Actually, it should be a simple enough problem and the rules, while not terribly complex, are left up to your discretion. Ergo, nothing forced EXCEPT for a real solution. Remember this is Ms. Manners, not Miss Manners. Ms. Manners is an OO-Rulebase Problem.
Hopefully, all of the sponsors (vendors) at ORF will have the solutions for these problems ready for the attendees. :-)
SDG
jco
Posts
5 comments:
I'm bias in favor of manners, so I think that's a good update of manners benchmark. A couple of thoughts. The updated version seems more performance intensive and will require the use of NOTCE. Any rule engine that has inefficient NOTCE will likely blow up.
I spent a little while thinking about this yesterday evening. Initial thoughts are these. Selecting all the matching groups of 12 people that match all the criteria for any one table is easy, as is ensuring that each group has 6 males and 6 females. The trouble, though, is that you would then need to select 12 groups from all those matches for which no person appears more than once in any one group. When you start to do the maths, the number of combinations is huge - and I mean hundreds of billions.
Rather like the classic Miss Manners, the best approach might possibly be a depth-first, brute force approach. Start searching for a solution, one person at a time. When you hit a brick wall, backtrack and try another path. I suspect this may be the fastest approach. However, it would highlight a classic problem when trying to put together a comparative benchmark for production systems. The time it would take to find the first complete seating arrangement would depend in great measure on other factors than the performance characteristics of the engine; namely random aspects of the generated data, the order in which facts are asserted to the engine and subtle differences in the way different engines process data. The number of searches that would be made, and the number of paths that would be followed to find the first answer, would be dictated by quite arbitrary considerations. Hence, the Ms Manners benchmark, I suspect, might end up being even worse than classic Miss Manners in terms of doing comparative benchmark testing.
Now, these are just preliminary thoughts. Better, more experienced rules developers than I may be able to convince me otherwise. Hopefully there is some marvellously elegant approach which would reach a conclusion in a far more deterministic fashion.
I just thought of a new rule benchmark that could be fun. I call it n degrees of kevin bacon based on the game six degrees of kevin bacon.
http://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon
in the original game, the player is suppose to find the shortest link to kevin bacon. for the benchmark, the rule engine would need to find all possible link combinations to kevin bacon.
When can we expect a problem data set to be available?
I 'd love to take a shot at it with drools-solver as soon as a problem data set can be downloaded.
You could release 4 early problem data sets, 4 late data sets and 4 hidden data sets, like the ITC2007 competition.
http://www.cs.qub.ac.uk/itc2007/index.htm
Peter, Charles and Geoffrey:
I think that I will answer all of this in three emails (one to each of you) and then blog the result. I'm thinking that we have possibly some additional benchmarks - the kind that I personally don't approve but the kind that seems to be popular - that should be considered just to keep things interesting.
I'll try and get the data for the Manners 2009, or whatever it's going to be called, next week. I was really, really hoping that one of our fine vendors would provide that but so far no one has stepped up to the plate to submit anything.
SDG
jco
Post a Comment