Use decision optimization to help a sports league schedule its games

This tutorial includes everything you need to set up decision optimization engines, build mathematical programming models, and arrive at a good working schedule for a sports league’s games.

When you finish this tutorial, you’ll have a foundational knowledge of Prescriptive Analytics.

This notebook is part of Prescriptive Analytics for Python

It requires either an installation of CPLEX Optimizers or it can be run on IBM Watson Studio Cloud (Sign up for a free IBM Cloud account and you can start using Watson Studio Cloud right away).

Table of contents:

The business problem: Games Scheduling in the National Football League

  • A sports league with two divisions must schedule games so that each team plays every team within its division a given number of times, and each team plays teams in the other division a given number of times.
  • A team plays exactly one game each week.
  • A pair of teams cannot play each other on consecutive weeks.
  • While a third of a team’s intradivisional games must be played in the first half of the season, the preference is for intradivisional games to be held as late as possible in the season.
    • To model this preference, there is an incentive for intradivisional games that increases each week as a square of the week.
    • An opponent must be assigned to each team each week to maximize the total of the incentives..

This is a type of discrete optimization problem that can be solved by using either Integer Programming (IP) or Constraint Programming (CP).

Integer Programming is the class of problems defined as the optimization of a linear function, subject to linear constraints over integer variables.
Constraint Programming problems generally have discrete decision variables, but the constraints can be logical, and the arithmetic expressions are not restricted to being linear.

For the purposes of this tutorial, we will illustrate a solution with mathematical programming (MIP).

How decision optimization can help

  • Prescriptive analytics (decision optimization) technology recommends actions that are based on desired outcomes. It takes into account specific scenarios, resources, and knowledge of past and current events. With this insight, your organization can make better decisions and have greater control of business outcomes.

  • Prescriptive analytics is the next step on the path to insight-based actions. It creates value through synergy with predictive analytics, which analyzes data to predict future outcomes.

  • Prescriptive analytics takes that insight to the next level by suggesting the optimal way to handle that future situation. Organizations that can act fast in dynamic conditions and make superior decisions in uncertain environments gain a strong competitive advantage.

With prescriptive analytics, you can:

  • Automate the complex decisions and trade-offs to better manage your limited resources.
  • Take advantage of a future opportunity or mitigate a future risk.
  • Proactively update recommendations based on changing events.
  • Meet operational goals, increase customer loyalty, prevent threats and fraud, and optimize business processes.

Use decision optimization

Step 1: Import the library

Run the following code to import the Decision Optimization CPLEX Modeling library. The DOcplex library contains the two modeling packages, Mathematical Programming (docplex.mp) and Constraint Programming (docplex.cp).

If CPLEX is not installed, install CPLEX Community edition.

Step 2: Model the data

In this scenario, the data is simple. There are eight teams in each division, and the teams must play each team in the division once and each team outside the division once.

Use a Python module, Collections, which implements some data structures that will help solve some problems. Named tuples helps to define meaning of each position in a tuple. This helps the code be more readable and self-documenting. You can use named tuples in any place where you use tuples.

In this example, you create a namedtuple to contain information for points. You are also defining some of the parameters.

Use basic HTML and a stylesheet to format the data.

Now you will import the pandas library. Pandas is an open source Python library for data analysis. It uses two data structures, Series and DataFrame, which are built on top of NumPy.

A Series is a one-dimensional object similar to an array, list, or column in a table. It will assign a labeled index to each item in the series. By default, each item receives an index label from 0 to N, where N is the length of the series minus one.

A DataFrame is a tabular data structure comprised of rows and columns, similar to a spreadsheet, database table, or R’s data.frame object. Think of a DataFrame as a group of Series objects that share an index (the column names).

In the example, each division (the AFC and the NFC) is part of a DataFrame.

The following display function is a tool to show different representations of objects. When you issue the display(teams) command, you are sending the output to the notebook so that the result is stored in the document.

