report.tex

\documentclass[a4paper]{article}
\usepackage{hyperref} 
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{mathtools}
 
\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
 
\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\newcommand{\mdef}[2]{
	\theoremstyle{definition}
	\begin{definition}{#1}
	#2
	\end{definition}
}

\newcommand{\mremark}[2]{
	\theoremstyle{remark}
	\begin{remark}{#1}
	#2
	\end{remark}
}

\newcommand{\ccc}[1]{{\mbox{\fontfamily{lmtt}\selectfont\textbf{#1}}}}

\def \golf {Golf Problem Solver}

\renewcommand{\abstractname}{\golf}

\begin{document}

\title{\golf}
\author{Petr Geiger}
\date
\maketitle

\begin{abstract}
The goal of this project is to implement constrain satisfaction model
for general case of \href{http://mathworld.wolfram.com/SocialGolferProblem.html}
{Social Golfer Problem}. The model is implemented in \href{https://sicstus.sics.se/}
{SICStus Prolog} using its \href{https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/lib_002dclpfd.html#lib_002dclpfd}
{CSP over Finite Domains library}.
\end{abstract}

\section{Problem Definition}\label{table}
From \href{http://mathworld.wolfram.com/SocialGolferProblem.html}{Wolfram Math World} original definition of problem is as follows:

\textit{``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? The answer is yes, and the following table gives a solution.}

\begin{tabular}{| l || c | c | c | c | r |}
\hline
Mon & ABCD & EFGH & IJKL & MNOP	& QRST \\
\hline
Tue & AEIM & BJOQ & CHNT & DGLS	& FKPR \\
\hline
Wed & AGKO & BIPT & CFMS & DHJR	& ELNQ \\
\hline
Thu & AHLP & BKNS & CEOR & DFIQ	& GJMT \\
\hline
Fri & AFJN & BLMR& CGPQ	& DEKT & HIOS \\
\hline
\end{tabular} 

\textit{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."
}


\subsection{General case problem definition}\label{general-def}

Lets first define problem parameters.

\mdef{}{ 
	\begin{enumerate}[(i)]
		\item $ N \in \mathbb{N} $ ... number of players 
		\item $ K \in \mathbb{N} $ ... size of groups
		\item $ D \in \mathbb{N} $ ... number of days
		\item $ G \in \mathbb{N} $ ... number of groups
	\end{enumerate}
}

Now when we have our problem parametrized we can describe model assuming those parameters.
But lets first define following simple notation.
\mdef{}{
	For given $S \in \mathbb{N}$ define:
	$$ [S] \equiv \{0,1,2,...,S-1\}.  $$
 }

\mdef{}{ Lets define groups as sets $\forall i \in [G], j \in [D]: S_{i,j}$ such  as:
	\begin{enumerate}[(i)]
		\item Players are identified by numbers in given groups. $$\forall p \in S_{i,j}: p \in [N]$$ 
		\item\label{groups-size} Every group has exactly $K$ players in it. $$ |S_{i,j}| = K$$  
		\item\label{one-player} Every player is at most once in group. $S_{i,j}$ are sets thus this holds trivaly. 
		\item\label{once-per-day} Every player is playing exactly once in every day.  $$ \forall i \in [D]: \bigsqcup_{ j \in [G]} S_{i,j} = [N] $$
		\item\label{player-pairs} Every player plays no more then once with any other player. Which is same as every pair of players 
		is in at most 1 group.  $$ \forall x,y \in [N]: |\{S | \exists i \in [D] \land \exists j \in [G]: x \in S_{i,j} \land y \in S_{i,j}\}| < 2 $$
	\end{enumerate}  
}



\mremark{}{ 
We can see that conditions \ref{groups-size} and \ref{once-per-day} implies that:
$$ N = G*K. $$
}\label{insight}


In following section our task is going to be to choose proper representation for this model in terms of CSP.



\section{CSP model representation}
% - v kazdem dni 
% (A) priradim kazdemu hraci skupinu
% vs
% (B) priradim kazdemu mistu ve skupine hrace
% vs
% (C) generovat rovnou inteligentne
% 
% (A)
% 5^20 k
% (1) podminka: kazda skupina ma prave k hrace
% 
% (B)
% 20^20
% (1a) podminka: hraci se ve skupine neopakuji
% (1b) podminka: kazdy hrac je pouze v jedne skupine 
% 
% 
% -pro vsechny skupiny mezi dny 
% (2) podminka: kazdy hrac hralje s kazdym nejvyse 1


Simpliest representation which comes right into our mind is using directly definition \ref{general-def}.

\subsection{Straight forward model}
We just create for each slot in each group in each day variable and will try to assign right players.

\mdef{}{ Lets define CSP model $M_a = \langle V_a,D_a,C_a \rangle$ such as:
	\begin{enumerate}[(i)]
		\item $$ V_a = \{V_k|  \forall i \in [D], \forall j \in [G], \forall p \in [K] \exists k \in \mathbb{N}: V_k \text{ is CSP variable } \land  k=i*G*K+j*K+p \} $$
		\item $$ D_a = \{D_i| \forall V_i \in V: D_i = [N] \} $$
		\item $$ C_a = \{ C_1, C_2, C_3, C_4\} $$
		\begin{enumerate}
			\item To ensure conditions \ref{groups-size} and \ref{one-player} we need constrain $C_1$ requiring that player can be assigned to at most one variable in certain group.
			\item To ensure condition \ref{once-per-day} we need constrain $C_2$ requiring that each player playes once per day. 
			\item To ensure condition \ref{player-pairs} we need constrain $C_3$ requiring that each pair of player plays at most once.
			\item Optionaly it would be good idea to create another constrain $C_4$ requiring order in variables of groups to prune state space.
		\end{enumerate}
	\end{enumerate}
}


One can see that although $M_a$ model is quite straight forward for variable representation,
we have to pay more attention for constrains. 

\subsubsection{Worst case estimate}

Lets make estimate how much states CSP solver has to go through in worst case.
Each variable $V_i$ can be assigned by $N$ domain values and there is 
$D*G*K$ of such variables thus estimate is:
$$N^{D*G*K} = 2^{\log_2{(N)}*D*G*K}$$

\subsubsection{Conclusion}
Problem of this model is obliviously unordered sets for group variables. 
This thought led us to following model.

\subsection{Model dealing with unordered sets}
This model increaces number of variables substantialy, but also reduces domains values substantialy.
\mdef{}{ Lets define CSP model $M_b = \langle V_b,D_b,C_b \rangle$ such as:
	\begin{enumerate}[(i)]
		\item $$ V_b = \{V_k|  \forall i \in [D], \forall j \in [G], \forall l \in [N] \exists k \in \mathbb{N}: V_k \text{ is CSP variable } \land  k=i*G*N+j*N+l \} $$
		\item $$ D_b = \{D_i| \forall V_i \in V: D_i = [2] \} $$
		\item $$ C_b = \{ C_1, C_2, C_3\} $$
		\begin{enumerate}
			\item To ensure condition \ref{groups-size} we need constrain $C_1$ ensuring there is going to be
			set exactly $K$ variables from each variables for given group.
			\item The condition \ref{one-player} is taken for granted in this model.
			\item To ensure condition \ref{once-per-day} we need constrain $C_2$ requiring that each player plays once per day. 
			\item To ensure condition \ref{player-pairs} we need constrain $C_3$ requiring that each pair of player plays at most once.
		\end{enumerate}
	\end{enumerate}
}

\subsubsection{Worst case estimate}

Lets make estimate how much states CSP solver has to go through in worst case.
Each variable $V_i$ can be assigned by $2$ domain values and there is 
$D*G*N$ of such variables thus estimate is:
$$2^{D*G*N}.$$

\subsubsection{Worst case estimate $M_a$ vs $M_b$}
Lets try to find out for, which $N$ and $G$ is $M_b$ model better.
$$2^{D*G*N} < 2^{\log_2{(N)}*D*G*K}$$
$$D*G*N < \log_2{(N)}*D*G*K$$
$$ N < \log_2{(N)}*K$$
Using remark from \ref{insight} $N = G*K$.
$$ K*G < \log_2{(N)}*K$$
$$ G < \log_2{(N)}$$
$$ 2^G < N $$
Which holds for $N$:
$$N \in \Omega(2^G)$$

Thus for $N >> G$ can be this model actually better.

\subsubsection{Conclusion}
To sum this up we have increased number of variables in favor of decreasing number of domain variables.
We also need less constrains, because this model does not have problem with order of
variables in groups. This model also automaticly ensures that one player
can not be in group multiple times, which leads to simplification of constrains.
Unfortunately condition $N \in \Omega(2^G)$ for better worst time estimate is quite hard.

Furthermore, there is still quite a few constrains which just ensure that players
are assigned properly to groups. Following model thus try to look at problem from
different perspective in order to simplify requried constrains.

\subsection{Dual model (used one)}
In this model there is met trade of between numbers of variables and numbers of values in domains.
We are going to assign groups to players which reduces number of variables significantly.

\mdef{}{ Lets define CSP model $M_c = \langle V_c,D_c,C_c \rangle$ such as:
	\begin{enumerate}[(i)]

        \item For each day we define variables for each player such as the variable of $j$-th player in $i$-th day determines group the player is in for that day.
            $$ V_c = \{V_{i,j} |  \forall i \in [D], \forall j \in [N]: V_{i,j} \text{ CSP variable }  \} $$
        \item Domain of each variable $V_{i,j}$ is set of numbers of each group $1,...,G$ player can be in. 
            $$ D_c = \{D_{i,j}| \forall V_{i,j} \in V_c: D_{i,j} = [G] \} $$
		\item In this model we need $3$ constrains defined below.
            $$ C_c = \{ C_1, C_2, C_3\} $$
		\begin{enumerate}
			\item To ensure condition \ref{groups-size} we need constrain $C_1$ ensuring that group assignment leds to 
			groups of equal size $K$. 
                \\
                $\forall i \in [D]: \forall g \in [G]:$
                $$|\{V_{i,j}| \exists j \in [N]: V_{i,j} = g \}| =  K$$
			\item The condition \ref{one-player} is taken for granted in this model, because each player in each day has assigned only one group.
			\item The condition \ref{once-per-day} is also taken for granted, because every player  in each day has assigned group.
			\item We still need to ensure condition \ref{player-pairs} with constrain $C_2$ requiring that each pair of player plays at most once.
                \\
                $\forall i' \neq i \in [D]: \forall k \neq l \in [N]:$ 
                $$V_{i,k} = V_{i,l} =>  V_{i',k} \neq V_{i',l} $$
			\item Optionaly we can add constrain $C_3$ reducing only solutions where days are accepted only in lexically ascending order - which reduces symetries.
                \\
                $\forall i < i' \in [D]:$ \\
                $(V_{i,1} \leq V_{i',1}) \land (V_{i,1} = V_{i',1} => V_{i,2} \leq V_{i',2}) \land ... \land (V_{i,1} = V_{i',1} \land ... \land V_{i,N-1} = V_{i',N-1}  => V_{i,N} < V_{i',N})$
		\end{enumerate}
	\end{enumerate}
}

\subsubsection{Worst case estimate}
For each day we assign groups to  $N$ players, which makes following estimate:

$$ G^{D*N} = 2^{D*N*\log_2(G)}.$$

\subsubsection{Worst case estimate $M_a$ vs $M_c$}
$$ 2^{D*N*\log_2(G)} < 2^{\log_2{(N)}*D*G*K}$$
$$ D*N*\log_2(G) < \log_2{(N)}*D*G*K $$
$$ N*\log_2(G) < \log_2{(N)}*G*K $$
Using remark from \ref{insight} $N = G*K$.
$$ N*\log_2(G) < \log_2{(N)}*N $$
$$ \log_2(G) < \log_2{(N)} $$
$$ G < N $$
Which holds, thus $M_c$ has better estimate than $M_a$.


\subsubsection{Worst case estimate $M_b$ vs $M_c$}
$$ 2^{D*N*\log_2(G)} < 2^{D*G*N}$$
$$ D*N*\log_2(G) < D*G*N$$
$$ \log_2(G) < G$$
Which holds, thus $M_c$ has better estimate than $M_b$.


\subsubsection{Conclusion}
This model gives best worst case estimate and has simpliest condition thus 
it is clear candidate for implementation, which is described in next section.

\section{CSP model $M_c$ implementation}
All the variables are stored in \textit{variables data structure} implemented as list
of days, where each days has $N$ variables determinig players group assignment.
For the purpouse of describing domain filtration algorithm of the 
\ccc{pair\_constrain} we define following notation.

\mdef{}{
\textit{Variables data structure}(VDS) is matrix $\mathbb{D}$ with $D \times N$ dimensions such as:
\begin{equation}
	\mathbb{D}_{i,j} = 
	\begin{cases*}
		\text{unbound}	& player $j$ in day $i$ does not have group assigned yet, \\
		g \in \{1,...,G\}        & player $j$ in day $i$ has assgned group $g$. 
	\end{cases*}
\end{equation}
}

\subsection{Group size constrain - \ccc{group\_size\_constrain}}
This constrain should satisfy condition \ref{groups-size}. For each day 
and each group constrain ensures that the same number of all assignment for
each group is present for each day. 

\subsection{Pairs constrain -- \ccc{pair\_constrain}}
This constrain should satisfy condition \ref{player-pairs}. Because this condition basically 
binds every pair of variables we have decided to implement that as custom global constrain
using \href{https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/The-Global-Constraint-Programming-Interface.html#The-Global-Constraint-Programming-Interface}{
The Global Constraint Programming Interface}. 

\subsubsection{Constrain data structures}
We set to wake up constrain every time arbitrary domain variable has changed.
Once our predicate is called because of change we have to identify, which 
variables has actually changed. For that purpouse we define
\textit{pair constrain state} and \textit{played record}.

\mremark{}{
In source code we define slang \textit{variable} is \textit{played}, 
which means \textit{variable} has changed from \textit{unbound} to \textit{grounded} \textit{variable}.
}

\mdef{}{
\textit{Pair constrain state}(PCS) is matrix $\mathbb{S}$ with $D \times N$ dimensions (represented as list of lists) such as:

\begin{equation}
	\mathbb{S}_{i,j} = 
	\begin{cases*}
		\text{ground} & variable is grounded, \\
		\text{var} & variable is unbound.
	\end{cases*}
\end{equation}
}

\mdef{}{
\textit{Played record}(PR) is matrix $\mathbb{P}$ with $D \times N$ dimensions (represented as list of lists) such as:

\begin{equation}
	\mathbb{P}_{i,j} = 
	\begin{cases*}
		\text{ground} & variable has been grounded, \\
		\text{none} & variable did not changed, \\ 
		\text{unground} & variable has became unbound .
	\end{cases*}
\end{equation}
}


\subsubsection{Psudo code algorithm}
Upon wake up constrain process following steps.

\begin{enumerate}
\item Gets previous PCS $\mathbb{S'}$ and current VDS $\mathbb{D}$.
\item Calculates new PCS $\mathbb{S}$ from current VDS $\mathbb{D}$.
\item Based on $\mathbb{S'}$ and $\mathbb{S}$ creates PR $\mathbb{P}$.
\item Base on $\mathbb{P}$ for each grounded variable finds invalid domain values of each variables.
\item For each variable calculate new domains.
\item Unifies action with new domains and new PCS $\mathbb{S}$ with output parameters.
\end{enumerate}

\subsubsection{Invalid domain values detection}
Lets assume we get notified that variable for $n$-th player in $p$-th day has been grounded. 
\mdef{}{Lets define following variables to simplify notation: 
\begin{enumerate}
\item $dp := \mathbb{D}_{p,*}$ \hfill day with notified grounded variable,
\item $\forall p' \neq p: d := \mathbb{D}_{p',*}$ \hfill arbitrary other day,
\item $I_{i,j}$ \hfill set of invalid domain values for variable in $i$-th day of $j$-th player.
\end{enumerate}
}

Following table illustrate which domains can be reduced by which type of reductions.
\begin{itemize}
\item o... denotes notified grounded variable
\item A... denotes variable whose domain can be reduced by A reduction
\item B... denotes variable whose domain can be reduced by B reduction
\item C... denotes variable whose domain can be reduced by C reduction
\end{itemize}
 
\begin{tabular}{
 l | c | c || c || c | c | r |}
\multicolumn{1}{l}{} & \multicolumn{1}{c}{$d_i$}  & $d_i$ & $d_n$ & \multicolumn{1}{c}{$d_i$} & \multicolumn{1}{c}{$d_i$} & \multicolumn{1}{r}{$d_i$} \\
\cline{2-7}
d & A & A & C & A & A & A \\
\cline{2-7}
d & A & A & C & A & A & A \\
\hline
\hline
dp & B & B & o & B & B & B \\
\hline
\hline
d & A & A & C & A & A & A \\
\cline{2-7}
d & A & A & C & A & A & A \\
\cline{2-7}
\end{tabular} 


\paragraph{Other day domains reduction -- A}
Add value $d_n$ to invalid set for $i$-th player in $p'$-th day.
$ \forall i \neq p \in [N]$ such as:
\begin{enumerate}[(i)]
\item $d_n \text{ grounded}$
\item $dp_i \text{ grounded}$
\item $d_i \text{ not grounded}$ \hfill variable whose domain can be reduced 
\item $dp_n = dp_i$ \hfill $n$-th and $i$-th player are in the same group in $p$-th day
\end{enumerate}
$$ I_{p',i} \cup \{ d_n \} $$

\paragraph{Played day domains reduction -- B}
Add value $dp_n$ to invalid set for $i$-th player in  $p$-th day.
$ \forall i \neq p \in [N]$ such as:
\begin{enumerate}[(i)]
\item $d_n \text{ grounded}$
\item $dp_i \text{ not grounded}$ \hfill variable whose domain can be reduced 
\item $d_i \text{ grounded}$ 
\item $d_n = p_i$ \hfill $n$-th and $i$-th player are in the same group in $p'$-th day
\end{enumerate}
$$ I_{p,i} \cup \{ dp_n \} $$


\paragraph{Player domain reduction -- C}
Add value $d_i$ to invalid set for $n$-th player in  $p'$-th day.
$ \forall i \neq p \in [N]$ such as:
\begin{enumerate}[(i)]
\item $d_n \text{ not grounded}$ \hfill variable whose domain can be reduced 
\item $dp_i \text{ grounded}$ 
\item $d_i \text{ grounded}$ 
\item $dp_n = dp_i$ \hfill $n$-th and $i$-th player are in the same group in $p$-th day
\end{enumerate}
$$ I_{p',n} \cup \{ d_i \} $$

Resulting algorithum thus for each notified grounded variable tries to apply all A, B, C reductions
to populate sets of invalid domain values. Together with this step is also done check whether
the grounded variables are valid. Using these invalid sets all possible domains are then reduced.
Based on the result the fail action or actions changing domain sets are returned.  

\subsection{Days symetry constrain }
To reduce day symetries we also provide solver variant, which searchs for 
only solutions with days assignment in lexically asecending order. To achieve this
we use built-in constrain \ccc{lex\_chain}.

\section{User manual}
Entire source code is present in file \ccc{golf-problem-solver.pl}.
There are basically two predicates one can be interested in:
\begin{itemize}
\item \ccc{golf} - solves golf problem with symetries of exchanged days removed by defining asscending lexical order of days,
\item \ccc{golf\_all} - solves golf problem with all (even symetric) solutions. 
\end{itemize}

There are following variants of these predicates with parameters description:
\begin{verbatim}
% golf_all(-DaysAttendance, +N, +K, +G, +D) :- 
% golf(-DaysAttendance, +N, +K, +G, +D) :- 
% golf_all(-T, -DaysAttendance, +N, +K, +G, +D, +Opt) :- 
% golf(-T, -DaysAttendance, +N, +K, +G, +D, +Opt) :- 
% T ... time of search in miliseconds
% N ... number of players
% K ... number of players in group
% G ... number of groups
% D ... number of days
% Opt ... labeling predicate options
\end{verbatim}

Example call can be as follows:
\begin{verbatim}
| ?- golf(T, X, 20, 4, 5, 4, []).
T = 20920,
X = [[1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5],[1,2,3,4,1,2,3,5,1,2,4,5,1,3,4,5,2,3,4,5],[1,2,3,4,2,1,4,5,3,4,5,1,4,5,2,3,5,1,3,2],[1,2,3,4,4,3,2,5,5,1,2,4,3,1,5,2,4,5,1,3]] ? 
yes

% formated X output
% 1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5
% 1,2,3,4,1,2,3,5,1,2,4,5,1,3,4,5,2,3,4,5
% 1,2,3,4,2,1,4,5,3,4,5,1,4,5,2,3,5,1,3,2
% 1,2,3,4,4,3,2,5,5,1,2,4,3,1,5,2,4,5,1,3
% ABCD | EFGH | IJKL | MNOP | QRST | 
% AEIM | BFJQ | CGNR | DKOS | HLPT | 
% AFLR | BEOT | CIPS | DGJM | HKNQ | 
% AJNS | BGKP | CFMT | DELQ | HIOR | 
\end{verbatim}

To simplify running more jobs and getting better output we have created
bash script \ccc{test.sh}. It automatically sets prologs print options
and formates result output and even converts result to table of sets 
as it is in problem definition \ref{table}. Lastly it saves log output into
file with name, metioning passed parameters, to log directory.

Script has following parameters:
\begin{verbatim}                                            
test.sh <solver-variant> [N K G D <labeling-opts-params> <variants-count-to-search>]
<solver-variant> := basic|day_symetries
\end{verbatim}                                            

\section{Tests}
Beside some really simple variants such as in predicate \ccc{test(X)} we ran 
solver with parameters as in original problem \ref{table}.

$$N=20, K=4, G=5, D=5 $$

Follows interesting part of logged solver output for variant which reduces 
symetries of days:

\begin{verbatim}
./logs/log-day_symetries-20-4-5-5-[]-10.txt

T = 4139770,
X = [[1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5],[1,2,3,4,1,2,3,5,1,2,4,5,1,3,4,5,2,3,4,5],[1,2,3,4,2,1,4,5,3,4,5,2,4,5,1,3,5,2,3,1],[1,2,3,4,3,4,5,2,4,1,3,5,2,4,5,1,5,1,2,3],[1,2,3,4,4,5,2,3,2,3,5,1,5,1,3,4,4,5,1,2]] ? 
1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5
1,2,3,4,1,2,3,5,1,2,4,5,1,3,4,5,2,3,4,5
1,2,3,4,2,1,4,5,3,4,5,2,4,5,1,3,5,2,3,1
1,2,3,4,3,4,5,2,4,1,3,5,2,4,5,1,5,1,2,3
1,2,3,4,4,5,2,3,2,3,5,1,5,1,3,4,4,5,1,2
ABCD | EFGH | IJKL | MNOP | QRST | 
AEIM | BFJQ | CGNR | DKOS | HLPT | 
AFOT | BELR | CIPS | DGJM | HKNQ | 
AJPR | BHMS | CEKT | DFIN | GLOQ | 
ALNS | BGIT | CHJO | DEPQ | FKMR | 
T = 4139820,
X = [[1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5],[1,2,3,4,1,2,3,5,1,2,4,5,1,3,4,5,2,3,4,5],[1,2,3,4,2,1,4,5,3,4,5,2,4,5,1,3,5,2,3,1],[1,2,3,4,3,4,5,2,4,1,3,5,2,4,5,1,5,1,2,3],[1,2,3,5,5,4,2,3,2,3,4,1,4,1,3,5,5,4,1,2]] ? 
1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5
1,2,3,4,1,2,3,5,1,2,4,5,1,3,4,5,2,3,4,5
1,2,3,4,2,1,4,5,3,4,5,2,4,5,1,3,5,2,3,1
1,2,3,4,3,4,5,2,4,1,3,5,2,4,5,1,5,1,2,3
1,2,3,5,5,4,2,3,2,3,4,1,4,1,3,5,5,4,1,2
ABCD | EFGH | IJKL | MNOP | QRST | 
AEIM | BFJQ | CGNR | DKOS | HLPT | 
AFOT | BELR | CIPS | DGJM | HKNQ | 
AJPR | BHMS | CEKT | DFIN | GLOQ | 
ALNS | BGIT | CHJO | FKMR | DEPQ | 
\end{verbatim}

Another par of logged solver output, which is not
reducing symetries, is as follows:

\begin{verbatim}
./logs/log-basic-20-4-5-5-[]-10.txt

T = 7714440,
X = [[1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5],[1,2,3,4,1,2,3,5,1,2,4,5,1,3,4,5,2,3,4,5],[1,2,3,4,2,1,4,5,3,4,5,2,4,5,1,3,5,2,3,1],[1,2,3,4,3,4,5,2,4,1,3,5,2,4,5,1,5,1,2,3],[1,2,3,4,4,5,2,3,2,3,5,1,5,1,3,4,4,5,1,2]] ? 
1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5
1,2,3,4,1,2,3,5,1,2,4,5,1,3,4,5,2,3,4,5
1,2,3,4,2,1,4,5,3,4,5,2,4,5,1,3,5,2,3,1
1,2,3,4,3,4,5,2,4,1,3,5,2,4,5,1,5,1,2,3
1,2,3,4,4,5,2,3,2,3,5,1,5,1,3,4,4,5,1,2
ABCD | EFGH | IJKL | MNOP | QRST | 
AEIM | BFJQ | CGNR | DKOS | HLPT | 
AFOT | BELR | CIPS | DGJM | HKNQ | 
AJPR | BHMS | CEKT | DFIN | GLOQ | 
ALNS | BGIT | CHJO | DEPQ | FKMR | 
T = 7714500,
X = [[1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5],[1,2,3,4,1,2,3,5,1,2,4,5,1,3,4,5,2,3,4,5],[1,2,3,4,2,1,4,5,3,4,5,2,4,5,1,3,5,2,3,1],[1,2,3,4,3,4,5,2,4,1,3,5,2,4,5,1,5,1,2,3],[1,2,3,5,5,4,2,3,2,3,4,1,4,1,3,5,5,4,1,2]] ? 
1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5
1,2,3,4,1,2,3,5,1,2,4,5,1,3,4,5,2,3,4,5
1,2,3,4,2,1,4,5,3,4,5,2,4,5,1,3,5,2,3,1
1,2,3,4,3,4,5,2,4,1,3,5,2,4,5,1,5,1,2,3
1,2,3,5,5,4,2,3,2,3,4,1,4,1,3,5,5,4,1,2
ABCD | EFGH | IJKL | MNOP | QRST | 
AEIM | BFJQ | CGNR | DKOS | HLPT | 
AFOT | BELR | CIPS | DGJM | HKNQ | 
AJPR | BHMS | CEKT | DFIN | GLOQ | 
ALNS | BGIT | CHJO | FKMR | DEPQ | 

\end{verbatim}

We can see that reducing symetries is really usefull, because 
compute time is nearly 2 times faster. However for smaller 
problems the difference is not that interesting.

We have also tried different labeling parametr options, however
default behaviour appeared to be the fastest one. You can found all the logs
in \ccc{logs} folder to see the difference in durations.
\end{document}