Tournament Schedule Assignment via Convex Optimization

Question

I am tasked with setting up a schedule for a sports "potluck" tournament as follows.

Everyone signs up as individuals, and are sorted into "pods" of 4-5 people where each pod has roughly the same average skill level to keep the games interesting. Teams of 8-10 players are made by combining 2 pods together and facing them off against an opposing team of 2 other pods. In this way, each pod (ideally) plays with every other pod once and against every other pod twice over the course of the day. One team plays in black jerseys and the other team white. A target setup would have N=9 pods so that each pod plays in 8 out of 18 games on a single field of play (each pod sits out for 10/18 time slots).

The ideal schedule would have the following attributes:

1. Each pod plays with every other pod exactly once
2. Each pod plays against every other pod exactly twice
3. No pod that plays consecutive games much switch colors (to give time to switch jerseys)
4. Of the remaining valid solutions, minimize the total number of color switches across all pods

Is it possible to formulate either this problem or its relaxation as a convex optimization? Is there some way to either obtain one such valid schedule (for N=9, say), or prove that no such schedule exists that satisfies #1-#3?

I thought I would be able to come up with a schedule manually, but it is trickier than anticipated. Here is an example I manually constructed that obeys constraints #1 and #3 but not #2.

It seems like something like the Hungarian Algorithm could work in this case, with vector elements of +-1 to denote black/white, and zero to denote sitting out that game.

Here are some initial thoughts along those lines. Denote X[i,j] as +-1 when pod j plays black/white in game i, and 0 if it sits this game out. The following convex constraints seem to handle the basic rules and #3:

• (C1) $-1 \leq X[i,j] \leq +1$
• (C2) $\sum_j X[i,j] = 0$
• (C3) $\sum_j |X[i,j]| = 4$
• (C4) $| {\rm diff}_i\{X\}[i,j]| <= 1$

The following constraints, or something like them could work for #1 and #2:

• (C5) $\langle X[:,j_1],X[:,j_2] \rangle = -1 ~~~ \forall j_1, j_2$
• (C6) $\langle |X[:,j_1]| , |X[:,j_2]| \rangle = 3 ~~~ \forall j_1, j_2$

Although it gets dicey with these cross-terms and abs, so I suppose it's no longer a linear program, and is now something else?

For #4, it seems nontrivial to set up under this formulation. The naive approach would minimize sum_{i,j} (abs(diff_i(X[i,j]))), but this would be incorrect because a pod schedule of +1, 0, +1, 0, +1, involves no change in jersey color. So it might be necessary to give up on #4 and just focus on a valid solution satisfying #1-#3.

Answer 1

An integer linear program with binary variables will do the job. There is more than one way to model it. I have an IP model that seems to work, in the sense that it produces feasible solutions, but the bound is rather loose, so proof of optimality could take quite a while.

The model might be too cumbersome to display here in its full glory, but I can least list the variables and describe the constraints. First, some terminology: a "team" is a pair of pods playing together, and each game is divided into two "slots" (white and black, as in jersey colors). There are 36 possible teams, each of which needs to play exactly once, and 36 slots. The variables used in my model (all binary) are:

• $x_{t,s}=1$ if team $t$ plays in slot $s$, 0 if not;
• $y_{p,\hat{p},s}=1$ if pod $p$ is playing in slot $s$ and is opposed by a team containing pod $\hat{p}\neq p$;
• $z_{p,g}=0$ if pod $p$ is wearing color 0 (white) during game $g$ and 1 if it is wearing color 1 (black) during game $g$ (regardless of whether pod $p$ is actually playing in game $g$ or not); and
• $w_{p,g}=1$ if pod $p$ changes its jersey color going into game $g$.

The objective is to minimize the sum of the $w$ variables. There are sets of constraints as follows:

• every team is assigned to exactly one slot;
• every slot is filled exactly once;
• the $y$ variables are defined by inequalities involving the $x$ variables;
• every pair of pods are opponents exactly twice;
• the slot a team plays in determines the jerseys worn during that game by the pods in the team (which has the side effect of preventing a pod from playing against itself);
• no pod plays in consecutive games in different colors; and
• the color jersey worn by a pod during a game is the same as the color worn in the previous game (regardless of whether the pod plays in either game) unless a change occurs and is counted.

Addendum: By request, here is the best solution I found (14 jersey changes, running the IP model with a time limit of 30 minutes).

