Optimizing a round-robin tournament schedule

Question

I need to invent an algorithm to optimize a specific tournament schedule.

There are 10 teams playing duels against each other in a full round-robin tournament (45 duels total). I need to schedule exactly 15 days of tournament, 3 duels per day.

So, on each day we need to call 3, 4, 5 or 6 teams to the venue. E.g. if we have scheduled duels A-B, A-C, B-C, we need to call only teams A, B and C. If we've scheduled duels A-B, C-D, D-E, we need to call teams A, B, C, D, E for that day.

Tournament organizers strongly prefer not to call a team to the venue to play only one duel that day. Let's say that cost of a schedule is the sum of number of teams called to the venue each day. I need to minimize that cost. Obviously, a lower bound is 45, because we cannot call less than three teams to have tree duels. But I think that 45 is not achievable.

A bruteforce approach of iterating over all possible schedules doesn't seem feasible. I'm looking for some other approach.

Answer 1

This sounds like a good candidate to use operations research style techniques, e.g., an integer linear programming (ILP) solver.

Let $x_{d,t}$ be a zero-or-one variable, that is 1 iff team $t$ plays on day $d$. Let $y_{d,t,u}$ be a zero-or-one variable, that is 1 iff team $t$ plays team $u$ in one of the duels on day $d$ (we treat $y_{d,t,u}$ as identical to $y_{d,u,t}$). We have the following constraints:

• Three duels per day: $\sum_{t,u} y_{d,t,u} = 3$ for each $d$ (where the sum is over $t,u$ such that $t<u$).

• Round robin format: $\sum_{d} y_{d,t,u} = 1$ for each $t,u$ such that $t<u$.

• $x$/$y$ consistency: $x_{d,t} \le \sum_{u} y_{d,t,u}$ and $x_{d,t} \ge y_{d,t,u}$ for each $u$.

• $0 \le x_{d,t} \le 1$ and $0 \le y_{d,t,u} \le 1$.

Finally, minimize $\sum_{d,t} x_{d,t}$, which counts the sum of the number of teams to the venue each day.

If the ILP solver is able to finish within the time available, it should give you the best possible schedule. It requires 825 variables and a few thousand linear inequalities, which might be within the realm of what is solvable by an off-the-shelf ILP solver. If not, you can set a timeout and ask the ILP solver to give you the best solution it could find within the time available.