Thursday, March 3, 2016

More Tennis Scheduling

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:

image 

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:

image

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:

image

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:

image