Back
 AJOR  Vol.11 No.6 , November 2021
Fair Scheduling Models for Doubles Group Competitions
Abstract: This paper gives integer linear programming models for scheduling doubles tennis group competitions. The goal is to build a fair and competitive schedule for all players. Our basic model achieves that for each player the average ranking of his partners in all matches is as close as possible to the average ranking of his opponents in all matches. One of the variations of the basic model provides that each matchup is fair and competitive. We also give models for the case when the number of players is 4n + 2, and thus one of the matches has to be singles. Our models were implemented and tested using optimization software AMPL. Computational results along with schedules for some typical situations are also given the paper.

1. Introduction

Problem description and solution methods

In recreational doubles tennis groups, each participant plays several doubles matches in a matchday. A matchday consists of several rounds. In each round, doubles teams are formed to play several doubles matches concurrently. Typically, a matchday is about 2 hours and consists of 2, 3, or 4 rounds, depending on the format and duration of matches. The match formats are determined by group organizers; each match could be just one full set, a short set with only six games plus a tie-break if necessary, or simply a time-limited incomplete set.

There might be different ways of forming the teams and scheduling the matches. An important consideration is to mix up the doubles teams so that each group member can have different partners and opponents. Other important considerations are making the matchups as competitive as possible and having a fair schedule for each member of the group. Building a matchday schedule that achieves all these goals at the same time is not a simple task for the group organizers. In this paper, we use integer linear programming models for building a fair and competitive matchday schedule.

The main goal of our models is to create a matchday schedule that is relatively fair for all members of the group. The fairness is based on rankings of the players that can be determined (by the group organizers) based on relative performances of the players in the group. Then fairness is defined as follows. For each player, the average ranking of his partners in all matches should be as close as possible to the average ranking of his opponents in all matches. The objective function of our basic integer programming model is to minimize the maximum deviation from this target. The constraints in the basic model provide a correct format for the matchday schedule and also make sure that each group member plays with different partners and opponents. The basic model, called Balanced Rankings model, is given in Section 2.

Variations of the basic model

An important consideration for organizing a matchday is making sure that each doubles match is fair and competitive by limiting the difference between the combined rankings of the two doubles teams playing the match. We create three different models where this condition is achieved by adding different types of constraints to the basic model of Section 2. Those three models, called Fair Matchup models, along with their comparative analysis are given in Section 3.

The basic model assumes that the number of players is a multiple of 4. But it is a common situation when the number of players who want to play in a given matchday is 4n + 2 for an integer n. Then it is not possible to have only doubles matches unless some people sit out in a round. A possible solution is to have n doubles and 1 single match in a round. In Section 4, we give a variation of the basic model for this situation.

Review of related literature

Scheduling of sporting events by mathematical techniques have been studied for many years. There are a number of surveys on the topic [1] - [6]. Most results are on scheduling of professional sports leagues [3] [5]. [7] gives solution methods for scheduling a recreational doubles tennis tournament. Their problem is close to ours but there are also significant differences. The problem in [7] has the following requirement. Each player partners with every other player exactly once and plays against every other player exactly twice. To satisfy the requirement, 4n − 1 rounds (and thus, 4n − 1 matches for each player) are needed for a tournament with 4n players. That format is used for a round-robin tournament. But it is not practical for recreational doubles groups playing only for 2 hours as we have in our problem. In this type of groups, each player normally plays at most 4 matches in a 2-hour matchday which is much smaller than 4n − 1 matches played in a round-robin tournament (normally, n is at least 2). In our work, we give criteria and models for scheduling the competitions with smaller number of matches in a fair and competitive way.

Time-efficiency of the models and computational results

The vast majority of decision variables in our models are binary, and thus solving the integer programming models might get slow for large number of players. But in Subsection 2.2 we show that the integrality requirements of most binary variables can be relaxed, thus making the models more time-efficient in practice.

The models were implemented and tested using optimization software AMPL. Outputs of the models for 8 and 10 players are included throughout the paper to better illustrate how the models work. The outputs include objective function values of the integer programs as well as specific matchday schedules for most relevant scenarios. Based on the computational results, we also give comparative analyses of the models for different combinations of parameters.

2. The Basic Balanced Rankings Model

Let N be the number of tennis courts available to the tennis group. The group has 4N players who concurrently play N doubles matches in those N courts. Let P be the set of the players. Let M be the number of rounds in a matchday. Thus, each player plays M doubles matches (See Table 2 in Section 2.3 for an illustration of a matchday schedule with 3 rounds played by a group of 8 players). The goal is to build a matchday schedule that specifies in which court each player plays in each round. To be more specific with court assignments when building the models, each court is considered to be a set of two half-courts which are the two opposite sides of the court. Thus, each player should be assigned to one of the 2N half-courts in each round.

