Maximally unique beach volleyball games

Question

There are 24 players, 12 men and 12 women. A team is a set of 1 man and 1 woman. A (beach volleyball mixed) game is a set of 2 different teams, i.e. players are unique in those teams.

Let's denote men from 1 to 12 and women from A to L. 1A2B is a game example, man 1 with woman A play versus man 2 with woman B. A round is a set of 6 unique games, i.e. players are unique in those games. For example the first round can be:

1A2B
3C4D
5E6F
7G8H
9I10J
11K12L

We'd like to have as unique games as possible, i.e. maximize the unique partners and enemies a player has during games. How to generate 5 more rounds?

If it's not possible to generate 5 more rounds with totally unique games, we give more priority to the unique partners than enemies: a penalty for repeated partner is 2, a penalty for repeated opponent is 1. Here is the scoring script and exemplary invocation.

For example the next 5 rounds could be the same as the first one, but the uniqueness score would be very low, -480, since 24 players would repeat partners (-2) and both opponents (-1 and -1) in 5 rounds, so 5 times -96.

Answer 1

Here's a solution with no repeats, obtained via integer linear programming:

1A2B 3C4D 5E6F 7G8H 9I10J 11K12L
1D9K 2C10L 3E11H 4F12G 5A8I 6B7J
1H5L 2F11J 3B10G 4I6K 7A12D 8C9E
1E12J 2D5G 3A6L 4B9H 7C11I 8F10K
1C6G 2H12I 3J5K 4A10E 7F9L 8B11D
1F3I 2E7K 4J8L 5B12C 6D10H 9A11G

Let $R$ be the set of rounds, let $M$ and $W$ be the sets of men and women, and let $$Q=\{(m_1,w_1,m_2,w_2)\in M \times W \times M \times W: m_1 < m_2 \land w_1 \not= w_2\}$$ be the set of quadruples of players. Let binary decision variable $x_{r,q}$ indicate whether round $r\in R$ uses quadruple $q\in Q$. The constraints are \begin{align} \sum_{\substack{(m_1,w_1,m_2,w_2)\in Q:\\ m\in \{m_1,m_2\}}} x_{r,m_1,w_1,m_2,w_2} &= 1 &&\text{for $r\in R, m\in M$} \tag1 \\ \sum_{\substack{(m_1,w_1,m_2,w_2)\in Q:\\ w\in \{w_1,w_2\}}} x_{r,m_1,w_1,m_2,w_2} &= 1 &&\text{for $r\in R, w\in W$} \tag2 \\ \sum_{r\in R} \sum_{\substack{(m_1,w_1,m_2,w_2)\in Q:\\ (m,w)\in\{m_1,m_2\}\times\{w_1,w_2\}}} x_{r,m_1,w_1,m_2,w_2} &\le 1 &&\text{for $m\in M, w\in W$} \tag3 \\ \sum_{r\in R} \sum_{\substack{(m_1,w_1,m_2,w_2)\in Q:\\ (m_i,m_j)=\{m_1,m_2\}}} x_{r,m_1,w_1,m_2,w_2} &\le 1 &&\text{for $m_i\in M, m_j\in M$ with $m_i<m_j$} \tag4 \\ \sum_{r\in R} \sum_{\substack{(m_1,w_1,m_2,w_2)\in Q:\\ \{w_i,w_j\}=\{w_1,w_2\}}} x_{r,m_1,w_1,m_2,w_2} &\le 1 &&\text{for $w_i\in W, w_j\in W$ with $w_i<w_j$} \tag5 \\ \end{align}

Constraints $(1)$ and $(2)$ use each man or woman exactly once per round, respectively. Constraint $(3)$ avoids repeated man-woman pairs. Constraint $(4)$ avoids repeated man-man pairs. Constraint $(5)$ avoids repeated woman-woman pairs.

For a fixed number of rounds, you can discourage repetition by introducing nonnegative "surplus" variables for the constraints and penalizing them in an objective function to be minimized. Alternatively, you can maximize the number of rounds with no repetition by introducing a binary variable $u_r$ to indicate whether round $r\in R$ is used, replace the $=1$ with $=u_r$ in constraints $(1)$ and $(2)$, and maximize $\sum_{r\in R} u_r$.

The maximum number of rounds without repeats turns out to be $6$. To see that this is an upper bound, note that there are $12\cdot12=144$ man-woman pairs and each round uses up $\frac{12+12}{4}\cdot2\cdot2=24$ of them.

---

By request, here is SAS code:

