In [1] a question was posed about designing a sports schedule.
We have the following information:
- There are 24 teams
- There are 23 rounds
- In every round, each team plays against another team. A team plays exactly once in a round. I.e., there are 12 games per round.
- A team \(t1\) plays against team \(t2\) exactly once.
This is actually not too difficult to model.
Math Programming Model
We define as binary decision variable: \[\mathit{game}_{t1,t2,r} = \begin{cases} 1 & \text{if team \(t1\) plays against team \(t2\) in round \(r\)}\\ 0 & \text{otherwise} \end{cases}\] To prevent double counting, we use the convention that \(\mathit{game}_{t1,t2,r}\) is only defined when \(t1 \lt t2\). So, we have in the model \(\mathit{game}_{team2,team8,round4}\), but we will never use: \(\mathit{game}_{team8,team2,round4}\). This is a little bit of a complicating factor in the model, but the pay-off is that the bookkeeping becomes in the end simpler.
With this we can formulate:
| Mixed-Integer Programming Model |
|---|
| \[\begin{align}\min\>& 0 && &&\text{dummy objective} \\ & \sum_{t2|t1\lt t2} \color{darkred}{\mathit{game}}_{t1,t2,r} + \sum_{t2|t2\lt t1} \color{darkred}{\mathit{game}}_{t2,t1,r} = 1 && \forall t1,r &&\text{play exactly one opponent each round}\\ & \sum_r \color{darkred}{\mathit{game}}_{t1,t2,r}=1&&\forall t1,t2|t1 \lt t2 && \text{meet opponent exactly once}\\ &\color{darkred}{\mathit{game}}_{t1,t2,r} \in \{0,1\} &&\forall t1,t2,r|t1 \lt t2 &&\text{binary variables} \end{align}\] |
The model does not have a real objective: we are just looking for a feasible solution. The first constraint is the most complicated one. Basically it says \[\sum_{t2} {\mathit{game}}_{t1,t2,r} = 1 \>\> \forall t1,r\] but as we only use \({\mathit{game}}_{t1,t2,r}\) for \(t1 \lt t2\), we need to split things in two. This can be visualized as follows:
 |
