Det sociala golfproblemet

Det sociala golfproblemet (SGP) är ett kombinatoriskt designproblem inom diskret matematik som härrör från en fråga som publicerades i usenet-nyhetsgruppen sci.op-research i maj 1998.^[1] Problemet är följande: 32 golfare spelar golf en gång i veckan i grupper om fyra. Schemalägg dessa golfare att spela i så många veckor som möjligt utan att två golfare spelar tillsammans i en grupp mer än en gång.

Mer generellt kan detta problem definieras för vilken som helst $n=g\times s$ golfare som spelar i $g$ grupper av $s$ golfare för $w$ veckor. Lösningen innebär att antingen verifiera eller motbevisa existensen av ett schema och, om ett sådant schema existerar, bestämma antalet unika scheman och konstruera dem.

Utmaningar

SGP är ett utmanande problem att lösa av två huvudskäl:^[2]

För det första är det det stora sökutrymmet som är ett resultat av problemets kombinatoriska och mycket symmetriska natur. Det finns totalt $(n!)^{w}$ scheman i sökfältet. För varje schema kan veckorna $(w!)$ , grupper inom varje vecka $(g!)$ , spelare inom varje grupp $(s!)$ och individuell spelare $(n!)$ , alla permuteras. Detta leder till totalt $w!\times g!\times s!\times n!$ isomorfismer – scheman som är identiska genom någon av dessa symmetrioperationer. På grund av sin höga symmetri används SGP ofta som ett standardriktmärke för symmetribrytning i villkorsprogrammering ( symmetribrytande begränsningar ).

Det andra är valet av variabler. SGP kan ses som ett optimeringsproblem för att maximera antalet veckor i schemat. Därför kan felaktigt definierade initialpunkter och andra variabler i modellen leda processen till ett område i sökrummet utan lösning.

Lösningar

SGP är inom Steinersystemet S(2,4,32) eftersom 32 golfare är indelade i grupper om 4 och både grupp- och veckotilldelningen för 2 golfare kan identifieras unikt. Strax efter att problemet föreslogs 1998 hittades en lösning på 9 veckor och existensen av en lösning på 11 veckor visade sig vara omöjlig. I fallet med det senare, observera att varje spelare måste spela med 3 unika spelare varje vecka. För ett schema som varar i 11 veckor kommer en spelare att grupperas med totalt $3\times 11=33$ andra spelare. Eftersom det bara finns 31 andra spelare i gruppen är detta inte möjligt.^[3] Det är nu känt att en lösning för 10 veckor kunde erhållas från resultat som redan publicerades 1996 av Hao Shen, men den konstruerades aldrig explicit.^[4] Den första explicita lösningen konstruerades oberoende av Alejandro Aguado år 2004 med en annan metod.^[5] Detta är lösningen som presenteras nedan.

10-veckorslösning till det sociala golfarproblemet (Aguado - 2004)
	Grupp 1	Grupp 2	Grupp 3	Grupp 4	Grupp 5	Grupp 6	Grupp 7	Grupp 8
Vecka 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
Vecka 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
Vecka 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
Vecka 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
Vecka 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
Vecka 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
Vecka 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
Vecka 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
Vecka 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
Vecka 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

Det finns många metoder för att lösa SGP, nämligen designteoritekniker,^[6]^[7] SAT-formuleringar (propositionellt satisfierbarhetsproblem), begränsningsbaserade metoder,^[8] metaheuristiska metoder och talbasmetoden.

Talbasmetoden delar in golfare i grupper baserat på addition av tal i basen $k$ ^[9] Variabler i det allmänna fallet med SGP kan omdefinieras som $n=s^{k}$ golfare som spelar i $g=s^{k-1}$ grupper av $s$ golfare för valfritt antal $k$ . Det maximala antalet veckor som dessa golfare kan spela utan att omgruppera två golfare är $(s^{k}-1)/(s-1)$ .

Tillämpningar

Att arbeta i grupp uppmuntras i klassrummen eftersom det främjar aktivt lärande och utveckling av kritiskt tänkande och kommunikationsförmåga. SGP har använts för att dela in studenter i grupper i kemikurser på grundnivå^[9] och i grupper i online-mötesprogram^[10] för att maximera studentinteraktion och socialisering.

SGP har också använts som modell för att studera turneringsplanering.^[11]

Se även

Round-robin-turnering

Referenser

↑ Harvey, Warwick. ”Problem 010: Social Golfers Problem”. www.csplib.org. https://www.csplib.org/Problems/prob010.
↑ Liu, Ke; Löffler, Sven; Hofstedt, Petra (2019). ”Social Golfer Problem Revisited”. Agents and Artificial Intelligence: 11th International Conference, ICAART 2019, Prague, Czech Republic, February 19–21, 2019, Revised Selected Papers. Springer International Publishing. sid. 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. https://www.metalevel.at/sgp/.
↑ Shen, Hao. Existence of resolvable group divisible designs with block size four and group size two or three.
↑ Aguado, Alejandro. ”A 10 Days Solution to the Social Golfer Problem”. Math Puzzles. https://www.mathpuzzle.com/MAA/54-Golf%20Tournaments/socgolf1.pdf.
↑ Lardeux, Frédéric; Monfroy, Eric (2015). Expressively Modeling the Social Golfer Problem in SAT. sid. 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. sid. 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. Science and Technology Publications. sid. 29–39. doi:10.5220/0007252300290039. ISBN 978-989-758-350-6
1 2 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): sid. 3038–3044. doi:10.1021/acs.jchemed.1c00424.
↑ Miller, Alice; Barr, Matthew; Kavanagh, William (2021). Breakout Group Allocation Schedules and the Social Golfer Problem with Adjacent Group Sizes. 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”. Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings. Springer. sid. 149–162. doi:10.1007/978-3-030-78230-6_10. ISBN 978-3-030-78230-6

Wolfram Community: Radix-metoden för att lösa problemet med sociala golfare och grafvisualisering
Wolfram Mathworld: Problem med social golfare

[1] Harvey, Warwick. ”Problem 010: Social Golfers Problem”. www.csplib.org. https://www.csplib.org/Problems/prob010.

[2] Liu, Ke; Löffler, Sven; Hofstedt, Petra (2019). ”Social Golfer Problem Revisited”. Agents and Artificial Intelligence: 11th International Conference, ICAART 2019, Prague, Czech Republic, February 19–21, 2019, Revised Selected Papers. Springer International Publishing. sid. 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. https://www.metalevel.at/sgp/.

[4] Shen, Hao. Existence of resolvable group divisible designs with block size four and group size two or three.

[5] Aguado, Alejandro. ”A 10 Days Solution to the Social Golfer Problem”. Math Puzzles. https://www.mathpuzzle.com/MAA/54-Golf%20Tournaments/socgolf1.pdf.

[6] Lardeux, Frédéric; Monfroy, Eric (2015). Expressively Modeling the Social Golfer Problem in SAT. sid. 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. sid. 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”. Proceedings of the 11th International Conference on Agents and Artificial Intelligence. Science and Technology Publications. sid. 29–39. doi:10.5220/0007252300290039. ISBN 978-989-758-350-6

[ACAD-Feedback-9] 1 2 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): sid. 3038–3044. doi:10.1021/acs.jchemed.1c00424.

[10] Miller, Alice; Barr, Matthew; Kavanagh, William (2021). Breakout Group Allocation Schedules and the Social Golfer Problem with Adjacent Group Sizes. 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”. Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 18th International Conference, CPAIOR 2021, Vienna, Austria, July 5–8, 2021, Proceedings. Springer. sid. 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]