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 | |
| Sacramento | ||
| Oakland | Oakland@Sacramento | |
| LAC | ||
| LAL | ||
| Phoenix | ||
| Utah | Utah@LAL | |
| Denver | Denver@Phoenix | |
| OKC | OKC@Denver | |
| Dallas | ||
| San Antonio | ||
| Houston | ||
| New Orleans | New Orleans@LAC | |
| Memphis | Memphis@San Antonio | |
| Minneapolis | Minneapolis@Dallas |