Doubles Round Robin Sorting Algorithm

Question

Background: I have a group of 6 guys that get together and play pickleball every week. We play 2v2 and 2 players sit each game. We play 2 sets of 6 games each week (12 total games) - in each set, each player plays 4 games, and sits for 2 games. At the end of each set, each player totals up the amount of points he scores, and we have a winner.

Anyway, I worked out all the combinations of games for 6 people for playing doubles. There are a total of 45 unique games that could be played, where every combination of partners would play every other combination of partners. I would like to come up with a schedule to play all 45 of these games across 4 sessions of 2 sets each for a total of 8 sets (the final 3 games in the last set can be arbitrary since 6x8=48, and there are only 45 unique games).

The problem comes in with determining the order of the games, such that following criteria is met, for each of the sets of 6 games:

1. Each player plays 4 games, and sits for 2 games.
2. No player sits for 2 consecutive games.
3. Each player partners with a different partner every game. (i.e. no 2 players partner more than once per set).

Where I could use help is figuring out the algorithm to come up with the optimal order of games. With 45 factorial possible orders ~1e56...it's too many to brute force. Any advice would be appreciated.

All the combinations for players A, B, C, D, E, and F:
T1  T2  Bye
AB  CD  EF
AB  CE  DF
AB  CF  DE
AB  DE  CF
AB  DF  CE
AB  EF  CD
AC  BD  EF
AC  BE  DF
AC  BF  DE
AC  DE  BF
AC  DF  BE
AC  EF  BD
AD  BC  EF
AD  BE  CF
AD  BF  CE
AD  CE  BF
AD  CF  BE
AD  EF  BC
AE  BC  DF
AE  BD  CF
AE  BF  CD
AE  CD  BF
AE  CF  BD
AE  DF  BC
AF  BC  DE
AF  BD  CE
AF  BE  CD
AF  CD  BE
AF  CE  BD
AF  DE  BC
BC  DE  AF
BC  DF  AE
BC  EF  AD
BD  CE  AF
BD  CF  AE
BD  EF  AC
BE  CD  AF
BE  CF  AD
BE  DF  AC
BF  CD  AE
BF  CE  AD
BF  DE  AC
CD  EF  AB
CE  DF  AB
CF  DE  AB

Tried writing a brute force algorithm in Excel VBA...seems like it was going to take forever to run.

Answer 1

You can solve this with an integer programming model. I will omit the objective function, since any feasible solution produces a viable schedule. You might give some thought to whether there is a criterion that would let you choose among viable schedules.

First, we define some sets:

$P=$ set of all players ($\vert P\vert=6$)

$G=$ set of all games ($\vert G\vert=45$)

$S=$ set of slots for games ($\vert S\vert=48$), with 12 slots in each week

$S_{0}\subset S=$ set of slots that start a set (so $S_{0}=\left\{ 1,7,\dots,43\right\} $)

$S_{1}\subset S=$ set of slots followed by another slot in the same set (so $S_{1}=\left\{ s\in S:6\not|\:s\right\} $)

$T=$ set of teams (pairs of players) ($\vert T\vert=15$)

Next, we define a couple of parameters:

$\pi_{p,g}=1$ if player $p$ plays in game $g$, else 0

$\tau_{t,g}=1$ if team $t$ is together in game $g$, else 0

We have the following binary variables:

$x_{g,s}=1$ if game $g$ is scheduled into slot $s$, 0 otherwise

Now come the constraints.

Each game is scheduled at least once and at most twice: $$1\le\sum_{s\in S}x_{g,s}\le2\quad\forall g\in G$$

Each slot is filled once: $$\sum_{g\in G}x_{g,s}=1\quad\forall s\in S$$

Each player plays four of six games within a set: $$\sum_{g\in G}\pi_{p,g}x_{g,s}+\sum_{g\in G}\pi_{p,g}x_{g,s+1}+\cdots+\sum_{g\in G}\pi_{p,g}x_{g,s+5}=4\quad\forall p\in P,\forall s\in S_{0} $$

No player sits for two consecutive games:$$\sum_{g\in G}\pi_{p,g}x_{g,s}+\sum_{g\in G}\pi_{p,g}x_{g,s+1}\ge1\quad\forall p\in P,\forall s\in S_{1}$$

No team plays more than once in a set:$$ \sum_{g\in G}\tau_{t,g}x_{g,s}+\sum_{g\in G}\tau_{t,g}x_{g,s+1}+\cdots+\sum_{g\in G}\tau_{t,g}x_{g,s+5}\le1\quad\forall t\in T,\forall s\in S_{0}$$

Addendum: I coded this in Java using CPLEX 22.1 to solve the MIP, and got what I assume is a valid schedule in about one second. Also, I believe you could just as well use a constraint programming model rather than an IP model.

Addendum 2: Here is the solution my code obtained.

Day 1, Set 1:

AB vs. CD (bye: EF)
AE vs. CF (bye: BD)
BD vs. CE (bye: AF)
AD vs. EF (bye: BC)
BC vs. DF (bye: AE)
AF vs. BE (bye: CD)

Day 1, Set 2:

AE vs. BF (bye: CD)
AC vs. DE (bye: BF)
AF vs. BD (bye: CE)
BE vs. CF (bye: AD)
AD vs. BC (bye: EF)
CD vs. EF (bye: AB)

Day 2, Set 1:

AB vs. EF (bye: CD)
AC vs. DF (bye: BE)
BE vs. CD (bye: AF)
AD vs. CF (bye: BE)
BF vs. DE (bye: AC)
AE vs. BC (bye: DF)

Day 2, Set 2:

CF vs. DE (bye: AB)
AC vs. BF (bye: DE)
CE vs. DF (bye: AB)
AE vs. BD (bye: CF)
AF vs. BC (bye: DE)
AD vs. BE (bye: CF)

Day 3, Set 1:

AD vs. CE (bye: BF)
BF vs. CD (bye: AE)
AC vs. BE (bye: DF)
AF vs. DE (bye: BC)
AB vs. CF (bye: DE)
BD vs. EF (bye: AC)

Day 3, Set 2:

AC vs. BD (bye: EF)
AE vs. DF (bye: BC)
BF vs. CE (bye: AD)
AF vs. CD (bye: BE)
AB vs. DE (bye: CF)
BC vs. EF (bye: AD)

Day 4, Set 1:

AE vs. CD (bye: BF)
AD vs. BF (bye: CE)
AB vs. CE (bye: DF)
BE vs. DF (bye: AC)
AC vs. EF (bye: BD)
BD vs. CF (bye: AE)

Day 4, Set 2:

AB vs. DF (bye: CE)
AF vs. CE (bye: BD)
BC vs. DE (bye: AF)
AE vs. CF (bye: BD)
AD vs. BE (bye: CF)
BF vs. CD (bye: AE)

Addendum 3: It belatedly occurred to me that we might want to add a constraint saying the 45 possible games must occur once each among the first 45 slots, meaning that any repeated games must occupy the last three slots (in case we want to cut the last day short and not play those three repeated games). In the IP model, this just adds the constraint $$\sum_{s\in \hat{S}} x_{g,s} = 1 \quad\forall g\in G$$where $\hat{S}\subset S$ consists of the first 45 slots.