The players in the group are ranked based on their past performances. They are assigned ranks from 1 to 4N, with 1 being the highest rank and 4N being the lowest rank. Let rank (p) be the ranking of player p. The main goal of this model is to achieve a matchday schedule with balanced rankings, that is, for each player the average ranking of his partners should be as close as possible to the average ranking of his opponents.

The rest of the section is organized as follows. Section 2.1 gives a detailed description of the model that solves the problem. In Section 2.2, we show how the model can be refined to make it more time-efficient in practice. Section 2.3 gives some computational results, including a matchday schedule which is an output of the model.

2.1. The Integer Linear Programming Model

Below we build the model by defining the variables and giving the objective function and all necessary constraints. First we give detailed explanations for the constraints, then summarize the whole model at the end of this subsection.

Variables.

We have the following set of binary variables.

1) Let xm,c,p be 1 if player p plays in half-court c in round m, and 0 otherwise.

2) Let sm,p,q be 1 if players p and q are in the same team in round m, and 0 otherwise.

3) Let om,p,q be 1 if players p and q are in opposite teams in round m, and 0 otherwise.

We also need the following two sets of variables for the balanced rankings constraints.

4) Let up be the average ranking of the partners of player p in all M matches.

5) Let vp be the average ranking of the opponents of player p in all M matches.

6) Finally, variable W represents the maximum difference between average same-team and opposite-team rankings for any player p:

W = max p P | u p v p | (1)

Objective function.

The objective function minimizes W, the maximum difference between average same-team and opposite-team rankings for any player p.

Minimize W

The expression for W given in (1) is nonlinear. To linearize it, the objective function is set to minimize just variable W while constraint (C1) below provides that W is equal to the right-hand side expression of (1) in any optimal solution.

Constraints.

Constraints (C1)-(C3) together with the objective function provide the ranking requirements of the model.

(C1) Linearizing the expression for W. We have the following two constraints for every player p,

W u p v p , W v p u p

These two constraints together imply that W max p P | u p v p | . But in any optimal solution we will have W = max p P | u p v p | since the objective function minimizes W, and W is not in any other constraint.

(C2) Same team average ranking constraint. This constraint connects variables up and sm,p,q, making sure that up is really the average ranking of the partners of playerp in all M matches. For any player p,

u p = m 1 , , M ; q P : q p r a n k ( q ) s m , p , q M

(C3) Opposite team average ranking constraint. This constraint connects variables vp and om,p,q, making sure that vp is really the average ranking of the opponents of player p in all M matches. For any player p,

v p = m 1 , , M ; q P : q p r a n k ( q ) o m , p , q 2 M

Constraints (C4) and (C5) provide that different sets of variables are properly connected to each other.

(C4) Connecting variables xm,c,p and sm,p,q. For any two players p and q, any round m, and any half-court c,

s m , p , q x m , c , p + x m , c , q 1

The constraint works the following way. Suppose players p and q both play in half-court c in round m. Then x m , c , p = x m , c , q = 1 , and the right-hand side of the constraint is 1 + 1 1 = 1 . Thus, s m , p , q 1 and as a binary variable it is forced to be 1; which means that players p andq are in the same team in round m. Note that if at least one of xm,c,p and xm,c,q is 0 then the right-hand side of the constraint is 0 or less, thus not forcing anything on sm,p,q.

(C5) Connecting variables xm,c,p and om,p,q. For any two players p andq, any round m, and any half-courts c and d which are the two opposite sides of the same court,

o m , p , q x m , c , p + x m , d , q 1

The constraint works the following way. Supposec andd are the two opposite half-courts of the same court, and players p and q play in c and d correspondingly in round m. Then x m , c , p = x m , d , q = 1 , and the right-hand side of the constraint is 1 + 1 1 = 1 . Thus, o m , p , q 1 and as a binary variable it is forced to be 1; which means that players p and q are in the opposite teams in round m. Note that if at least one of xm,c,p and xm,d,q is 0 then the right-hand side of the constraint is 0 or less, thus not forcing anything on om,p,q.

Constraints (C6)-(C9) provide that the matchday schedule has the correct format.

(C6) Two players in each half-court. For any round m and any half-court c,

p P x m , c , p = 2

This constraint provides that exactly two of the binary variables in the summation take value 1, and thus there are exactly two players in each half-court in any round.

(C7) Each player is in exactly one half-court in each round. For any round m and any player p,

c 1 , , 2 N x m , c , p = 1

This constraint provides exactly one of the binary variables in the summation takes value 1, and thus each player is in exactly one half-court in any round.

(C8) Each player with exactly one partner in each round. For any round m and any player p,

q P : q p s m , p , q = 1

This constraint provides exactly one of the binary variables in the summation takes value 1, and thus each player has exactly one partner in any round.

(C9) Each player with exactly two opponents in each round. For any round m and any player p,

q P : q p o m , p , q = 2

This constraint provides exactly two of the binary variables in the summation take value 1, and thus each player has exactly two opponents in any round.