AFC NFC
0 Baltimore Ravens Chicago Bears
1 Cincinnati Bengals Detroit Lions
2 Cleveland Browns Green Bay Packers
3 Pittsburgh Steelers Minnesota Vikings
4 Houston Texans Atlanta Falcons
5 Indianapolis Colts Carolina Panthers
6 Jacksonville Jaguars New Orleans Saints
7 Tennessee Titans Tampa Bay Buccaneers
8 Buffalo Bills Dallas Cowboys
9 Miami Dolphins New York Giants
10 New England Patriots Philadelphia Eagles
11 New York Jets Washington Redskins
12 Denver Broncos Arizona Cardinals
13 Kansas City Chiefs San Francisco 49ers
14 Oakland Raiders Seattle Seahawks
15 San Diego Chargers St. Louis Rams

Step 3: Prepare the data

Given the number of teams in each division and the number of intradivisional and interdivisional games to be played, you can calculate the total number of teams and the number of weeks in the schedule, assuming every team plays exactly one game per week.

The season is split into halves, and the number of the intradivisional games that each team must play in the first half of the season is calculated.

Number of games to play between pairs depends on whether the pairing is intradivisional or not.

Step 4: Set up the prescriptive model

* system is: Windows 64bit
* Python version 3.7.3, located at: c:\local\python373\python.exe
* docplex is present, version is (2, 11, 0)
* pandas is present, version is 0.25.1

Create the DOcplex model

The model contains all the business constraints and defines the objective.

Define the decision variables

Express the business constraints

Each pair of teams must play the correct number of games.
Model: sports
 - number of variables: 405
   - binary=405, integer=0, continuous=0
 - number of constraints: 45
   - linear=45
 - parameters: defaults
 - problem type is: MILP
Each team must play exactly once in a week.
Model: sports
 - number of variables: 405
   - binary=405, integer=0, continuous=0
 - number of constraints: 135
   - linear=135
 - parameters: defaults
 - problem type is: MILP
Games between the same teams cannot be on successive weeks.
Model: sports
 - number of variables: 405
   - binary=405, integer=0, continuous=0
 - number of constraints: 495
   - linear=495
 - parameters: defaults
 - problem type is: MILP
Some intradivisional games should be in the first half.
Model: sports
 - number of variables: 405
   - binary=405, integer=0, continuous=0
 - number of constraints: 505
   - linear=505
 - parameters: defaults
 - problem type is: MILP

Express the objective

The objective function for this example is designed to force intradivisional games to occur as late in the season as possible. The incentive for intradivisional games increases by week. There is no incentive for interdivisional games.

Solve with Decision Optimization

You will get the best solution found after n seconds, due to a time limit parameter.

Model: sports
 - number of variables: 405
   - binary=405, integer=0, continuous=0
 - number of constraints: 505
   - linear=505
 - parameters: defaults
 - problem type is: MILP
* model sports solved with objective = 260

Step 5: Investigate the solution and then run an example analysis

Determine which of the scheduled games will be a replay of one of the last 10 Super Bowls. We start by creating a pandas DataFrame that contains the year and teams who played the last 10 Super Bowls.

year team1 team2
0 2016 Carolina Panthers Denver Broncos
1 2015 New England Patriots Seattle Seahawks
2 2014 Seattle Seahawks Denver Broncos
3 2013 Baltimore Ravens San Francisco 49ers
4 2012 New York Giants New England Patriots
5 2011 Green Bay Packers Pittsburgh Steelers
6 2010 New Orleans Saints Indianapolis Colts
7 2009 Pittsburgh Steelers Arizona Cardinals
8 2008 New York Giants New England Patriots
9 2007 Indianapolis Colts Chicago Bears

We now look for the games in our solution that are replays of one of the past 10 Super Bowls.

[(4, 'February', 'Green Bay Packers', 'Pittsburgh Steelers')]
week Month Team1 Team2
0 4 February Green Bay Packers Pittsburgh Steelers

Summary

You learned how to set up and use IBM Decision Optimization CPLEX Modeling for Python to formulate a Constraint Programming model and solve it with CPLEX.

Copyright � 2017-2019 IBM. IPLA licensed Sample Materials.