| Opponents of team t3 |
If we would not have excluded all \(t2\ge t1\), but used a fully allocated \({\mathit{game}}_{t1,t2,r}\) we would have needed to add the constraints: \[\begin{align} & {\mathit{game}}_{t1,t2,r} = {\mathit{game}}_{t2,t1,r} \\ & {\mathit{game}}_{t1,t1,r}=0 \end{align}\] This will make the model larger, but a good presolver should help with that. Although for this model it probably does not make much difference, I prefer explicitly excluding all \(t2\ge t1\).
This is a rather simple model. But it will deliver the schedules we are looking for:
---- 24 VARIABLE game.L schedule for teams round1 round2 round3 round4 round5 round6 round7 round8 team1 .team15 1 team1 .team16 1 team1 .team17 1 team1 .team18 1 team1 .team19 1 team1 .team20 1 team1 .team22 1 team1 .team24 1 team2 .team12 1 team2 .team15 1 team2 .team16 1 team2 .team19 1 team2 .team20 1 team2 .team21 1 team2 .team23 1 team2 .team24 1 team3 .team12 1 team3 .team13 1 team3 .team14 1 team3 .team15 1 team3 .team16 1 team3 .team21 1 team3 .team23 1 team3 .team24 1 team4 .team10 1 team4 .team14 1 team4 .team15 1 team4 .team16 1 team4 .team18 1 team4 .team21 1 team4 .team22 1 team4 .team23 1 team5 .team11 1 team5 .team15 1 team5 .team16 1 team5 .team18 1 team5 .team19 1 team5 .team20 1 team5 .team21 1 team5 .team22 1 team6 .team9 1 team6 .team10 1 team6 .team11 1 team6 .team16 1 team6 .team17 1 team6 .team20 1 team6 .team22 1 team6 .team23 1 team7 .team9 1 team7 .team10 1 team7 .team12 1 team7 .team14 1 team7 .team16 1 team7 .team19 1 team7 .team21 1 team7 .team24 1 team8 .team9 1 team8 .team11 1 team8 .team12 1 team8 .team13 1 team8 .team14 1 team8 .team16 1 team8 .team19 1 team8 .team22 1 team9 .team18 1 team9 .team20 1 team9 .team21 1 team9 .team22 1 team9 .team23 1 team10.team17 1 team10.team20 1 team10.team21 1 team10.team23 1 team10.team24 1 team11.team17 1 team11.team18 1 team11.team19 1 team11.team23 1 team11.team24 1 team12.team17 1 team12.team18 1 team12.team22 1 team12.team24 1 team13.team17 1 team13.team18 1 team13.team19 1 team13.team20 1 team13.team23 1 team13.team24 1 team14.team17 1 team14.team18 1 team14.team20 1 team14.team21 1 team15.team17 1 team15.team19 1 team15.team22 1 + round9 round10 round11 round12 round13 round14 round15 round16 team1 .team9 1 team1 .team10 1 team1 .team11 1 team1 .team12 1 team1 .team13 1 team1 .team14 1 team1 .team21 1 team1 .team23 1 team2 .team9 1 team2 .team10 1 team2 .team11 1 team2 .team13 1 team2 .team14 1 team2 .team17 1 team2 .team18 1 team2 .team22 1 team3 .team9 1 team3 .team10 1 team3 .team11 1 team3 .team17 1 team3 .team18 1 team3 .team19 1 team3 .team20 1 team3 .team22 1 team4 .team9 1 team4 .team11 1 team4 .team12 1 team4 .team13 1 team4 .team17 1 team4 .team19 1 team4 .team20 1 team4 .team24 1 team5 .team9 1 team5 .team10 1 team5 .team12 1 team5 .team13 1 team5 .team14 1 team5 .team17 1 team5 .team23 1 team5 .team24 1 team6 .team12 1 team6 .team13 1 team6 .team14 1 team6 .team15 1 team6 .team18 1 team6 .team19 1 team6 .team21 1 team6 .team24 1 team7 .team11 1 team7 .team13 1 team7 .team15 1 team7 .team17 1 team7 .team18 1 team7 .team20 1 team7 .team22 1 team7 .team23 1 team8 .team10 1 team8 .team15 1 team8 .team17 1 team8 .team18 1 team8 .team20 1 team8 .team21 1 team8 .team23 1 team8 .team24 1 team9 .team17 1 team9 .team19 1 team9 .team24 1 team10.team18 1 team10.team19 1 team10.team22 1 team11.team20 1 team11.team21 1 team11.team22 1 team12.team19 1 team12.team20 1 team12.team21 1 team12.team23 1 team13.team21 1 team13.team22 1 team14.team19 1 team14.team22 1 team14.team23 1 team14.team24 1 team15.team18 1 team15.team20 1 team15.team21 1 team15.team23 1 team15.team24 1 team16.team17 1 team16.team18 1 team16.team19 1 team16.team20 1 team16.team21 1 team16.team22 1 team16.team23 1 team16.team24 1 + round17 round18 round19 round20 round21 round22 round23 team1 .team2 1 team1 .team3 1 team1 .team4 1 team1 .team5 1 team1 .team6 1 team1 .team7 1 team1 .team8 1 team2 .team3 1 team2 .team4 1 team2 .team5 1 team2 .team6 1 team2 .team7 1 team2 .team8 1 team3 .team4 1 team3 .team5 1 team3 .team6 1 team3 .team7 1 team3 .team8 1 team4 .team5 1 team4 .team6 1 team4 .team7 1 team4 .team8 1 team5 .team6 1 team5 .team7 1 team5 .team8 1 team6 .team7 1 team6 .team8 1 team7 .team8 1 team9 .team10 1 team9 .team11 1 team9 .team12 1 team9 .team13 1 team9 .team14 1 team9 .team15 1 team9 .team16 1 team10.team11 1 team10.team12 1 team10.team13 1 team10.team14 1 team10.team15 1 team10.team16 1 team11.team12 1 team11.team13 1 team11.team14 1 team11.team15 1 team11.team16 1 team12.team13 1 team12.team14 1 team12.team15 1 team12.team16 1 team13.team14 1 team13.team15 1 team13.team16 1 team14.team15 1 team14.team16 1 team15.team16 1 team17.team18 1 team17.team19 1 team17.team20 1 team17.team21 1 team17.team22 1 team17.team23 1 team17.team24 1 team18.team19 1 team18.team20 1 team18.team21 1 team18.team22 1 team18.team23 1 team18.team24 1 team19.team20 1 team19.team21 1 team19.team22 1 team19.team23 1 team19.team24 1 team20.team21 1 team20.team22 1 team20.team23 1 team20.team24 1 team21.team22 1 team21.team23 1 team21.team24 1 team22.team23 1 team22.team24 1 team23.team24 1
This model solved very quickly, it needed about 0.2 seconds. Of course, the solution is not unique.
GAMS representation
set
t 'team' /team1*team24/ r 'rounds' /round1*round23/ ; alias (t,t1,t2); set lt(t1,t2) 'less than'; lt(t1,t2) = ord(t1)<ord(t2); binary variable game(t1,t2,r) 'schedule for teams'; variable dummy 'objective variable'; equations round(r,t1) 'play exactly one opponent each round' meet(t1,t2) 't1 meets t2 exactly once' obj 'dummy objective' ; round(r,t1).. sum(lt(t1,t2),game(t1,t2,r))+sum(lt(t2,t1),game(t2,t1,r)) =e= 1; meet(lt(t1,t2)).. sum(r,game(t1,t2,r)) =e= 1; obj.. dummy=e=0; model m /all/; solve m minimizing dummy using mip; option game:0; display game.l; |
Notice how the set lt(t1,t2) implements the strictly upper-triangular structure we want. We use the GAMS feature that if a variable does not appear in any of the equations, it will not be generated, even though we declared all game(t1,t2,r). Note that we don't need to set a gap using the optcr option. The solver will stop as soon as it has found a feasible integer solution: that solution is immediately optimal.
References
- Excel solver failure to get optimal solution when generating a schedule for 12 week schedule for 24 teams, https://stackoverflow.com/questions/62327762/excel-solver-failure-to-get-optimal-solution-when-generating-a-schedule-for-12-w
Interesting approach! You might be already aware of it, but there's also a pretty simple scheduling algorithm to solve problems of this sort: https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm . Given that this algorithm guarantees that a solution always exists, I guess it means that the MIP you formulated must have some structure to guarantee automatic feasibility. I think you can relax the binary constraints to 0<=x<=1 constraints and adding an arbitrary linear cost would yield an optimal MIP solution through an LP solver. That'd still be slower than the round-robin algorithm, but probably faster than the MIP one?
ReplyDeleteCheers!
Thanks. That is a nice reference. I don't think we can just solve as an LP (I tried; that produces a fractional solution). However the MIP model solves very fast: 0 nodes needed.
Delete