Tournament Schedule Assignment via Convex Optimization 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:

*

*Each pod plays with every other pod exactly once

*Each pod plays against every other pod exactly twice

*No pod that plays consecutive games much switch colors (to give time to switch jerseys)

*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.
 A: 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$
