\newchapter{Social Golfer Problem}

\renewcommand{\CURPATH}{SGP}

\leveldown{}

\begin{framed}
\begin{quotation}
Twenty golfers wish to play in foursomes for 5 days. Is it possible for each golfer to play no more than once with any other golfer?

...

Event organizers for bowling, golf, bridge, or tennis frequently tackle problems of this sort, unaware of the problem complexity. In general, it is an unsolved problem. A table of known results is maintained by Harvey.
\end{quotation}
\end{framed}
( \url{http://mathworld.wolfram.com/SocialGolferProblem.html} )

It's also problem 010 in CSPLIB\footnote{\url{https://csplib.github.io/csplib-builds/ghmeta/Problems/prob010/results/}}.

This is the solution that was ported from Markus Triska's solution written in Prolog\footnote{\url{https://www.metalevel.at/sgpsat.pdf},
\url{https://www.metalevel.at/sgp/satgolf.pl}}.

This is an example solution for 7 golfers, 3 players in group, 9 weeks/days (7-3-9):

\begin{lstlisting}
* week 1
[[1, 2, 4], [3, 5, 13], [6, 8, 19], [7, 16, 20], [9, 11, 14], [10, 15, 18], [12, 17, 21]]
* week 2
[[1, 3, 10], [2, 11, 18], [4, 13, 16], [5, 14, 19], [6, 9, 12], [7, 15, 17], [8, 20, 21]]
* week 3
[[1, 6, 14], [2, 7, 9], [3, 15, 21], [4, 10, 11], [5, 12, 20], [8, 13, 18], [16, 17, 19]]
* week 4
[[1, 7, 11], [2, 5, 17], [3, 6, 16], [4, 9, 18], [8, 12, 15], [10, 19, 20], [13, 14, 21]]
* week 5
[[1, 9, 20], [2, 12, 13], [3, 7, 8], [4, 6, 15], [5, 16, 18], [10, 14, 17], [11, 19, 21]]
* week 6
[[1, 12, 19], [2, 16, 21], [3, 9, 17], [4, 7, 14], [5, 8, 10], [6, 18, 20], [11, 13, 15]]
* week 7
[[1, 13, 17], [2, 6, 10], [3, 11, 12], [4, 5, 21], [7, 18, 19], [8, 9, 16], [14, 15, 20]]
* week 8
[[1, 15, 16], [2, 3, 20], [4, 8, 17], [5, 6, 11], [7, 10, 21], [9, 13, 19], [12, 14, 18]]
* week 9
[[1, 18, 21], [2, 8, 14], [3, 4, 19], [5, 9, 15], [6, 7, 13], [10, 12, 16], [11, 17, 20]]
\end{lstlisting}

I also wanted to check timings when symmertry breaking constraints present and when not.
These are my results.
All checked on Intel(R) Xeon(R) CPU E3-1270 v3 @ 3.50GHz.
Kissat 2.0.1 (2021) SAT solver was used.
Time in seconds.

\begin{center}
\begin{longtable}{ | l | l | l | }
\hline
G-P-W   & with symmetry breaking & without symmetry breaking \\
\hline
2-2-3   & <1            & <1 \\
3-2-5   & <1            & <1 \\
3-3-4   & <1            & <1 \\
4-2-7   & <1            & <1 \\
4-3-4   & <1            & <1 \\
4-4-4   & <1            & <1 \\
4-4-5   & <1            & - \\
5-2-9   & <1            & <1 \\
6-2-11  & <1            & - \\
7-2-13  & <1            & 1 \\
\hline
5-3-7   & 1             & 29 \\
5-4-5   & 1             & <1 \\
5-5-6   & 1             & - \\
6-6-3   & 1             & 1 \\
8-2-15  & 1             & <1 \\
9-2-17  & 1             & 1 \\
\hline
6-4-5   & 2             & <1 \\
10-2-19 & 5             & 7 \\
7-5-5   & 7             & - \\
\hline
7-6-4   & 11            & - \\
9-4-8   & 14            & 2649 \\
9-5-6   & 14            & 75 \\
9-8-3   & 15            & 4 \\
8-7-4   & 16            & 1832 \\
8-3-10  & 18            & 18089 \\
9-9-3   & 19            & 4 \\
9-7-4   & 26            & 23 \\
9-3-11  & 33            & 5867 \\
10-9-3  & 35            & 6 \\
9-6-5   & 37            & 49 \\
10-8-4  & 37            & - \\
10-5-7  & 40            & 829 \\
7-3-9   & 55            & 19147 \\
10-4-9  & 81            & 21702 \\
\hline
10-10-3 & 140           & - \\
10-7-5  & 171           & - \\
6-3-8   & 236           & 86172 \\
10-6-6  & 393           & 4421 \\
\hline
8-5-6   & 1423          & 881 \\
10-3-13 & 2065          & ? \\
8-6-5   & 7105          & 689 \\
\hline
7-4-7   & 11021         & ? \\
\hline
6-5-6   & 70026         & 66669 \\
\hline
6-4-7   & ?             & - \\
6-6-4   & ?             & - \\
6-6-7   & ?             & ? \\
7-3-10  & ?             & ? \\
7-4-9   & ?             & ? \\
7-7-7   & ?             & ? \\
7-7-8   & ?             & ? \\
8-3-11  & ?             & ? \\
8-4-10  & ?             & ? \\
8-4-9   & ?             & - \\
8-8-9   & ?             & ? \\
9-4-11  & ?             & - \\
9-9-10  & ?             & ? \\
\hline
\end{longtable}
\end{center}

'?' --- not solved withing 24 hours.
'-' --- not executed.

Clearly, almost always, symmetry breaking constraints are of help.
But there are few cases, when they slows down everything.

Python source code: \url{\RepoURL/\CURPATH/gen.py}.

All resulting files: \url{\RepoURL/\CURPATH/results.tar}.

Further reading:

\begin{itemize}
\item Ian P. Gent and Inês Lynce -- \href{https://web.archive.org/web/20061008121707/https://www.inesc-id.pt/ficheiros/publicacoes/2516.pdf}{A SAT Encoding for the Social Golfer Problem}.

\item Markus Triska:
        \href{https://www.metalevel.at/sgp/}{Webpage},
        \href{https://www.metalevel.at/mst.pdf}{Solution Methods for the Social Golfer Problem}.

\item Warwick Harvey:
        \href{https://web.archive.org/web/20050308115423/http://www.icparc.ic.ac.uk/~wh/golf/}{Warwick's Results Page for the Social Golfer Problem},
        \href{https://web.archive.org/web/20050407074608/http://www.icparc.ic.ac.uk/~wh/golf/solutions.html}{Solutions to various Social Golfer configurations}.

\item Ed Pegg Jr:
        \href{https://web.archive.org/web/20130516045754/http://www.maa.org/editorial/mathgames/mathgames_08_14_07.html}{Social Golfer Problem}.

\item \url{https://demonstrations.wolfram.com/SocialGolferProblem/}.

\item Ke Liu, Sven Löffler and Petra Hofstedt: \href{https://pdfs.semanticscholar.org/30ff/5ca06d1714e7837cfb0889b77024a8e64f4f.pdf}{Solving the Social Golfers Problems by Constraint Programming in Sequential and Parallel}.

\end{itemize}

\levelup{}