Heuristic for Tournament Scheduling

Question

I am holding a bi-yearly tournament in my city, for which I want to write a program that gives me (nearly-)optimal pairings, and waiting time. The setup is as follows:

-Up to 42 groups of 2 persons each.
-3 groups will be paired to be one team
-a game is played between 2 teams (6 groups) and takes 20 minutes
-3 games will be played at the same time, there will be 12 rounds of 3 games
-Every group has the same amount of games
-after every game, the teams change
-What I want to optimize: 
 minimize the amount of times a group gets put in a team with another group 
 they have already played with (if they played against them it is ok)
 Bonus: Minimize the games a group has to wait until their next game 
 (Since only 3 games can be played at once (so 6x3 = 18 groups), there are a lot of 
 groups who have to wait for the next round of games.)

I want the program to give me the pairings of the groups and a schedule, if possible. I am giving the exact numbers, because if it can't be done in polynomial time, but the instance is small enough so exponential time does not matter too much, it is fine with me. The solution does not have to be optimal, but should be close.

What is a good algorithm or heuristic for my problem?

Answer 1

I would suggest that you use an integer linear programming (ILP) solver or a SAT solver. This will probably be easier to formulate as ILP, so start there.

Let's check whether it is possible to ensure that no group ever gets teamed up with another group more than once. (We'll ignore the bonus condition.) Define a zero-or-one integer variable $x_{g,t,r}$, with the intent that $x_{g,t,r} = 1$ if group $g$ plays in team $t$ during round $r$, and $x_{g,t,r} = 0$ otherwise. Now we can write some linear inequalities to capture the constraints on a valid solution:

• $0 \le x_{g,t,r} \le 1$ ensures that each $x_{g,t,r}$ is zero or one.

• $\sum_g x_{g,t,r} = 3$ ensures that exactly 3 groups are assigned to each team in each round.

• $\sum_t x_{g,t,r} \le 1$ ensures that no group is assigned to more than one team in any given round.

• Arbitrarily choose 36 groups to play 5 games; for those groups $g$, the linear equality $\sum_{t,r} x_{g,t,r} = 5$ ensures they will play 5 times. The other 6 groups will play 6 games; for them, enforce the linear inequality $\sum_{t,r} x_{g,t,r} = 6$.

• For each pair of groups $g,g'$, we enforce the linear inequality $x_{g,t,r} + x_{g',t,r} + x_{g,t',r'} + x_{g',t',r'} \le 3$ for all $t,r,t',r'$; this ensures that $g,g'$ never play together on the same team more than once.

Feed this system of inequalities to an ILP solver. If it has a feasible solution, then you have found a valid schedule for your tournament.

If it has no feasible solution, next check whether there's a feasible tournament where no group ever gets teamed up with any other group more than twice. Do this by replacing the last set of inequalities above with the following:

• For each pair of groups $g,g'$, we enforce the linear inequality $x_{g,t,r} + x_{g',t,r} + x_{g,t',r'} + x_{g',t',r'} + x_{g,t'',r''} + x_{g',t'',r''} \le 5$ for all $t,r,t',r',t'',r''$; this ensures that $g,g'$ never play together on the same team more than twice.

If this doesn't have a feasible solution, check whether there's a way to do it where no group ever gets teamed up with any other group more than three times. Do a linear search until you find the best solution.

Once you've found the best solution, now you can try to handle the bonus condition. Let's say you want to see whether there's a way to do it where no group gets teamed up with another group more than once, and (here's the bonus condition:) no group has to wait more than three games. The bonus condition is easy to enforce: for each $r$, simply add the linear inequality $\sum_t x_{g,t,r} + \sum_{t'} x_{g,t',r+1} + \sum_{t''} x_{g,t'',r+2} \ge 1$. Now test whether that's feasible. Of course, you can vary the waiting time (it doesn't have to be three games) to find the smallest waiting time possible.

I'd expect this might find a solution to your problem. Modern ILP solvers are surprisingly good at solving many ILP instances, if there is sufficient structure -- and in this case I suspect there might be enough structure that off-the-shelf ILP solvers might work well.

There are variations possible to speed up the ILP solver, but I suspect that this straightforward formulation might just work with no tweaks or optimizations needed. Give it a try! It shouldn't be too hard to test out and see if it works.

Answer 2

You want to choose 36 games so you have 216 group slots to fill from 42 groups so your limitation of 'Every group has the same amount of games' makes your problem infeasible because 216 is not divisible by 42.. In contrast many groupings/games seem to satisfy everything else so yes you have room for good or even optimal heuristics (if your infeasibility is lifted).

More good news is that looking at your problem this way i.e. slots to fill for your end result 'games' -which is your lowest dimension- probably makes the problem quite solvable. (If you looked at it from the all possible games perspective you would be looking at 65,889,460 possible games and their permutations/scheduling for your delay part)

Even more good news: your delay constraint is satisfied well by having each team wait the same amount rounds (minimum delay equals uniform delay - otherwise if a team waits less the wait is paid by another team maximizing the minimum delay) This gives us a fast heuristic - no need to run NP-hard exhastive solution on scheduleing/permutations.

Even better news: I am giving you a sort of heuristic to look at and solve this extremely fast! Looks like following this way you can get a lot of heuristics for your problem due to the large feasible space as outlined above so here is how you would go about it:

So first let's lift the infeasibility by increasing your maximum number of groups to 54. You can just have 42 if you like as your requirement with the same algo but the equal games will never work as aforementioned.

Now schedule your first 3 rounds (STEP=1) Groups 1 ...54 in a row meaning Game 1 is Team of Groups 1 2 and 3 vs 4 5 and 6, Game 2 is 7 6 and 8 vs 9 10 and 11 and so on until 54

Now for STEP=2 schedule your next 3 rounds (why 3 at a time? because 3 is uniform delay ensures min max delay per group -see note above) Replace each Group by the Group + 3*Group modulo 55 so looking at them in a row your Round 4 becomes 4 8 and 12 vs 16 20 and 24 and so on. For example Group 1 will play with 52 and 5 against 9 13 and 17

Now for STEP=3 schedule your next 3 rounds Replace each Group + 3 * Group modulo 55 again (using group numbers from the previous round) For example your Round 7 has 16 32 and 48 vs 9 25 and 41 and Group 1 will play with 17 and 33 vs 49 10 and 26

Now for STEP=4 schedule your final 3 rounds (12 rounds scheduled after this step) Do the same as above! So Round 10 has 9 18 and 27 vs 36 45 and 54. Group 1 will play with 10 and 19 vs 28 37 and 46

Of course the above is a loop so you can have as many rounds/groups as you want (or your numbers allow)

Now for sanity check that your constrains are all met by the scheduling heuristic provided (I only checked a few seems ok if not just change the modulo equation to include more variables STEP, Round, Game number etc - but again due to your large feasibility space this simple equation seems to also work, replace it just to get different schedules if you want more than one - although with one schedule you can schedule any tournament per note 2 below)

NOTE 1: I have the whole schedule here for now but it is probably too much to post.

NOTE 2: You can use the same schedule every time (just assign Group numbers to people and your new schedule is done each time)

NOTE 3: You seem to have room for even more groups or rounds if you want. To find out just continue the loop above until one of your constrains is not met.