In recreational tennis groups, it is also important to mix up the teams so that nobody plays with the same partner or against the same opponent too often. Constraints (C10) and (C11) provide that players have different partners and opponents.

(C10) Upper bound on the number of times having the same partner. First we define a parameter max_same which indicates the maximum number of times any two players can be on the same team in a matchday. Then we have the following constraint. For any two players p andq,

m 1 , , M s m , p , q max_same

(C11) Upper bound on the number of times having the same opponent. First we define a parameter max_opp which indicates the maximum number of times any two players can be on opposite teams in a matchday. Then we have the following constraint. For any two players p and q,

m 1 , , M o m , p , q max_opp

The model is summarized below.

Minimize W

Subject to

W u p v p , W v p u p (C1)

u p = m 1 , , M ; q P : q p r a n k ( q ) s m , p , q M (C2)

v p = m 1 , , M ; q P : q p r a n k ( q ) o m , p , q 2 M (C3)

s m , p , q x m , c , p + x m , c , q 1 (C4)

o m , p , q x m , c , p + x m , d , q 1 (C5)

p P x m , c , p = 2 (C6)

c 1 , , 2 N x m , c , p = 1 (C7)

q P : q p s m , p , q = 1 (C8)

q P : q p o m , p , q = 2 (C9)

m 1 , , M s m , p , q max_same (C10)

m 1 , , M o m , p , q max_opp (C11)

x m , c , p , s m , p , q , o m , p , q binary

u p , v p , W 0

2.2. Results for Making the Model More Time-Efficient

The following two results imply that the integrality constraints of some of the binary variables can be relaxed, thus making the model more time-efficient.

Theorem 1. If the binary requirements of variables sm,p,q are relaxed to 0 s m , p , q 1 then constraints (C4), (C6), (C7), (C8) will provide that sm,p,q takes only values 0 and 1 in any feasible solution.

Proof.

Suppose the binary requirements of variables sm,p,q are relaxed to 0 s m , p , q 1 . Consider player p* in round m*. We want to show that for any other player q, variable s m * , p * , q can only take values 0 or 1 in any feasible solution.

Constraint (C7), c 1 , , 2 N x m , c , p = 1 provides that player p* is in exactly one half-court in round m*. Suppose that half-court is c*. Then x m * , c * , p * = 1 .

Constraint (C6), p P x m , c , p = 2 provides that in round m*, there are exactly 2 players in half-court c*. One of the players is p*; suppose the other player is q*. Then x m * , c * , q * = 1 .

Consider constraint (C4) for m*, c*, p* and q*. The constraint implies that s m * , p * , q * x m * , c * , p * + x m * , c * , q * 1 = 2 1 = 1 . Hence s m * , p * , q * = 1 .

Now consider constraint (C8) for round m* and player p*, q P : q p s m * , p * , q = 1 . Since s m * , p * , q * = 1 and the summation in constraint (C8) is equal to 1, then s m * , p * , q = 0 for any other player q. o

Theorem 2. If the binary requirements of variables om,p,q are relaxed to 0 o m , p , q 1 then constraints (C5), (C6), (C7), (C9) will provide that om,p,q takes only values 0 and 1 in any feasible solution.

Proof.

Suppose the binary requirements of variables om,p,q are relaxed to 0 o m , p , q 1 . Consider player p* in round m*. We want to show that for any other player q, variable o m * , p * , q can only take values 0 or 1 in any feasible solution.

Constraint (C7), c 1 , , 2 N x m , c , p = 1 provides that player p* is in exactly one half-court in round m*; suppose that half-court is c*. Then x m * , c * , p * = 1 .

Suppose half-court d* is the opposite side of half-court c*. Constraint (C6) for round m* and half-court d*, p P x m * , d * , p = 2 provides that there are exactly 2 players in half-court d*. Suppose those two players are q* and q**. Then x m * , d * , q * = 1 and x m * , d * , q * * = 1 .

Consider constraint (C5) for round m*, courts c* and d*, players p* and q*. The constraint implies that o m * , p * , q * x m * , c * , p * + x m * , d * , q * 1 = 2 1 = 1 . Hence o m * , p * , q * = 1 . Similarly, consider constraint (C5) for round m*, courts c* and d*, players c* and d**. The constraint implies that o m * , p * , q * * x m * , c * , p * + x m * , d * , q * * 1 = 2 1 = 1 . Hence o m * , p * , q * * = 1 .

Now consider constraint (C9) for match m* and player p*, q P : q p o m * , p * , q = 2 . Since o m * , p * , q * = o m * , p * , q * * = 1 and the summation in constraint (C9) is equal to 2, then o m * , p * , q = 0 for any other player q. o

Theorems 1 and 2 imply that we can relax the binary requirements of s-variables and o-variables, thus making the model significantly more time-efficient in practice.

