Same Conference LP Models

See Appendix for Linear Programming Model Downloads.

Manual cross conference play for first two months is followed by computer generated same conference play to finish regular the season.

The season begins with 450 non computer generated cross conference games for the first 60 days. Each team from the Eastern Conference goes on a 15 game road trip while the Western Conference stays home for a 15 game home stand, lasting thirty days. The Western Conference then goes on its 15 game road trip for thirty more days to complete cross conference play. (These long road trips could be split up for the same effect with longer total distance travelled.) The remaining 780 games are computer generated from the two Linear Programming models described below. Because the playoffs are determined within each conference, the end of the season would involve teams directly competing with one another for playoff spots. The cross conference beginning of the season might act as something of a pre season with star or older players taking more rest time.

A full 1230 game season, generated from one LP model is a goal for continued improvement and expansion of this project.

Games generated Manually vs Linear Programming

Decision Variables

A variable is an individual team beginning a road trip on a particular day. Here's how the model has 60,525 variables:

15 teams going on 15 potential road trips per team creates 225 variables. With 1 game, 2 game, 3 game, 4 game, and 6 game road trips, the season has five "road trip types". Therefore, most days involve 1,125 variables (225*5). The final few days of the season have less road trip possibilities so a road trip does not go beyond the season. (A six game road trip cannot begin on the last day of the season.) Therefore, 2,475 variables were eliminated at the end of the season. The equation to determine the number of variables: (15 teams * 15 road trips * 5 road trip types * 56 start dates) - 2475 = 60,525 Decision Variables. Most variables will end up having a value of "0"; occasional "1s" indicate a team has begun a road trip on a particular day.

(If you happen to download the LP models from the appendix you may notice that the coefficients for the eastern conference road trips are the same as the western conference. I did not have time to change the coefficients; nevertheless, the model still behaves the same because the teams are indexed. A proper grid of distances and a python script was used to calculate final totals for distance traveled.)

In the example below, Denver goes on a road trip to Oakland, then to Los Angeles for a game against the Clippers and then the Lakers. The entire road trip of leaving Denver, going to Oakland for one game, then to Los Angeles for two games and finally back to Denver is all condensed into a single binary variable, indicating that road trip began on a particular day.

Road Trip Lookup

Team Index Away Team 1 2 3
1 Portland 2,3,4, 3,4,5, 4,5,6,
2 Sacramento 1,3,4, 3,4,5, 4,5,6,
3 Oakland 1,2,4, 2,4,5, 4,5,6,
4 LAC 1,2,3, 2,3,5, 3,5,6,
5 LAL 1,2,3, 2,3,4, 3,4,6,
6 Phoenix 1,2,3, 2,3,4, 3,4,5,
7 Utah 1,2,3, 2,3,4, 3,4,5,
8 Denver 1,2,3, 2,3,4, 3,4,5,
9 OKC 1,2,3, 2,3,4, 3,4,5,
10 Dallas 1,2,3, 2,3,4, 3,4,5,
11 San Antonio 1,2,3, 2,3,4, 3,4,5,
12 Houston 1,2,3, 2,3,4, 3,4,5,
13 New Orleans 1,2,3, 2,3,4, 3,4,5,
14 Memphis 1,2,3, 2,3,4, 3,4,5,
15 Minneapolis 1,2,3, 2,3,4, 3,4,5,

Binary Decision Variable

Team Index Away Team Trip 1 Trip 2 Trip 3
1 Portland 0 0 0
2 Sacramento 0 0 0
3 Oakland 0 0 0
4 LAC 0 0 0
5 LAL 0 0 0
6 Phoenix 0 0 0
7 Utah 0 0 0
8 Denver 0 0 1
9 OKC 0 0 0
10 Dallas 0 0 0
11 San Antonio 0 0 0
12 Houston 0 0 0
13 New Orleans 0 0 0
14 Memphis 0 0 0
15 Minneapolis 0 0 0

Objective Function

All 60,525 variables are multiplied by the total distance of the road trip, resulting in an extremely long equation.

objective_value = (rt_1 * rd_1) + (rt_2 * rd_2) ... (rt_60,524 * rd_60,524) + (rt_60,525 * rd_60,525)

rt = road_trip

rd = road trip distance

Constraint #1

Teams can only play once per day. Below is an example of a violation of this constraint. The Linear Programming Constraint ensures teams never play on the same day and the example below is just for demonstration.

Because all teams play every other day, as long as teams are no teams double booked for a game, no back to backs will occur.
Away Team 12/21/2018 12/22/2018
Portland Portland@OKC
Oakland Oakland@Sacramento
Utah Utah@LAL
Denver Denver@Phoenix
OKC OKC@Denver
San Antonio
New Orleans New Orleans@LAC
Memphis Memphis@San Antonio
Minneapolis Minneapolis@Dallas

Constraint #2

Teams play the minimum amount of games to complete an 82 game season. The constraint does not merely ensure that teams play 82 games but that they play particular teams the right amount of times. This constraint forces the model to contain non-zero values. (A model with all zeros would be the minimum amount of miles but no games would be played.) The Linear Programming models actually produced two extra games that had to be deleted manually after.

Full Season Breakdown

Constraint #3

All decision variables must be binary (or just 1's and 0's). A team cannot play a decimal of a game and the model only makes sense with road trips occurring, a "1", or a road trip not occurring, a "0".