Published July 8, 2021
For Professor Mark Karwan, working with the Center for Computational Research (CCR) has been instrumental in facilitating his work with the National Football League (NFL). Since 2018, Dr. Karwan has used up to 100 machines per night on CCR’s industry cluster to help solve one of the NFL’s more computationally challenging problems.
For the NFL proper scheduling of 256 games (now 280 since adding a 17th game) is an extremely difficult task. In order to create a very good and not just a ‘playable’ schedule, considerations beyond the predetermined “who plays who” any given year contain many factors aimed towards fairness of schedule. This includes number of consecutive road trips, starting/ending with too many games on the road, consecutive coast to coast trips, playing against many teams that are coming off more rest, etc. On top of all these factors, large complications arise from having 40% of all stadium times being blocked due to pre-arranged national touring concerts, college bowl games, MLB conflicts (typically schedule first), and many more. Add in broadcast contract obligations and offering a quality set of televised games each weekend throughout the season, and you have a seriously complex challenge to solve.
In order to work a viable solution, Professor Karwan models the problem as a large-scale mixed integer linear programming (MILP) problem, which is standard for many types of scheduling problems. The model itself has over 10,000 variables and constraints, growing in complexity as the scheduling season evolves and new conditions are added. This model is so complex that regular solution techniques can not generate a feasible solution in a lifetime of computing. Thus, the current approach focuses on fixing roughly 50-80 matchups (day/time/network) and completing the schedule, if possible, using MILP software. This involves strategically seeding (fixing) these games in many thousands of trials, on many machines, and running each trial up to 8-12 hours over night. The NFL often uses up to 1500 machines on the AWS cloud each night for three months combing the infinite solution space for better and better schedules. Over the past three years, Dr. Karwan has explored many avenues for both developing new schedules, modifying the seeding algorithms, and polishing existing schedules by seeding on a set of games from an already feasible schedule.
This partnership has been extremely rewarding for Professor Karwan and his group at UB who have been working alongside an excellent team of folks at the NFL and their main software partner. Dr. Karwan states “I can guarantee that besides the fun involved in this effort, it is the most academically challenging problem I have ever seen as an MILP expert with more than 40 years of experience.”