2.3. Computational Results

The model was tested for different combinations of parameters. The results for 8 players and 3 rounds and different combinations of max_same and max_opp are summarized in Table 1.

The results show that it is possible to have equal average rankings for a player’s partners and opponents if it is allowed to play against the same opponent twice (that is, max_opp = 2). When max_opp = 1 then the difference between average rankings of a player’s partners and opponents is 0.17.

As an example of a model output, we give the matchday schedule for max_same = 1, max_opp = 1 in Table 2. For the rest of the paper, to simplify the presentation of output results we assume that the player number is the same as his ranking.

3. Fair Matchup Models

The model of the previous section achieves fairness in the following sense. For each player, the average ranking of his partners in all matches is not much different from the average ranking of his opponents in all matches. But it does not provide a fair matchup in each match. The average ranking of a doubles team might be much higher than the average ranking of the opponent team. For example, in round 2 of Table 2 players ranked 2 and 3 play against players ranked 6 and 7. In this section, we give three variations of the basic model for fixing that problem. The variations are named Fair Matchup Models A, B, C and are presented in Subsections 3.1, 3.2, 3.3 correspondingly. Each of the models is followed by computational results.

3.1. Fair Matchup Model A: Pairing Highest and Lowest Ranked Players

Suppose a doubles match is played by four players p1, p2, p3, and p4 such that

Table 1. Summary of computational results for the Balanced rankings model.

Table 2. Matchday schedule for max_same = 1, max_opp = 1 (Balanced rankings model).

rank (p1) > rank (p2) > rank (p3) > rank (p4). Then the match would be relatively more competitive if p1 andp4 partner to form one of the doubles teams while p2 and p3 form the second team.

Modifications to the basic model

The following two constraints are added to the basic model of Section 2 to achieve the above requirement.

(F1) {p1, p2} and {p3, p4} cannot be the teams. For any round m and any four players p1, p2, p3, and p4 such that rank (p1) > rank (p2) > rank (p3) > rank (p4),

s m , p 1 , p 2 + o m , p 1 , p 3 + o m , p 1 , p 4 2

The constraint works the following way. If p1 and p2 are in the same team while p3 and p4 are in the opposite team then s m , p 1 , p 2 = o m , p 1 , p 3 = o m , p 1 , p 4 = 1 . But then the left-hand of the inequality would be 3, and the constraint would be violated. Thus the constraint prevents {p1, p2} and {p3, p4} being the two teams.

(F2) {p1, p3} and {p2, p4} cannot be the teams. For any round m and any four players p1, p2, p3, and p4 such that rank (p1) > rank (p2) > rank (p3) > rank (p4),

s m , p 1 , p 3 + o m , p 1 , p 2 + o m , p 1 , p 4 2

Similar to the logic of constraint (F1), this constraint prevents {p1, p3} and {p2, p4} being the two teams.

Summarizing, if any given match the four players arep1,p2, p3, and p4 such that rank (p1) > rank (p2) > rank (p3) > rank (p4), then constraints (F1) and (F2) together allow only {p1, p4} and {p2, p3} to be the two teams.

Computational results

Model A was tested for 8 players and 3 rounds. The results are summarized in row 2 of Table 3.

The numerical values in Table 3 are the optimal objective function values (when the model has a feasible solution). Compared to the basic model of Section 2 (row 1 of Table 3), the optimal values are higher for Model A because two new constraints (F1) and (F2) are added. There is no feasible solution for Model A when it is not allowed to have the same partner or opponent more than once (max_same = 1 and max_opp = 1). When that restriction is relaxed by allowing to have the same opponent twice (max_opp = 2), there is an optimal solution with objective function value 2. The optimal value is worse, 3.17 when it is

Table 3. Comparative results for the basic model, Model A, and Model B.

*The solution has exactly the same matchup in two different rounds.

allowed to have the same partner twice. The optimal value is slightly better, 1.67 when it is allowed to have both the same partner and the same opponent twice (but it is achieved by having exactly the same matchup in two different rounds which is not a desirable outcome). Thus, the combination of max_same = 1 and max_opp = 2 gives the most sensible schedule for Model A, with a relatively small optimal value and no repeated matchups. That schedule is given in Table 4.

3.2. Fair Matchup Model B: Top Two Ranked Players Cannot Be in the Same Team

Model A of the previous section makes the matches more competitive. But the original objective of minimizing the difference between partners’ and opponents’ rankings suffers in the result. For 8 players and 3 matches, it is increased from 0 to 2 when adding the competitiveness constraints of Section 3.1. A compromise solution would be relaxing the competitiveness restrictions the following way. The top two ranked players still cannot be in the same team but the players ranked one and three are allowed to be one of the teams. More specifically, we drop constraint (F2) from Model A and keep only (F1):

