Dinner Club Scheduling Challenge

  • Thread starter Greg'sDad
  • Start date
  • #26
11
0
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.
 

Attachments

  • #27
pbuk
Science Advisor
Gold Member
1,883
726
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.
 

Attachments

  • #28
pbuk
Science Advisor
Gold Member
1,883
726
A little more googling shows that your problem is known as the Social Golfer Problem 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.
 
Last edited:

Related Threads on Dinner Club Scheduling Challenge

  • Last Post
Replies
3
Views
728
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
13
Views
5K
Replies
5
Views
1K
  • Last Post
Replies
6
Views
6K
  • Last Post
Replies
1
Views
2K
Replies
1
Views
757
Replies
18
Views
2K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
15
Views
2K
Top