Consider the case where we want to design a mixed doubles tennis tournament. Mixed doubles means every team consist of one man and one woman. The idea is to have several rounds where we want try to to have players with and against many different players. We implement this by forbidding to play with another person more than once, and also forbid to play against another player more than once. An additional goal is to have teams of the same strength play against each other. I.e. we don’t want a very strong team play against a very weak team. This we do by minimizing the differences in team ratings.
Some data:
To summarize:
- We have 12 players: 6 male and 6 female.
- We have 3 rounds with 3 games (so 3 courts). So in each round we have 6 teams.
- Each player has a rating. For this exercise we just invent them using random numbers drawn from a uniform distribution.
We have a bunch of decision variables:
The central variable is team. This is binary variable indicating player \(p\) is assigned to team \(t\) during round \(r\). The derived variable game is integer valued automatically, so we declare it as just positive and set its upper bound to one. (It is not always clear this is a good approach – in some cases it is better just to declare as binary).
The first equations are easy:
In the last equation the \(ct_{c,t}\) mapping helps to find the two teams that play on court \(c\). The first two constraints should probably be rewritten as a single constraint using an extra set \(gender=\{male,female\}\).
The other equations in the model deal with:
- “play with” constraints.
- “play against” constraints. These two are essentially the result of a linearization of a product of binary variables.
- Ratings constraints.
- Anti-symmetry constraints. We can add some additional constraints to reduce the symmetry in the model.
The results look like:
We play badminton socially and are currently looking for a system like this to set games.
ReplyDeleteCurrently we use a few manual methods which mean someone has to spend time working out games and the biggest 'compliant' is that games are not varied enough, with the same partners or opponents appearing in game regularly.
There are a few differences to what you outline here, because it's social we don't know in advance who will attend.
Actually, the number of available players will vary throughout the time games are played, making things more difficult.
The priorities are:
- To keep games even (based on rating).
- Ensure all players are assigned teams as often as possible.
- Avoid players having the same partner and opponent if possible.
I'd love some advice on how we might use be able to achieve our goals
Thanks
This model can solve fast if the data set is not very large. Maybe check with your local university to see if this would be a suitable student project. This post is more about the mathematical modeling than about a canned application.
Delete