sport_scheduling.py¶
How can a sports league schedule matches between teams in different divisions such that the teams play each other the appropriate number of times and maximize the objective of scheduling intradivision matches as late as possible in the season?
A sports league with two divisions needs to schedule games such that each team plays every team within its division a specified number of times and plays every team in the other division a specified number of times. Each week, a team plays exactly one game. The preference is for intradivisional matches to be held as late as possible in the season. To model this preference, there is an incentive for intradivisional matches; this incentive increases in a non-linear manner by week. The problem consists of assigning an opponent to each team each week in order to maximize the total of the incentives.
This example works only with the unlimited version of IBM ILOG CPLEX Optimization Studio as it exceeds the limits of the Community Edition.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | # --------------------------------------------------------------------------
# Source file provided under Apache License, Version 2.0, January 2004,
# http://www.apache.org/licenses/
# (c) Copyright IBM Corp. 2015, 2018
# --------------------------------------------------------------------------
from collections import namedtuple
from docplex.mp.model import Model
from docplex.util.environment import get_environment
# ----------------------------------------------------------------------------
# Initialize the problem data
# ----------------------------------------------------------------------------
nbs = (8, 3, 2)
team_div1 = {"Baltimore Ravens", "Cincinnati Bengals", "Cleveland Browns",
"Pittsburgh Steelers", "Houston Texans", "Indianapolis Colts",
"Jacksonville Jaguars", "Tennessee Titans", "Buffalo Bills",
"Miami Dolphins", "New England Patriots", "New York Jets",
"Denver Broncos", "Kansas City Chiefs", "Oakland Raiders",
"San Diego Chargers"}
team_div2 = {"Chicago Bears", "Detroit Lions", "Green Bay Packers",
"Minnesota Vikings", "Atlanta Falcons", "Carolina Panthers",
"New Orleans Saints", "Tampa Bay Buccaneers", "Dallas Cowboys",
"New York Giants", "Philadelphia Eagles", "Washington Redskins",
"Arizona Cardinals", "San Francisco 49ers", "Seattle Seahawks",
"St. Louis Rams"}
Match = namedtuple("Matches", ["team1", "team2", "is_divisional"])
# ----------------------------------------------------------------------------
# Build the model
# ----------------------------------------------------------------------------
def build_sports(**kwargs):
print("* building sport scheduling model instance")
mdl = Model('sportSchedCPLEX', **kwargs)
nb_teams_in_division, nb_intra_divisional, nb_inter_divisional = nbs
assert len(team_div1) == len(team_div2)
mdl.teams = list(team_div1 | team_div2)
# team index ranges from 1 to 2N
team_range = range(1, 2 * nb_teams_in_division + 1)
# Calculate the number of weeks necessary.
nb_weeks = (nb_teams_in_division - 1) * nb_intra_divisional + nb_teams_in_division * nb_inter_divisional
weeks = range(1, nb_weeks + 1)
mdl.weeks = weeks
print("{0} games, {1} intradivisional, {2} interdivisional"
.format(nb_weeks, (nb_teams_in_division - 1) * nb_intra_divisional,
nb_teams_in_division * nb_inter_divisional))
# Season is split into two halves.
first_half_weeks = range(1, nb_weeks // 2 + 1)
nb_first_half_games = nb_weeks // 3
# All possible matches (pairings) and whether of not each is intradivisional.
matches = [Match(t1, t2, 1 if (t2 <= nb_teams_in_division or t1 > nb_teams_in_division) else 0)
for t1 in team_range for t2 in team_range if t1 < t2]
mdl.matches = matches
# Number of games to play between pairs depends on
# whether the pairing is intradivisional or not.
nb_play = {m: nb_intra_divisional if m.is_divisional == 1 else nb_inter_divisional for m in matches}
plays = mdl.binary_var_matrix(keys1=matches, keys2=weeks,
name=lambda mw: "play_%d_%d_w%d" % (mw[0].team1, mw[0].team2, mw[1]))
mdl.plays = plays
for m in matches:
mdl.add_constraint(mdl.sum(plays[m, w] for w in weeks) == nb_play[m],
"correct_nb_games_%d_%d" % (m.team1, m.team2))
for w in weeks:
# Each team must play exactly once in a week.
for t in team_range:
max_teams_in_division = (plays[m, w] for m in matches if m.team1 == t or m.team2 == t)
mdl.add_constraint(mdl.sum(max_teams_in_division) == 1,
"plays_exactly_once_%d_%s" % (w, t))
# Games between the same teams cannot be on successive weeks.
mdl.add_constraints(plays[m, w] + plays[m, w + 1] <= 1
for w in weeks for m in matches if w < nb_weeks)
# Some intradivisional games should be in the first half.
for t in team_range:
max_teams_in_division = [plays[m, w] for w in first_half_weeks for m in matches if
m.is_divisional == 1 and (m.team1 == t or m.team2 == t)]
mdl.add_constraint(mdl.sum(max_teams_in_division) >= nb_first_half_games,
"in_division_first_half_%s" % t)
# postpone divisional matches as much as possible
# we weight each play variable with the square of w.
mdl.maximize(mdl.sum(plays[m, w] * w * w for w in weeks for m in matches if m.is_divisional))
return mdl
# a named tuple to store solution
TSolution = namedtuple("TSolution", ["week", "is_divisional", "team1", "team2"])
def print_sports_solution(mdl):
# iterate with weeks first
solution = [TSolution(w, m.is_divisional, mdl.teams[m.team1], mdl.teams[m.team2])
for w in mdl.weeks for m in mdl.matches
if mdl.plays[m, w].to_bool()]
currweek = 0
print("Intradivisional games are marked with a *")
for s in solution:
# assume records are sorted by increasing week indices.
if s.week != currweek:
currweek = s.week
print(" == == == == == == == == == == == == == == == == ")
print("On week %d" % currweek)
print(" {0:s}{1} will meet the {2}".format("*" if s.is_divisional else "", s.team1, s.team2))
# ----------------------------------------------------------------------------
# Solve the model and display the result
# ----------------------------------------------------------------------------
if __name__ == '__main__':
# Build the model
model = build_sports()
model.print_information()
# Solve the model. If a key has been specified above, the solve
# will use IBM Decision Optimization on cloud.
if model.solve():
model.report()
print_sports_solution(model)
# Save the CPLEX solution as "solution.json" program output
with get_environment().get_output_stream("solution.json") as fp:
model.solution.export(fp, "json")
else:
print("Problem could not be solved: " + model.solve_details.get_status())
|