proc optmodel;
   set MEN = 1..12;
   set WOMEN = /A B C D E F G H I J K L/;
   set ROUNDS = 1..6;
   set QUADS = {m1 in MEN, w1 in WOMEN, m2 in MEN diff {m1}, w2 in WOMEN diff {w1}: m1 < m2};
   set MAN_PAIRS = {mi in MEN, mj in MEN: mi < mj};
   set WOMAN_PAIRS = {wi in WOMEN, wj in WOMEN: wi < wj};

   var UseRound {ROUNDS} binary;
   var UseQuad {ROUNDS, QUADS} binary;

   max NumUsedRounds = sum {r in ROUNDS} UseRound[r];

   con OncePerRoundMan {r in ROUNDS, m in MEN}:
      sum {<m1,w1,m2,w2> in QUADS: m in {m1,m2}} UseQuad[r,m1,w1,m2,w2] = UseRound[r];

   con OncePerRoundWoman {r in ROUNDS, w in WOMEN}:
      sum {<m1,w1,m2,w2> in QUADS: w in {w1,w2}} UseQuad[r,m1,w1,m2,w2] = UseRound[r];

   con NoRepeatedMW {m in MEN, w in WOMEN}:
      sum {r in ROUNDS} sum {<m1,w1,m2,w2> in QUADS: <m,w> in {m1,m2} cross {w1,w2}} UseQuad[r,m1,w1,m2,w2] <= 1;

   con NoRepeatedMM {<mi,mj> in MAN_PAIRS}:
      sum {r in ROUNDS} sum {<m1,w1,m2,w2> in QUADS: <mi,mj> in {<m1,m2>,<m2,m1>}} UseQuad[r,m1,w1,m2,w2] <= 1;

   con NoRepeatedWW {<wi,wj> in WOMAN_PAIRS}:
      sum {r in ROUNDS} sum {<m1,w1,m2,w2> in QUADS: <wi,wj> in {<w1,w2>,<w2,w1>}} UseQuad[r,m1,w1,m2,w2] <= 1;

   for {<m1,w1,m2,w2> in {<1,'A',2,'B'>,<3,'C',4,'D'>,<5,'E',6,'F'>,<7,'G',8,'H'>,<9,'I',10,'J'>,<11,'K',12,'L'>}}
      fix UseQuad[1,m1,w1,m2,w2] = 1;

   solve;
   for {r in ROUNDS} do;
      for {<m1,w1,m2,w2> in QUADS: UseQuad[r,m1,w1,m2,w2].sol > 0.5} put (m1||w1||m2||w2) @;
      put;
   end;
quit;

Answer 2

I think I found 7 of such rounds. Let me describe how I found those. \begin{array}{c|c|c|c|c|c|c} &1A-2B &1K-12J &1L-3B &1H-11F &1J-4A &1D-10A &1C-7I\\ &3C-4D &2L-3A &2A-4C &2I-12G &2K-5B &2E-11B &2D-8J\\ &5E-6F &4B-5C &5D-7F &3J-5L &3L-6C &3F-12C &3E-9K\\ &7G-8H &6D-7E &6E-8G &4K-6A &7D-10G &4G-7J &4F-10L\\ &9I-10J &8F-9G &9H-11J &7B-9D &8E-11H &5H-8K &5G-11A\\ &11K-12L &10H-11I &10I-12K &8C-10E &9F-12I &6I-9L &6H-12B\\ \end{array} $1)$ Arrange 12 men around the circle. These men will stick to their positions. Each dot is a man.

$2)$ Arrange 12 women around the circle. We will keep rotating those women only, so that they never see the same partner on a new round. A man and a woman on the same position are in a team.

$3)$ Connect two dots with a line. Those two dots are in a game.

$4)$ At the beginning, we'll connect $n$'th and $(n+1)$'th dots. There are two cases - $2n$ to $2n+1$, and $2n+1$ to $2n+2$. Rounds $1$ and $2$ are such two cases.

$5)$ Note that between Rounds $1$ and $2$, we rotated women by 2 clicks,because otherwise women will meet the same enemy they've already met.

$6)$ And the connect $n$'th and $(n+2)$'th dots. If we care about only men, then there can be $4$ such cases. But to have women avoid to meet the same enemy, there can be only two cases. Women rotated back by 1 click to save the cases for later.

$7)$ Likewise, connect $n$'th and $(n+3)$'th dots. If we care about only men, then there can be $6$ such cases. But to have women avoid to meet the same enemy, there can be only two cases.

$8)$ Connecting $n$'th and $(n+6)$'th dots has only one case even if considering men only. We rotate women so that they partner with any man with whom they haven't partnered.

$$\\\\$$

Answer 3

Building upon Kay's "clocks" method, I found the 6 rounds with unique games:

1A2B
3C4D
5E6F
7G8H
9I10J
11K12L

1I12H
2J3K
4L5A
6B7C
8D9E
10F11G

1K3A
2L4B
5C7E
6D8F
9G11I
10H12J

1H4K
2I5L
3J6A
7B10E
8C11F
9D12G

1L7F
2A8G
3B9H
4C10I
5D11J
6E12K

1B5G
2K10C
3F12I
4J8E
6H9L
7A11D

I noticed that already in Kay's round 2 there is a repetition: A already played against 2. So, the rotation by 2 clicks is not enough. Rotation by 4 was the first that had no repetitions, so I took it. Round 3 was similar, rotation by 2 was the first one that worked. In round 4 there was no rotation for which Kay's connection would work, so I skipped that connection scheme. The one from Kay's round 5 worked, although with rotation of 5. Schema from Kay's round 6 didn't work with any rotation, skipped. Schema from Kay's round 7 worked, with rotation 1. Thanks to that I already got 5 rounds.

For the 6th round I needed a new connection schema. I noticed that there was no connection from 1 to 5 ("by 4") in any previous schema. So, could connect 1-5, 7-11, 2-10, 4-8. 4 numbers left unconnected: 3, 6, 9, 12. I could connect 3-12 and 6-9, because I didn't have those connections in mine schemas (they are in Kay's round 6, but I skipped that round).

Now I only needed to place letters there. No rotation worked. Rotations represent a tiny fraction of the search space, only 12 out of all 12! possibilities. So I decided to do some trial-and-error using DFS. With the slightly modified script (looping through the letters) I was able to see which letters could be paired with 1. There were 7 options: 1B5G, 1B5I, 1B5J, 1C5G, 1C5J, 1D5I, 1G5J. Took the first one, saw which letters could be paired with 2 (2H10C, 2H10D, 2K10C, 2K10D) and so on, I followed DFS. Due to many possible solutions I could be lucky and find one after expanding a small part of tree. Was lucky to find it after only expanding about a half of the first 1B5G branch. Bottom-right in the image:

Green circles mark the 6 unique rounds.