(F1) {p1, p2} and {p3, p4} cannot be the teams. For any match m and any four players p1, p2, p3, and p4 such that rank (p1) > rank (p2) > rank (p3) > rank (p4),

s m , p 1 , p 2 + o m , p 1 , p 3 + o m , p 1 , p 4 2

Computational results for Model B are given in row 3 of Table 3. Unlike Model A, Model B has a feasible solution for max_same = 1, max_opp = 1. For other combinations of max_same and max_opp, Model B achieves significantly better optimal values compared to Model A. The best optimal value 0.67 is achieved when max_same = 1 and max_opp = 2 (versus optimal value 2 for Model A); the corresponding matchday schedule is given in Table 5.

Table 4. Matchday schedule for Model A (max_same = 1, max_opp = 2).

Table 5. Matchday schedule for Model B (max_same = 1, max_opp = 2).

3.3. Fair Matchup Model C: Limiting the Difference between Combined Rankings of Two Teams

In this subsection, we suggest a different way for achieving competitive matchups. Model B of Section 3.2 still allows to have players ranked 1 and 3 to play against players ranked 2 and 8 which is not a sufficiently competitive and fair matchup. Even Model A of Section 3.1 allows to have players ranked 1 and 8 to play against players ranked 2 and 3, making the second team significantly stronger with combined ranking 5 versus the combined ranking 9 of the first team. To overcome this problem, we suggest to have a restriction which requires that the difference between the combined rankings of the two doubles teams in each matchup is not too big. Let T be an upper bound for that difference. The following set of constraints is needed to satisfy the requirement.

(F3) Upper bound on the difference between the combined rankings. For any round m and any four players p1, p2, p3, and p4 such that | ( rank ( p 1 ) + rank ( p 2 ) ) ( rank ( p 3 ) + rank ( p 4 ) ) | > T ,

s m , p 1 , p 2 + s m , p 3 , p 4 + o m , p 1 , p 3 2

The constraint works the following way. The left-hand side of the condition on playersp1, p2, p3, and p4 represents the absolute value of the difference between the combined rankings of teams {p1, p2} and {p3, p4}. The summation in the left-hand side of the constraint, s m , p 1 , p 2 + s m , p 3 , p 4 + o m , p 1 , p 3 is greater than 2 if and only if s m , p 1 , p 2 = s m , p 3 , p 4 = o m , p 1 , p 3 = 1 , that is, {p1, p2} and {p3, p4} are two teams playing against each other in round m. Thus, the constraint imposes the following requirement: if the difference between combined rankings of {p1, p2} and {p3, p4} is greater than the allowed upper boundT then {p1, p2} and {p3, p4} cannot be the two teams playing a match.

Model C (8 players and 3 rounds) was tested for different values of T and different combinations of max_same and max_opp values. The results are summarized in Table 6. The numerical values in the table are the optimal objective function values (when the model has a feasible solution).

Analysis of the computational results for Model C

Setting T to 0 or 1 is too restrictive, resulting in either no feasible solution or a high optimal value. On the other hand, T greater than 3 could result in one of

Table 6. Computational results for Model C.

*The solution has exactly the same matchup in two different rounds.

the teams being much stronger than the other. Thus, setting T to 2 or 3 could be a reasonable middle ground for achieving satisfactory results for all the goals of the model. Increasing max_same from 1 to 2 does not improve the optimal values; thus, it is better to set max_same = 1 to avoid having the same team in more than one match. When both max_same = 1 and max_opp = 1, that is, any two players can play against each other at most once, then setting T = 2 results in no feasible solution, hence T = 3 is the best choice. When max_same = 1 and max_opp = 2, that is, any two players can play against each other at most twice, then setting T = 3 does not improve much from T = 2; thus, T = 2 could be the best choice. Those two recommended combinations of values are highlighted in bold in Table 6, and the corresponding matchday schedules are given in Table 7 and Table 8.

Note also that if T is set to 3 (or less) then it does not let the top two ranked players to be in the same team, and thus constraint (F1) of Models A and B is automatically satisfied.

4. Models with both Doubles and Singles Matches

Normally, the number of players participating in doubles groups is a multiple of 4, and the models of the previous sections are designed for that case. But sometimes the number of people who would like to play in a particular matchday might be 4N – 2 for some integer N. In that case N – 1 doubles and 1 singles matches can be played concurrently. Below we modify the basic model of Section 2 for this new scenario. The new model is called Doubles + Singles Model.

As before, let N be the number of tennis courts available to the tennis group; the first N – 1 courts are designated for doubles matches, and court number N is designated for singles matches. As before, each doubles court is considered to be a set of two half-courts which are the two opposite sides of the court. In our

Table 7. Matchday schedule for Model C (T = 2, max_same = 1, max_opp = 2).

Table 8. Matchday schedule for Model C (T = 3, max_same = 1, max_opp = 1).

