Create balanced tennis rounds

Question

We are a group of 20 people and we like to go play 2 vs 2 tennis matches. Each of us plays one match each round and we do 5 rounds in total, so everyone plays 5 matches. Matches have two restrictions:

• Everyone has a different level (from 1 to 5), so the matches must be balanced: two players with levels 5 and 5 shoulnd't be matched with two levels 1. So between the two teams, the difference in level must be lower or equal to 1.5.
  Ej.: level 1.5 and level 2 vs level 2 and level 2.5. The difference in level between teams is 1 so the match is accepted.
• If two players play together in one match, they must not play toghether again in the following rounds.

I managed to create a python script that does the specified above, but it takes about 20 minutes to finish depending on the level of the people :/. What I do is shuffle the list with every one in it, break it into 5 lists of 4 people, check if conditions are satisfied and repeat for every round.

I tried modeling the problem to solve it with linear programming (LP) but I don't know which is my function to optimize to begin with... Any ideas on how to do this with or without LP?

Thanks in advance!

Answer 1

You could use a dummy objective or even try to minimize the max of the difference in levels.

My MIP model is not completely trivial, but it solves quite fast (about a second or so using a commercial solver).

The results look ok at first sight:

I assumed two players cannot be in the same team more than once. I.e. not just in the same game. That is in my case you can play against another player more than once.

A more complex example can be found here.