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