model, there is no need to explicitly consider half-courts for the singles court. The group has 4N – 2 players who concurrently play N – 1 doubles and 1 singles match in those N courts. Let P be the set of the players. Let M be the number of rounds in a matchday. The goal is to build a matchday schedule that specifies in which court each player plays in each match. Each player should be assigned either to play singles in court number N or to one of the 2 (N – 1) doubles half-courts if playing doubles.

Below we give an integer program for the Doubles + Singles Model by updating the set of variables and constraints of the basic model of Section 2.

Variables.

We keep all the variables defined in Section 2, but now those variables are defined only for the doubles courts and the doubles matches. For the singles matches, we need the following new sets of binary variables.

1) Let gm,p be 1 if player p plays singles in round m, and 0 otherwise.

2) Let hm,p,q be 1 if players p and q play singles against each other in round m, and 0 otherwise.

3) Letbp,j be 1 if player p plays exactly j singles matches in the matchday.

Note that the sets of binary variables defined above are related to each other. The connections between different sets of variables are given in constraints (S5) and (S6) below.

The Objective function is the same as in Section 2.

Minimize W

Constraints.

Constraint (C1) which together with the objective function provides the ranking requirements of the model stays the same.

Constraints (C2) and (C3) need to be changed. Recall that the denominators in (C2) and (C3) are the numbers of player p’s all doubles partners and opponents correspondingly. But if player p plays jp singles matches then the number of doubles partners should be changed from M to M jp, and the number of doubles opponents should be changed from 2M to 2 (M jp). In the result, we obtain the following two modified constraints (C2n) and (C3n).

(C2n) Same team average ranking constraint. This constraint connects variables up and sm,p,q, making sure that up is really the average ranking of the partners of player p in M-jp doubles matches. For any player p,

u p = m 1 , , M ; q P : q p r a n k ( q ) s m , p , q M j p

(C3n) Opposite team average ranking constraint. This constraint connects variables vp and om,p,q, making sure that vp is really the average ranking of the opponents of player p in M-jp doubles matches. For any player p,

v p = m 1 , , M ; q P : q p r a n k ( q ) o m , p , q 2 ( M j p )

But constraints (C2n) and (C3n) are nonlinear since jp is a variable quantity. However, (C2n) and (C3n) can be replaced with linear constraints (C2m) and (C3m) below, by using the bp,j variables defined earlier in this section.

(C2m) Same team average ranking constraints. For any playerp and for any possible number of singles matches j,

u p m 1 , , M ; q P : q p r a n k ( q ) s m , p , q M j K ( 1 b p , j ) (C2m_1)

u p m 1 , , M ; q P : q p r a n k ( q ) s m , p , q M j K ( 1 b p , j ) (C2m_2)

where K is a sufficiently large positive number (a possible choice is the sum of all player rankings).

The constraint works the following way.

First note that the left-hand sides of (C2m_1) and (C2m_2) are the same. Constraint (S4) given later in this section provides that for player p, bp,j = 1 for exactly one j 0 , 1 , , M .

If bp,j = 1, that is, player p plays exactly j singles matches, then the left-hand side of (C2m_1) and (C2m_2) is ³ 0 based on (C2m_1) and £ 0 based on (C2m_2). That could happen only if the left-hand side is exactly 0 which implies that up is equal to the average ranking of M-j doubles partners of player p, which was the goal of the constraint.

On the other hand, if bp,j = 0 then the left-hand side of (C2m_1) and (C2m_2) is ³ -K based on (C2m_1) and £ K based on (C2m_2). Thus, a sufficiently large value for K would not impose any restriction on the left-hand side.

(C3m) Opposite team average ranking constraint. For any player p and for any possible number of singles matches j,

v p m 1 , , M ; q P : q p r a n k ( q ) o m , p , q 2 ( M j ) K ( 1 b p , j ) (C3m_1)

v p m 1 , , M ; q P : q p r a n k ( q ) o m , p , q 2 ( M j ) K ( 1 b p , j ) (C3m_2)

where K is a sufficiently large positive number (a possible choice is the sum of all player rankings).

Constraint (C3m) works the same way as constraint (C2m). It provides that vp is equal to the average ranking of 2 (M-j) doubles opponents of player p.

Constraints (C4) and (C5) that connect variables xm,c,p , sm,p,q , and sm,p,q stay the same but are given only for doubles courts.

There are some changes in Constraints (C6)-(C9) which provide a correct tournament format. Constraint (C6) stays the same but is given only for doubles courts. The other constraints are modified the following way.

(C7m) Each player either plays singles or is in exactly one doubles half-court in each round. For any round m and any player p,

g m , p + c 1 , , 2 N x m , c , p = 1

This constraint provides that in any round, either gm,p = 1 (player p plays singles) or exactly one of the binary variables in the summation takes value 1 (player p is in exactly one doubles half-court).

(C8m) Each player with exactly one doubles partner in each round if not playing singles. For any round m and any player p,

