Dinner Club Scheduling Challenge

[Greg'sDad]

It's been 40 years since engineering school, so I could use some help.
We have a subdivision dinner club. Each year, a leader sets up the schedule.
Knowns:
Number of couples, usually around 16
Number of dinners attended each season, 4
Number of couples per home, usually 4 including the host couple
Each couple hosts once per season

Challenge:
How to schedule couples so that each couple hosts once, and there's an absolute minimum number of times couples attend with the same couples. We don't want couples attending with the same people each time.

 

[Greg Bernhardt]

fyi, he is my dad! :)

 

[micromass]

Hmm, that's a problem in discrete math called designs. I'll think about it tomorrow if nobody else posts. I'm not good in discrete math, though

Some design problems are notoriously hard though. Kirkman's problem is an example of a really hard similar problem.

 

[micromass]

OK, I did it now anyway. Here is a near-optimal solution. (the hosts are bolded)

1 5 9 13
2 5 12 15
3 5 10 16
4 6 9 15
4 5 11 14
3 6 12 16
2 7 9 16
1 8 10 15
3 8 9 14
4 7 10 13
2 8 11 13
1 7 12 14
4 8 12 13
2 6 10 14
3 7 11 15
1 6 11 16

For people curious on how I obtained this. I noticed that $16=4^2$. So I started looking to lines in 2-dimension $\mathbb{F}_4$-space. Using GAP ( http://www.gap-system.org/gap.html ) and the DESIGN-package ( http://designtheory.org/software/gap_design/ ) I found an optimal solution.

However, the solution implied each couple having to go to 5 dinners. This was easily solved by eliminating 4 dinners, and I still had an optimal solution. However, each couple has to host once. This I couldn't satisfy, so I changed 2 numbers in the design. This no longer makes it optimal, but it's very close.

 

[Greg'sDad]

It certainly seems you've solved the problem! Just brilliant... I tried a simple 2 dimensional matrix and quickly saw that fail. I'm impressed (not that I'm surprised to be). I'll need to dive into your approach to see if I can duplicate it myself as the number of caveats and/or as conditions change... ie, number of couples.

Thank you so much!

 

[Greg'sDad]

I spent more time reviewing the solution and see a problem. Maybe it has to do with how to use the result. If I look at the first four rows as being the first dinner session, couple #5 attends with three hosts. They should be assigned to only one row(host).

 

[micromass]

I spent more time reviewing the solution and see a problem. Maybe it has to do with how to use the result. If I look at the first four rows as being the first dinner session, couple #5 attends with three hosts. They should be assigned to only one row(host).

Oh, so you want the dinner parties to happen at the same time?? Yes, I can see how you want that, and I certainly didn't think of that constraint.

This makes the problem a little more difficult. I'll have to think about the solution.

 

[Greg'sDad]

It was careless for me not to mention that... Apologies. By the way, the next planning session won't happen until next summer, so don't feel rushed... Thanks again.

 

[micromass]

What about this:

(1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16)

(1 5 9 13) (2 6 10 14) (3 7 11 15) (4 8 12 16)

(1 6 11 16) (2 7 12 13) (3 8 9 14) (4 5 10 15)

(1 7 12 14) (2 8 9 15) (3 5 11 13) (4 6 10 16)

This solution is not optimal (as an optimal solution can not exist). So here are the couples who have to sit twice with each other:

3 11
4 10
4 16
5 13
6 10
6 16
7 12
8 9

Be sure that 4 6 10 and 16 like each other.

I'll look for a more optimal solution.

 

[Greg'sDad]

It's really an interesting problem. I'd make a small change to start with:

(1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16)

(1 5 9 13) (2 6 10 14) (3 7 11 15) (4 8 12 16)

(1 6 11 16) (2 7 12 13) (3 8 9 14) (4 5 10 15)

(1 7 12 14) (2 8 9 15) (3 5 11 13) (4 6 10 16)

 

[micromass]

Oh sorry, I meant to change that in a 10, I think...

There is no way you can make a solution where nobody meets each other more than once (this would be the optimal solution). But now you have some people meeting one couple twice and some people meeting two couples twice. A nice mathematical problem is whether you can make a solution where every couple only meets one other couple twice. I think such a thing is impossible, but I'm not sure why.

In any case, it's an immensely interesting problem, thanks for asking!

 

[pbuk]

My first try:

( 1 2 3 4) ( 5 6 7 8) ( 9 10 11 12) (13 14 15 16)
( 1 5 9 13) ( 2 6 10 14) ( 3 7 11 15) ( 4 8 12 16)
( 1 6 11 16) ( 2 7 12 13) ( 3 8 9 14) ( 4 5 10 15)
( 1 7 9 14) ( 2 8 10 15) ( 3 5 11 16) ( 4 6 12 13)

The following 7 couples meet each other twice, with 10, 11 and 12 featuring twice
(2 10) (3 11) (4 12) (9 14) (10 15) (11 16) (12 13)

 

[pbuk]

Don't think I can improve on this at the moment:

( 1 2 3 4) ( 5 6 7 8) ( 14 10 11 12) (13 9 15 16)
( 1 5 10 13) ( 2 6 9 14) ( 3 7 11 15) ( 4 8 12 16)
( 1 6 11 16) ( 2 7 12 13) ( 3 8 9 10) ( 4 5 14 15)
( 1 7 9 14) ( 2 8 10 15) ( 3 5 12 16) ( 4 6 11 13)

The following 4 couples meet each other twice:
(6 11) (8 10) (9 14) (12 16)

Edit: it could obviously be improved by normalising (swap 9 and 14 everywhere): I'll leave that for others...

 

[pbuk]

I knew there was an optimal solution in there somewhere:

(1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16)
(1 5 9 13) (2 6 10 14) (3 7 11 15) (4 8 12 16)
(1 6 11 16) (2 5 12 15) (3 8 9 14) (4 7 10 13)
(1 7 12 14) (2 8 11 13) (3 5 10 16) (4 6 9 15)

No couple meets twice.

 

[micromass]

I knew there was an optimal solution in there somewhere:

(1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16)
(1 5 9 13) (2 6 10 14) (3 7 11 15) (4 8 12 16)
(1 6 11 16) (2 5 12 15) (3 8 9 14) (4 7 10 13)
(1 7 12 14) (2 8 11 13) (3 5 10 16) (4 6 9 15)

No couple meets twice.

Wonderful! I really thought it was impossible.

How did you obtain it? Just trial and error??

 

[pbuk]

... and note that
(1 8 10 15) (2 7 9 16) (3 6 12 13) (4 5 11 14)
completes the design so that each member is paired with each other member exactly once.

Not exactly trial and error, there is an heuristic for building these designs which I came across a while ago. Sometimes the heuristic requires backtracking, but in this case it doesn't. I believe that this heuristic will always find an optimal design if one exists (providing the backtracking algorithm is thorough).

Basically a row of the design is generated by selecting the lowest number that does not create a collision: you just have to be careful to keep track of pairs that have already been generated (my first solution I didn't take enough care and got some doubles). If you get to the stage where there is no such pair, you need to backtrack using some strategy.

 

[Greg'sDad]

Absolutely amazing! We need the following small change so #13 doesn't host twice:
(1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 (16 hosts)) (I don't see how to format)
(1 5 9 13) (2 6 10 14) (3 7 11 15) (4 8 12 16)
(1 6 11 16) (2 5 12 15) (3 8 9 14) (4 7 10 13)
(1 7 12 14) (2 8 11 13) (3 5 10 16) (4 6 9 15)

I see the pattern on the first two rows, but the 3rd and 4th look like you just kept track of previous assignments and somehow "figured it out". My challenge in the future will be figuring this out myself when/if there are more couples in the club in future seasons. I thank you though for your efforts! Well done and very helpful.

 

[micromass]

Absolutely amazing! We need the following small change so #13 doesn't host twice:
(1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 (16 hosts)) (I don't see how to format)
(1 5 9 13) (2 6 10 14) (3 7 11 15) (4 8 12 16)
(1 6 11 16) (2 5 12 15) (3 8 9 14) (4 7 10 13)
(1 7 12 14) (2 8 11 13) (3 5 10 16) (4 6 9 15)

I see the pattern on the first two rows, but the 3rd and 4th look like you just kept track of previous assignments and somehow "figured it out". My challenge in the future will be figuring this out myself when/if there are more couples in the club in future seasons. I thank you though for your efforts! Well done and very helpful.

Perhaps I could write you a computer program that automatically calculates such things. I'll think some more about it to see if this is actually possible/efficient...

 

[Greg'sDad]

(1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 16)
(1 5 9 13) (2 6 10 14) (3 7 11 15) (4 8 12 16)
(1 6 11 16) (2 5 12 15) (3 8 9 14) (4 7 10 13)
(1 7 12 14) (2 8 11 13) (3 5 10 16) (4 6 9 15)

Minor change to make sure couple #13 hosts only once...

Amazing work. My challenge will come now when numbers of couples change in future seasons. Thanks.

p.s. I'm very skilled with Excel if that helps...

 

[pbuk]

Oops, sorry about the 2x13 - unlucky number syndrome

This heuristic should be fairly easy to program apart from the backtracking algorithm (which wasn't needed here and probably won't be unless the groups get bigger so there are more pairs each time).

Since I used Excel to keep track, I'll upload the file here: note that this doesn't generate trial solutions or count pairs or anything like that, it just provides a template (and some check sums) to aid the manual process.

 

[micromass]

... and note that
(1 8 10 15) (2 7 9 16) (3 6 12 13) (4 5 11 14)
completes the design so that each member is paired with each other member exactly once.

Not exactly trial and error, there is an heuristic for building these designs which I came across a while ago. Sometimes the heuristic requires backtracking, but in this case it doesn't. I believe that this heuristic will always find an optimal design if one exists (providing the backtracking algorithm is thorough).

Basically a row of the design is generated by selecting the lowest number that does not create a collision: you just have to be careful to keep track of pairs that have already been generated (my first solution I didn't take enough care and got some doubles). If you get to the stage where there is no such pair, you need to backtrack using some strategy.

LOL, I just realized that this is the exact same thing as I already posted in post 4! I was just too stupid to notice that they could be arranged as a partition!

I mean: the design you found by trial-and-error is exactly the lines of a 2-dimensional vector space over $\mathbb{F}_4$!

Man, I can be stupid sometimes...

 

[pbuk]

I mean: the design you found by trial-and-error is exactly the lines of a 2-dimensional vector space over $\mathbb{F}_4$!

Yes, if I had thought about it the fact that there were 4 groups of 4 made the solution trivial so I didn't need to embark on the heuristic search for it. The solutions of these systems in general are surprisingly unpredictable - see for example Kirkman's Schoolgirl Problem.

 

[Greg'sDad]

OK. I confess you're way ahead of me! Now you say this is actually easy? I'm in awe.

 

[pbuk]

Like most maths that is interesting to a mathematician it is a bit of a niche - I have only skimmed it personally. Related problems include Latin Squares and of course Sudoku!

 

[micromass]

OK. I confess you're way ahead of me! Now you say this is actually easy? I'm in awe.

No, we say that we've been very lucky! You have 16 people and want to divide them 4 times in 4 groups. This is much easier then having 15 people and dividing them 7 times in groups of 3 for example (which is essentially http://en.wikipedia.org/wiki/Kirkman's_schoolgirl_problem ).

 

[Greg'sDad]

I de-constructed your model spreadsheet to the point where it really gets interesting. Am I correct that now brute-force trial and error steps are needed to complete the matrix? I've never seen the Excel index command, and that's extremely powerful in this exercise.

 

[pbuk]

Your markup in that table is incomplete, see the attached. You can then proceed without trial and error (with the parameters for this problem) as follows:

1. 6 is the first vacant column in the 1 row so enter 6 as the second element of the first group and mark a 1 in (row 1, col 6)
2. 7 is the next vacant column in the 1 row but we also need to check this against 6 and can see that it has already been paired, so move to 8 (already paired with 6), 9 (paired with 1), 10 (paired with 6), and 11 - that has no entry in either the 1 or 6 rows so that is the third element; mark 1s in (row 1, col 11) and (row 6, col 11)
3. Next we consider 12 (paired with 11), 13 (1), 14 (6) 15 (11) and 16 (that's OK).
4. Proceed in the same manner until complete

It's all quite straightforward until you run out of choices, then you either have to continue with a sub-optimal solution or backtrack in the hope of finding an optimal one - there is no guarantee that one exists in general, but much work has been done on many similar systems, for instance complete optimal solutions exist for a Steiner Quadruple System with n elements if and only if n mod 6 = 2 or 4 so it would be interesting to see if your system has an optimal design when n = 12.

Note that the choice of backtracking algorithm will impact compution speed significantly: I suspect that changing choices at the beginning of the decision tree would yield an optimum solution much more quickly than a simple 'undo last decision' strategy.

 

[pbuk]

A little more googling shows that your problem is known as the http://www.cs.brown.edu/~sello/golf.html and has been investigated for a number of parameters. Surprisingly it appears to be the case that the solution for the original problem is unique (barring symmetry).

Note that the generalised problem ignores the 'single host' constraint of the original problem: I would guess that this is either trivial to satisfy or (if there are more meals than hosts) impossible.