How to minimize the number of breaks in sports scheduling?

Question

I have the following sports scheduling problem.

For $n$ teams and $m$ rounds, I define the binary decision variable

$$ x_{i,j,s} = \text{1 if team $i$ plays at home against team $j$ at round $s$, 0 otherwise}. $$

and the constraints:

$$ \begin{align} x_{i,i,s} &= 0\quad \forall i = 1,\ldots, n, s = 1,\ldots, m \tag{1} \\ \sum_{j=1}^{n} x_{i,j,s} + x_{j,i,s} &= 1 \quad \forall i=1,\ldots,n, s = 1,\ldots,m \tag{2} \\ \sum_{s=1}^{m} x_{i,j,s} + x_{j,i,s} &= 1 \quad \forall i,j=1,\ldots,n, i \neq j \tag{3} \\ \end{align} $$

(1) ensures that no team plays againts itself, (2) that the match is either at team $i$'s home or at team's $j$ and (3) enforces that each team plays against the other teams exactly once.

I'd like to minimize the number of breaks. That is, if team $i$ plays at home for two consecutive rounds, it has a break. The same holds true for two consecutive away games. How can I minimize the number of breaks?

Answer 1

If I understood you correctly, you could do it like this (assuming that $n$ is even and $m = n-1$)

First, add the binary variables

$$ \begin{align} h_{is} &= \begin{cases} 1, &\text{if team $i$ plays at home in round $s$ and $s-1$}, \\ 0, &\text{otherwise}, \end{cases} \\\\ % a_{is} &= \begin{cases} 1, &\text{if team $i$ plays away in round $s$ and $s-1$}, \\ 0, &\text{otherwise} \end{cases} \end{align} $$

for all teams $i = 1, \ldots, n$ and rounds $s = 2, \ldots, m$.

In order to count the number of breaks, we need to formulate the following if-then constraints

$$ \begin{align} \sum_{j=1}^{n} x_{i,j,s-1} + x_{i, j, s} &= 2 \implies h_{i,s} = 1, \quad\forall i=1,\ldots,n, s=2,\ldots,m,\\ \sum_{j=1}^{n} x_{j,i,s-1} + x_{j, i, s} &= 2 \implies a_{i,s} = 1, \quad\forall i=1,\ldots,n, s=2,\ldots,m.\\ \end{align} $$

This can be done as follows:

$$ \begin{align} \sum_{j=1}^{n} x_{i,j,s-1} + x_{i,j,s} &\leq 1 + h_{i,s} \quad\forall i=1,..,n, s=2,...,m, \\ \sum_{j=1}^{n} x_{j,i,s-1} + x_{j,i,s} &\leq 1 + a_{i,s}, \quad\forall i=1,...n, s=2,...,m. \end{align} $$

Consequently, we can minimize the number of breaks by setting the objective function

$$ \min \quad \sum_{i=1}^{n} \sum_{s = 2}^{m} h_{i,s} + a_{i,s} . $$

Answer 2

joni's answer is correct. However, this formulation will not allow you to find an optimal solution for anything more than 10-12 teams, even without any additional typical sports scheduling constraints. If you aren't using a commercial solver, the limit is even lower.

There is an excellent book about round robin scheduling by Dirk Briskorn. It is a must-read if you are interested in sports scheduling: https://www.springer.com/gp/book/9783540755173

There are chapters about theoretical limits of number of breaks and also suggests alternative methods that are worth looking into. If your main goal is to minimize the number of breaks and you don't have too many side constraints, I suggest you take a look at the "first-break-then-schedule" method.

Btw. in reality, none of the methods that you will find in literature are powerful/ sophisticated enough to solve larger (>20 teams) league scheduling problems. The methods that are used in reality are mostly trade secrets of the companies that do this type of work. Nevertheless, Briskorn's book is a good starting point and contains many valuable references to other papers and publications.