Social golfer problem
In discrete mathematics, the social golfer problem (SGP) is a combinatorial design problem derived from a question posted in the usenet newsgroup sci.op-research in May 1998.[1] It is listed as Problem 010 in the online test problem library CSPLib.
A group of 32 golfers plays golf once a week in groups of 4. Schedule these golfers to play for as many weeks as possible without any two golfers playing in the same group more than once.
More generally, this problem can be defined for any golfers who play in groups of golfers for weeks. The solution involves affirming/denying the existence of a schedule and, if a schedule exists, determining the number of unique schedules and constructing them.
Challenges
The SGP is a challenging problem to solve for two main reasons:[2]
First is the large search space resulting from the combinatorial and highly symmetrical nature of the problem. That is, the weeks , groups within each week , players within each group , and individual player can all be permuted. This leads to a search space of size . Two solutions that are identical through any of these symmetry operations are isomorphisms of each other. Due to its high symmetry, the SGP is commonly used as a standard benchmark in symmetry breaking in constraint programming (symmetry-breaking constraints).
Second is the choice of variables. The SGP can be seen as an optimization problem to maximize the number of weeks in the schedule. Hence, incorrectly defined initial points and other variables in the model can lead the process to an area in the search space with no solution.
Solutions
The SGP is the Steiner system S(2,4,32) because 32 golfers are divided into groups of 4 and both the group and week assignments of any 2 golfers can be uniquely identified. Soon after the problem was proposed in 1998, a solution for 9 weeks was found and the existence of a solution for 11 weeks was proven to be impossible. In the case of the latter, note that each player must play with 3 unique players each week. For a schedule lasting 11 weeks, a player will be grouped with a total of other players. Since there are only 31 other players in the group, this is not possible.[3]
In 2004, Alejandro Aguado found a solution for 10 weeks.[4]
| Group 1 | Group 2 | Group 3 | Group 4 | Group 5 | Group 6 | Group 7 | Group 8 | |
|---|---|---|---|---|---|---|---|---|
| Week 01 | 0,1,2,3 | 4,5,22,23 | 6,7,20,21 | 8,25,26,27 | 9,10,11,24 | 12,13,15,30 | 14,28,29,31 | 16,17,18,19 |
| Week 02 | 0,4,8,28 | 1,6,18,23 | 2,7,17,22 | 3,5,26,31 | 9,13,14,27 | 10,15,19,21 | 11,25,29,30 | 12,16,20,24 |
| Week 03 | 0,11,14,21 | 1,7,10,28 | 2,15,20,25 | 3,13,22,24 | 4,9,18,31 | 5,16,27,30 | 6,8,19,29 | 12,17,23,26 |
| Week 04 | 0,18,24,27 | 1,9,19,26 | 2,8,11,16 | 3,10,17,25 | 4,7,12,29 | 5,6,14,15 | 13,20,23,28 | 21,22,30,31 |
| Week 05 | 0,6,13,26 | 1,4,11,15 | 2,9,21,28 | 3,8,14,23 | 5,12,18,25 | 7,19,24,30 | 10,16,22,29 | 17,20,27,31 |
| Week 06 | 0,7,25,31 | 1,5,24,29 | 2,12,14,19 | 3,18,28,30 | 4,6,10,27 | 8,13,17,21 | 9,15,16,23 | 11,20,22,26 |
| Week 07 | 0,5,19,20 | 1,14,22,25 | 2,23,27,29 | 3,4,16,21 | 6,9,17,30 | 7,11,13,18 | 8,10,12,31 | 15,24,26,28 |
| Week 08 | 0,15,17,29 | 1,13,16,31 | 2,4,26,30 | 3,6,11,12 | 5,7,8,9 | 10,14,18,20 | 19,22,27,28 | 21,23,24,25 |
| Week 09 | 0,9,12,22 | 1,8,20,30 | 2,5,10,13 | 3,7,15,27 | 4,14,17,24 | 6,16,25,28 | 11,19,23,31 | 18,21,26,29 |
| Week 10 | 0,10,23,30 | 1,12,21,27 | 2,6,24,31 | 3,9,20,29 | 4,13,19,25 | 5,11,17,28 | 7,14,16,26 | 8,15,18,22 |
There are many approaches to solving the SGP, namely design theory techniques,[5][6] SAT formulations (| propositional satisfiability problem), | constraint-based approaches,[7] metaheuristic methods, and radix approach.
The radix approach assigns golfers into groups based on the addition of numbers in base .[8] Variables in the general case of the SGP can be redefined as golfers who play in groups of golfers for any number . The maximum number of weeks that these golfers can play without regrouping any two golfers is .
Applications
- Group assignment in classrooms
- Sport tournament
See also
References
- ^ Harvey, Warwick. "Problem 010: Social Golfers Problem". www.csplib.org. Retrieved 6 September 2021.
- ^ Liu, Ke; Löffler, Sven; Hofstedt, Petra (February 19–21, 2019). "Social Golfer Problem Revisited". In van den Herik, Jaap; Rocha, Ana Paula; Steels, Luc (eds.). Agents and Artificial Intelligence. Springer International Publishing. pp. 72–99. ISBN 978-3-030-37494-5.
{{cite book}}: CS1 maint: date format (link) - ^ Triska, Markus. "The Social Golfer Problem". www.metalevel.at.
- ^ Aguado, Alejandro. "A 10 Days Solution to the Social Golfer Problem" (PDF). Math Puzzles. Retrieved 9 September 2021.
- ^ Lardeux, Frédéric; Monfroy, Eric (2015). "Expressively Modeling the Social Golfer Problem in SAT". Procedia Computer Science. 51: 336–345. doi:10.1016/j.procs.2015.05.252.
- ^ Triska, Markus; Musliu, Nysret (April 2012). "An improved SAT formulation for the social golfer problem". Annals of Operations Research. 194 (1): 427–438. doi:10.1007/s10479-010-0702-5.
- ^ Liu, Ke; Löffler, Sven; Hofstedt, Petra (2019). "Solving the Social Golfers Problems by Constraint Programming in Sequential and Parallel". Proceedings of the 11th International Conference on Agents and Artificial Intelligence: 29–39. doi:10.5220/0007252300290039.
- ^ Limpanuparb, Taweetham; Datta, Sopanant; Tawornparcha, Piyathida; Chinsukserm, Kridtin (17 August 2021). "ACAD-Feedback: Online Framework for Assignment, Collection, Analysis, and Distribution of Self, Peer, Instructor, and Group Feedback". Journal of Chemical Education: acs.jchemed.1c00424. doi:10.1021/acs.jchemed.1c00424.