Sport scheduling
This tutorial was generated using Literate.jl. Download the source as a .jl file.
This tutorial was adapted from an example written by Eli Towle in 2016 as part of an operations research course at the University of Wisconsin-Madison.
This tutorial formulates a round-robin sports scheduling problem as a binary integer program that assigns home and away games to Big Ten Conference teams across a season. It shows how to iteratively improve the schedule by minimising back-to-back away games.
Learning intentions:
- Encode a round-robin schedule as a three-index binary variable and express home-game, matchup, and away-game-limit constraints in JuMP
- Break solution symmetry by fixing one team's schedule, which makes the problem significantly easier to solve
- Extend the feasibility model with an objective to minimise back-to-back away games, and provide a warm start to help the solver find a good solution within a time limit
Required packages
This tutorial uses the following packages:
using JuMP
import HiGHSBasic model
Here are the teams in our tournament:
M = [
"Ill", # U. Illinois Urbana-Champaign
"Ind", # Indiana University Bloomington
"Iowa", # University of Iowa
"MSU", # Michigan State University
"NU", # Northwestern University
"OSU", # The Ohio State Univesity
"Penn", # Pennsylvania State University
"Purd", # Purdue University
"Rtgrs", # Rutgers University
"UMD", # University of Maryland, College Park
"UMich", # University of Michigan
"UMN", # University of Minnesota Twin Cities
"UNL", # University of Nebraska-Lincoln
"UW", # University of Wisconsin-Madison
];For each team to play each other exactly once, we need the number of teams - 1 weeks:
T = length(M) - 1;Now we create a JuMP model to build our optimzation problem:
model = Model(HiGHS.Optimizer);Variable: a binary which is true for x[m,n,t] if team m is playing n at home in week t.
@variable(model, x[M, M, 1:T], Bin);Constraint: each team m can never play themselves.
@constraint(model, [m in M, t in 1:T], x[m, m, t] == 0);Constraint: each team m can play at most once per day
@constraint(model, [m in M, t in 1:T], sum(x[m, :, t]) + sum(x[:, m, t]) <= 1);Constraint: every team m plays at least half home games
@constraint(model, [m in M], div(T, 2) <= sum(x[m, :, :]) <= div(T, 2) + 1);Constraint: no more than two away games in any three-game window
@constraint(model, [m in M, t in 1:(T-2)], sum(x[:, m, t:(t+2)]) <= 2);Constraint: every team must play every other team exactly once
@constraint(
model,
[m in M, n in M; m != n],
sum(x[m, n, :]) + sum(x[n, m, :]) == 1,
);One problem with out model is that there is a lot of symmetry. To make the problem easier to solve, we fix the schedule of a random team to play every team in order, alternating between home and away:
m = rand(M)
for (t, n) in enumerate(filter(!=(m), M))
if isodd(t)
fix(x[m, n, t], 1)
else
fix(x[n, m, t], 1)
end
endNow we can solve our model:
set_silent(model)
optimize!(model)
assert_is_solved_and_feasible(model)and print the schedule:
function print_schedule(M::Vector{String}, T::Int, Y::AbstractArray{Bool})
println("Week ", join(rpad.(M, 6), ' '))
for t in 1:T
print(rpad(t, 5))
for m in M, n in M
if Y[m, n, t]
print(rpad(n, 7))
elseif Y[n, m, t]
print("@", rpad(n, 6))
end
end
println()
end
return
end
Y = round.(Bool, value.(x))
print_schedule(M, T, Y)Week Ill Ind Iowa MSU NU OSU Penn Purd Rtgrs UMD UMich UMN UNL UW
1 @UNL @OSU @UMich @UMN Purd Ind UW @NU @UMD Rtgrs Iowa MSU Ill @Penn
2 @Purd UNL UW @NU MSU UMN UMD Ill UMich @Penn @Rtgrs @OSU @Ind @Iowa
3 UMich @UMD @UNL OSU @UW @MSU @Rtgrs @UMN Penn Ind @Ill Purd Iowa NU
4 Rtgrs @Purd Penn UNL UMN @UMich @Iowa Ind @Ill @UW OSU @NU @MSU UMD
5 @Iowa UW Ill @UMD @UNL Rtgrs Purd @Penn @OSU MSU UMN @UMich NU @Ind
6 Penn @UMich @MSU Iowa @Rtgrs UNL @Ill UMD NU @Purd Ind UW @OSU @UMN
7 @UMD UMN OSU @Rtgrs UMich @Iowa @UNL @UW MSU Ill @NU @Ind Penn Purd
8 @UMN @Penn @NU UMich Iowa @UMD Ind UNL @UW OSU @MSU Ill @Purd Rtgrs
9 NU @Iowa Ind Penn @Ill UW @MSU @UMich @UNL @UMN Purd UMD Rtgrs @OSU
10 OSU MSU Purd @Ind @Penn @Ill NU @Iowa UMN UNL @UW @Rtgrs @UMD UMich
11 Ind @Ill UMN @UW UMD Penn @OSU Rtgrs @Purd @NU @UNL @Iowa UMich MSU
12 UW Rtgrs @UMD Purd @OSU NU @UMich @MSU @Ind Iowa Penn UNL @UMN @Ill
13 @MSU NU @Rtgrs Ill @Ind @Purd UMN OSU Iowa @UMich UMD @Penn UW @UNLThis schedule is okay, but it features a large number of back-to-back away games (in which a team plays away from home two weeks in a row). Let's count them:
number_of_back_to_back_away_games =
sum(round(Int, value(sum(x[:, m, (t-1):t]))) == 2 for m in M, t in 2:T)27A better schedule would minimize this quantity.
Minimizing the number of back-to-back away games
To minimize the number of back-to-back away games, we modify our model.
Variable: a binary which is true for y[m,t] if team m is playing back-to-back away games in week t.
@variable(model, y[M, 2:T], Bin);Objective: minimize the number of back-to-back away games
@objective(model, Min, sum(y));Constraint: count back-to-back away games
@constraint(model, [m in M, t in 2:T], y[m, t] >= sum(x[:, m, (t-1):t]) - 1);Now we can solve our model. However, this problem is actually very difficult to solve to optimality. Rather than wait a very long time, we set a time limit so that this documentation doesn't take too long to build:
set_time_limit_sec(model, 30.0)We're also going to set a start value based on the previous solution:
set_start_value.(x, Y)
for m in M, t in 2:T
set_start_value(y[m, t], sum(Y[:, m, (t-1):t]) - 1)
endNow we can optimize:
optimize!(model)Because we hit a time limit, we can't use assert_is_solved_and_feasible, but we still check that we found a feasible primal solution:
@assert termination_status(model) == TIME_LIMIT
@assert primal_status(model) == FEASIBLE_POINTThis solution has fewer back-to-back away games:
number_of_back_to_back_away_games =
sum(round(Int, value(sum(x[:, m, (t-1):t]))) == 2 for m in M, t in 2:T)9And the final schedule is:
Y = round.(Bool, value.(x))
print_schedule(M, T, Y)Week Ill Ind Iowa MSU NU OSU Penn Purd Rtgrs UMD UMich UMN UNL UW
1 @UNL @UMN @UW @UMD OSU @NU @Rtgrs @UMich Penn MSU Purd Ind Ill Iowa
2 @Iowa UNL Ill UW @Rtgrs UMich UMD UMN NU @Penn @OSU @Purd @Ind @MSU
3 MSU Rtgrs @UNL @Ill UMich @UW @UMN @UMD @Ind Purd @NU Penn Iowa OSU
4 @UMich @Penn NU UNL @Iowa UMD Ind UW UMN @OSU Ill @Rtgrs @MSU @Purd
5 Rtgrs MSU @UMD @Ind @UNL @Purd @UW OSU @Ill Iowa @UMN UMich NU Penn
6 UW @UMich UMN @Penn Purd UNL MSU @NU UMD @Rtgrs Ind @Iowa @OSU @Ill
7 @UMN OSU @Purd Rtgrs @UW @Ind @UNL Iowa @MSU UMich @UMD Ill Penn NU
8 @UMD @Iowa Ind @UMich UMN Penn @OSU UNL UW Ill MSU @NU @Purd @Rtgrs
9 NU UMD @Penn Purd @Ill @UMN Iowa @MSU @UNL @Ind @UW OSU Rtgrs UMich
10 @OSU @NU MSU @Iowa Ind Ill @Purd Penn @UMich UNL Rtgrs @UW @UMD UMN
11 Purd UW @Rtgrs OSU @Penn @MSU NU @Ill Iowa @UMN @UNL UMD UMich @Ind
12 Penn @Purd @UMich @NU MSU Rtgrs @Ill Ind @OSU @UW Iowa UNL @UMN UMD
13 @Ind Ill OSU UMN @UMD @Iowa UMich @Rtgrs Purd NU @Penn @MSU UW @UNLTry running the model for longer. What is the smallest number of back-to-back away games you can find?