q P : q p s m , p , q = 1 g m , p

The constraint works the following way. There are two possibilities.

If gm,p = 1, that is, player p plays singles in round m, then the summation in the left-hand side is 0. Thus all sm,p,q variables in the summation are 0, and player p does not have any doubles partner in round m.

If gm,p= 0, that is, player p does not play singles in round m, then the summation in the left-hand side is 1. Hence exactly one of the binary variables in the summation takes value 1, and thus player p has exactly one doubles partner in round m.

(C9m) Each player with exactly two opponents in each round if not playing singles. For any round m and any player p,

q P : q p o m , p , q = 2 ( 1 g m , p )

The constraint works the following way. There are two possibilities.

If gm,p = 1, that is, player p plays singles in round m, then the summation in the left-hand side is 0. Thus all om,p,q variables in the summation are 0, and player p does not have any doubles opponents in round m.

If gm,p = 0, that is, player p does not play singles in round m, then the summation in the left-hand side is 2. Hence exactly two binary variables in the summation take value 1, and thus player p has exactly two doubles opponents in round m.

Constraints (C10) and (C11) providing that players have different doubles partners and opponents stay the same.

The model also has new constraints specifically for singles matches.

Some players might prefer playing singles more than others. We define an input parameter MNSMp for each player p to indicate the maximum number of singles matches the player would like to play. Then we have the following constraint.

(S1) Maximum number of singles matches. For any player p,

m 1 , , M g m , p M N S M p

The summation in the left-hand side represents the total number singles matches played by player p, and that number cannot be more than MNSMp .

(S2) Any two players at most one singles match. For any playersp and q,

m 1 , , M h m , p , q 1

The constraint provides that at most one binary variable in the summation is 1, that is, any two players p and q play a singles match with each other at most once. It prevents having the same singles matchup happening more than once. Thus, a player who prefer playing more singles can play against different opponents.

To make singles matchups more competitive we need to provide that the ranking difference between the players of a singles matchup is not too big. To achieve that, first we define a new input parameter MRD_S which is the maximum ranking difference allowed between the players in a singles matchup. Then we need the following constraint.

(S3) Limit on ranking difference in each singles matchup. For any two players p and q such that | rank ( p ) rank ( q ) | > MRD _ S ,

m 1 , , M h m , p , q = 0

The constraint provides that if the absolute value of the ranking difference of the two players is bigger than the allowed upper limit MRD_S then all the binary variables in the summation are 0, that is, p and q do not play singles with each other.

The following constraint connects the bp,j variables for a given player.

(S4) Number of singles matches. For any player p,

j 0 , , M b p , j = 1

The constraint forces that exactly one binary variable in the left-hand side is 1. If that variable has index j then playerp will be playing exactly j singles matches.

The next two constraints provide that different sets of the singles variables are properly connected to each other.

(S5) Connecting variables gm,p and bp,j . For any player p,

j 1 , , M g m , p = j 0 , , M j b p , j

The constraint works the following way. The summation in the left-hand represents the total number of singles matches for player p since gm,p = 1 if player p plays singles in round m, and the summation is taken over all M rounds. Recall that constraint (S4) provides that for player p, variable bp,j = 1 for exactly onej. But then the summation in the right-hand side will be equal toj*1 = j for that particular j which is again equal to the total number of singles matches for player p, based on the definition of variable bp,j.

(S6) Connecting variables gm,p and hm,p,q . For any two players p and q, and any round m,

h m , p , q g m , p + g m , q 1

The constraint works the following way. Suppose players p and q play singles in round m. Then g m , p = g m , q = 1 , and the right-hand side of the constraint is 1 + 1 1 = 1 . Thus, h m , p , q 1 and as a binary variable it is forced to be 1; which means that players p and q play singles against each other in round m. Note that if at least one of gm,p and gm,q is 0 then the right-hand side of the constraint is 0 or less, thus not forcing anything on hm,p,q .

Summarizing, the Doubles + Singles Model is obtained by updating the set of constraints of the basic model of Section 2 in the following way. Constraints (C1), (C4), (C5), (C6), (C10), (C11) stay the same; constraints (C2), (C3) are replaced by (C2m), (C3m); constraints (C7)-(C9) are replaced by (C7m)-(C9m); new singles-specific constraints (S1)-(S6) are added.

The fair matchup constraints of Section 3 can also be added to the Doubles + Singles Model to achieve that each doubles match is relatively competitive and fair. Examples motivating that idea are given below.

Computational results and analysis.

We illustrate how the Doubles + Singles Model works by giving a solution for the following input: 10 players, 3 rounds, max_same = 1, max_opp = 1, maximum ranking difference in singles matches MRD_S = 2, and the following values for maximum number of singles matches for each player:

The following solution was obtained for the above input. The optimal objective function value (the maximum difference between average same-team and opposite-team rankings for any player p in doubles matches) is 0.75. The resulting matchday schedule is given in Table 9.