Game  1: 1 & 3 vs. 7 & 8
Game  2: 3 & 9 vs. 2 & 4
Game  3: 1 & 9 vs. 2 & 8
Game  4: 5 & 9 vs. 3 & 7
Game  5: 5 & 8 vs. 2 & 6
Game  6: 1 & 5 vs. 6 & 9
Game  7: 1 & 2 vs. 6 & 7
Game  8: 2 & 9 vs. 3 & 6
Game  9: 8 & 9 vs. 4 & 5
Game 10: 3 & 8 vs. 4 & 6
Game 11: 2 & 3 vs. 5 & 7
Game 12: 3 & 4 vs. 1 & 6
Game 13: 4 & 9 vs. 1 & 7
Game 14: 4 & 8 vs. 2 & 7
Game 15: 1 & 4 vs. 2 & 5
Game 16: 1 & 8 vs. 3 & 5
Game 17: 4 & 7 vs. 5 & 6
Game 18: 7 & 9 vs. 6 & 8

Addendum 2: Responding to the issue of pods playing in four consecutive games, here is a (not necessarily optimal) schedule with 16 jersey changes and some streaks of three consecutive games, but no streaks of four consecutive games.

Game  1: 3 & 7 vs. 4 & 8
Game  2: 5 & 7 vs. 1 & 9
Game  3: 4 & 5 vs. 6 & 9
Game  4: 3 & 4 vs. 1 & 2
Game  5: 3 & 6 vs. 1 & 8
Game  6: 4 & 7 vs. 2 & 5
Game  7: 3 & 8 vs. 5 & 9
Game  8: 2 & 6 vs. 1 & 7
Game  9: 4 & 6 vs. 7 & 8
Game 10: 1 & 4 vs. 5 & 8
Game 11: 2 & 3 vs. 5 & 6
Game 12: 4 & 9 vs. 1 & 6
Game 13: 2 & 9 vs. 6 & 8
Game 14: 7 & 9 vs. 1 & 3
Game 15: 6 & 7 vs. 3 & 5
Game 16: 2 & 7 vs. 8 & 9
Game 17: 2 & 4 vs. 3 & 9
Game 18: 2 & 8 vs. 1 & 5

Answer 2

Never mind linear program. It's not even convex, due to the L1-equality-constraint (C3). Nor will relaxing help: the corresponding convexified inequality constraint $\sum_j |X[i,j]| \leq 4$ will be insufficient to prevent the trivial solution $X=0$.

It seems necessary to model the "envelope" explicitly so that $X[i,j] = P[i,j] C[i,j]$ for binary function $P[i,j]$, that is one if pod $j$ plays game $i$ and zero otherwise. Sign-valued jersey color $C[i,j]$ is $\pm 1$ to denote jersey colors during a game, and is allowed to ``float'' to intermediate values during games that the pod sits out, allowing better modeling of the objective function #4.

Then we have:

(DO) $\min \sum_{i,j} |C[i,j]-C[i-1,j]|$

subject to:

• (D1) $-1 \leq C[i,j] \leq 1 ~~~ \forall i,j$
• (D2) $0 \leq P[i,j] \leq 1 ~~~ \forall i,j$
• (D3) $|C[i,j] - C[i-1,j]| \leq 1 ~~~ \forall i,j$
• (D4) $\sum_i P[i,j] = N-1 ~~~ \forall j$
• (D5) $\sum_j P[i,j] = 4 ~~~ \forall i$
• (D6) $\sum_j C[i,j] P[i,j] = 0 ~~~ \forall i$
• (D7) $\sum_i P[i,j_1] P[i,j_2] = 3 ~~~ \forall j_1, j_2$
• (D8) $\sum_i C[i,j_1] P[i,j_1] C[i,j_2] P[i,j_2] = -1 ~~~ \forall j_1, j_2$

Well... this isn't exactly convex either, but at least is more amenable to convexification. The following approximation to the above seems closer to the mark...

(EO) $ \min \sum_{i,j} |C[i,j]-C[i-1,j]| $

subject to:

• (E1) $~ -1 \leq C[i,j] \leq 1 ~~~ \forall i,j $
• (E2) $~ 0 \leq P[i,j] \leq 1 ~~~ \forall i,j $
• (E3) $ |C[i,j] - C[i-1,j]| \leq 1 ~~~ \forall i,j $
• (E4) $ \sum_i P[i,j] = N-1 ~~~ \forall j $
• (E5) $ \sum_j P[i,j] = 4 ~~~ \forall i $
• (E6) $ | \sum_j C[i,j] P[i,j]| \leq 0 ~~~ \forall i $
• (E7) $ \sum_i P[i,j_1] P[i,j_2] \leq 3 ~~~ \forall j_1, j_2 $
• (E8) $\sum_i C[i,j_1] C[i,j_2] = -1 ~~~ \forall j_1, j_2$