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] The problem is as follows: 32 golfers play golf once a week in groups of 4. Schedule these golfers to play for as many weeks as possible without any two golfers playing together in a group more than once.

More generally, this problem can be defined for any $n=g\times s$ golfers who play in $g$ groups of $s$ golfers for $w$ weeks. The solution involves either affirming or denying the existence of a schedule and, if such 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. There are a total of $(n!)^{w}$ schedules in the search space. For each schedule, the weeks $(w!)$ , groups within each week $(g!)$ , players within each group $(s!)$ , and individual player $(n!)$ can all be permuted. This leads to a total of $w!\times g!\times s!\times n!$ isomorphisms, schedules that are identical through any of these symmetry operations. 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 $3\times 11=33$ other players. Since there are only 31 other players in the group, this is not possible.^[3] A solution for 10 weeks could be obtained from results already published in 1996.^[4] It was independently rediscovered using a different method in 2004,^[5] which is the solution presented below.

10-Week solution to the Social Golfer Problem (Aguado - 2004)
	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,^[6]^[7] SAT formulations (propositional satisfiability problem), constraint-based approaches,^[8] metaheuristic methods, and radix approach.

The radix approach assigns golfers into groups based on the addition of numbers in base $k$ .^[9] Variables in the general case of the SGP can be redefined as $n=s^{k}$ golfers who play in $g=s^{k-1}$ groups of $s$ golfers for any number $k$ . The maximum number of weeks that these golfers can play without regrouping any two golfers is $(s^{k}-1)/(s-1)$ .

Applications

Working in groups is encouraged in classrooms because it fosters active learning and development of critical-thinking and communication skills. The SGP has been used to assign students into groups in undergraduate chemistry classes^[9] and breakout rooms in online meeting software^[10] to maximize student interaction and socialization.

The SGP has also been used as a model to study tournament scheduling.^[11]

References

^ Harvey, Warwick. "Problem 010: Social Golfers Problem". www.csplib.org. Retrieved 6 September 2021.
^ Liu, Ke; Löffler, Sven; Hofstedt, Petra (2019). "Social Golfer Problem Revisited". In van den Herik, Jaap; Rocha, Ana Paula; Steels, Luc (eds.). Agents and Artificial Intelligence: 11th International Conference, ICAART 2019, Prague, Czech Republic, February 19–21, 2019, Revised Selected Papers. Springer International Publishing. pp. 72–99. doi:10.1007/978-3-030-37494-5_5. ISBN 978-3-030-37494-5.
^ Triska, Markus. "The Social Golfer Problem". www.metalevel.at.
^ Shen, Hao (1996). "Existence of resolvable group divisible designs with block size four and group size two or three". Journal of Shanghai Jiaotong University. 1 (1): 68–70. MR 1454271.
^ 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". In Rocha, Ana; Steels, Luc; van den Herik, Jaap (eds.). Proceedings of the 11th International Conference on Agents and Artificial Intelligence. Science and Technology Publications. pp. 29–39. doi:10.5220/0007252300290039. ISBN 978-989-758-350-6.
^ ^a ^b Limpanuparb, Taweetham; Datta, Sopanant; Tawornparcha, Piyathida; Chinsukserm, Kridtin (2021). "ACAD-Feedback: Online Framework for Assignment, Collection, Analysis, and Distribution of Self, Peer, Instructor, and Group Feedback". Journal of Chemical Education. 98 (9): 3038–3044. doi:10.1021/acs.jchemed.1c00424.
^ Miller, Alice; Barr, Matthew; Kavanagh, William; Valkov, Ivaylo; Purchase, Helen C (2021). "Breakout Group Allocation Schedules and the Social Golfer Problem with Adjacent Group Sizes". Symmetry. 13 (13). doi:10.3390/sym13010013.
^ Lambers, Roel; Rothuizen, Laurent; Spieksma, Frits C. R. (2021). "The Traveling Social Golfer Problem: The Case of the Volleyball Nations League". In Stuckey, Peter J. (ed.). Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings. Springer. pp. 149–162. doi:10.1007/978-3-030-78230-6_10. ISBN 978-3-030-78230-6.

External links

Wolfram Community: Radix Approach to Solving the Social Golfer Problem and Graph Visualization
Wolfram Mathworld: Social Golfer Problem

[1] Harvey, Warwick. "Problem 010: Social Golfers Problem". www.csplib.org. Retrieved 6 September 2021.

[2] Liu, Ke; Löffler, Sven; Hofstedt, Petra (2019). "Social Golfer Problem Revisited". In van den Herik, Jaap; Rocha, Ana Paula; Steels, Luc (eds.). Agents and Artificial Intelligence: 11th International Conference, ICAART 2019, Prague, Czech Republic, February 19–21, 2019, Revised Selected Papers. Springer International Publishing. pp. 72–99. doi:10.1007/978-3-030-37494-5_5. ISBN 978-3-030-37494-5.

[3] Triska, Markus. "The Social Golfer Problem". www.metalevel.at.

[4] Shen, Hao (1996). "Existence of resolvable group divisible designs with block size four and group size two or three". Journal of Shanghai Jiaotong University. 1 (1): 68–70. MR 1454271.

[5] Aguado, Alejandro. "A 10 Days Solution to the Social Golfer Problem" (PDF). Math Puzzles. Retrieved 9 September 2021.

[6] 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.

[7] 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.

[8] Liu, Ke; Löffler, Sven; Hofstedt, Petra (2019). "Solving the Social Golfers Problems by Constraint Programming in Sequential and Parallel". In Rocha, Ana; Steels, Luc; van den Herik, Jaap (eds.). Proceedings of the 11th International Conference on Agents and Artificial Intelligence. Science and Technology Publications. pp. 29–39. doi:10.5220/0007252300290039. ISBN 978-989-758-350-6.

[ACAD-Feedback-9] Limpanuparb, Taweetham; Datta, Sopanant; Tawornparcha, Piyathida; Chinsukserm, Kridtin (2021). "ACAD-Feedback: Online Framework for Assignment, Collection, Analysis, and Distribution of Self, Peer, Instructor, and Group Feedback". Journal of Chemical Education. 98 (9): 3038–3044. doi:10.1021/acs.jchemed.1c00424.

[10] Miller, Alice; Barr, Matthew; Kavanagh, William; Valkov, Ivaylo; Purchase, Helen C (2021). "Breakout Group Allocation Schedules and the Social Golfer Problem with Adjacent Group Sizes". Symmetry. 13 (13). doi:10.3390/sym13010013.

[11] Lambers, Roel; Rothuizen, Laurent; Spieksma, Frits C. R. (2021). "The Traveling Social Golfer Problem: The Case of the Volleyball Nations League". In Stuckey, Peter J. (ed.). Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings. Springer. pp. 149–162. doi:10.1007/978-3-030-78230-6_10. ISBN 978-3-030-78230-6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Challenges

Solutions

Applications

See also

References

External links