As can be seen from the matchday schedule, some doubles matchups are not competitive enough. For example, players ranked 1 and 3 play against players ranked 5 and 6 in Round 1; players ranked 4 and 5 play against players ranked 9 and 10 in Round 3. To fix the problem, the fair matchup constraints of Section 3 can be added. Recall that we gave three different sets of constraints in Fair Matchup Models A, B, and C. To illustrate how those constraints will affect the solution we also give the solution to the above example when the fair matchup constraints of Model C are added to the Doubles+Singles Model. The following (Model C specific) data is added to the above input. Let T = 3 be the maximum difference between the combined rankings of the two doubles teams in each matchup. In the output, the optimal value is 4. The resulting matchday schedule is given in Table 10.

The matchups in Table 10 are significantly more competitive than the matchups

Table 9. Matchday schedule for the Doubles + Singles Model.

Table 10. Matchday schedule for the Doubles+Singles Model when the fair matchup constraints of Model C are added.

in Table 9. But it is achieved at the cost of increasing the optimal value from 0.75 to 4. For example, the average ranking of the doubles partners of player 1 is ( 8 + 10 ) / 2 = 9 ; while the average ranking of the doubles opponents of player 1 is ( 3 + 5 + 2 + 10 ) / 4 = 5 . So the opponents of player 1 are significantly stronger than his partners. Thus, each model has its advantages and disadvantages. The tennis group organizers can decide which matchday schedule is more suitable for the group: the schedule of Table 10 with fair matchup constraints added or the schedule of Table 9 without those constraints.

5. Future Directions

Below we give some future directions grouped in three categories.

Other possible variations of the models

· An alternative way of organizing the tournament is the following. The doubles teams are staying the same, and the winning teams of the first round play against each other in further rounds. Then it is becoming even more important to form the teams and the matchups of the first round in a fair way.

· A common ranking system is simply having ranks 1, 2, …, 4n for the 4n players. That approach was adopted in our models and computational results. But in some doubles groups, many members might have roughly the same level of tennis skills. In that case a different ranking system can be used to reflect the relative levels of the players more accurately. For example, the NTRP ratings of the USTA (United States Tennis Association) can be used.

· Another condition that might be taken into account when building the schedules is the following. Some group members play well (or the opposite, do not play well) with each other because of their styles of play. Thus, each member might have a preference list of other members who he would like to be partners with.

Extending the models to other sports

The models can be extended to other related sports where recreational doubles groups are common (badminton, table tennis, card games). The format and the criteria of our models might be applicable to the related sports; but each sport might also have a specific set of conditions and criteria that should be taken into account when building the models. Fair scheduling based on team rankings can also be used in those professional sport events where the tournament format is relatively close to our problem.

Alternative methods for solving the scheduling problems

Our solution method, integer programming guarantees to obtain optimal solutions. But integer programming might be computationally slow for large size of problems. It would be interesting to see if it is possible to build matchday schedules using combinatorial techniques. Developing heuristic techniques that do not guarantee optimal solutions but might be computationally fast is another direction.

Cite this paper: Melkonian, V. (2021) Fair Scheduling Models for Doubles Group Competitions. American Journal of Operations Research, 11, 338-356. doi: 10.4236/ajor.2021.116021.
References

[1]   Dinitz, J.H., Froncek, D., Lamken, E.R. and Wallis, W.D. (2006) Scheduling a Tournament. In: Colbourn, C.J. and Dinitz, J.H., Eds., Handbook of Combinatorial Designs, CRC Press, Boca Raton.

[2]   Easton, K., Nemhauser, G. and Trick, M. (2004) Sports Scheduling. In: Leung, J.T., Ed., Handbook of Scheduling, CRC Press, Boca Raton.

[3]   Kendall, G., Knust, S., Ribeiro, C.C. and Urrutia, S. (2010) Scheduling in Sports: An Anno-tated Bibliography. Computers and Operations Research, 37, 1-19.
https://doi.org/10.1016/j.cor.2009.05.013

[4]   Rasmussen, R.V. and Trick, M.A. (2008) Round Robin Scheduling: A Survey. European Journal of Operational Research, 188, 617-636.
https://doi.org/10.1016/j.ejor.2007.05.046

[5]   Ribeiro, C.C. (2012) Sports Scheduling: Problems and Applications. International Transac-tions in Operational Research, 19, 201-226.
https://doi.org/10.1111/j.1475-3995.2011.00819.x

[6]   Wright, M. (2009) 50 Years of OR in Sport. Journal of the Operational Research Society, 60, 161-168.
https://doi.org/10.1057/jors.2008.170

[7]   Salassa, F. and Della Croce, F. (2017) The Social Doubles Tournament Problem. Proceed-ings of MathSport International Conference 2017, Padua, Italy, 320-329.

 
 
Top