I’m Eli Towle, a second year Ph.D. student here at UW – Madison. My research focuses on optimization, especially integer, linear, and stochastic programming. Currently, I’m working on a cutting plane approach to solving the stochastic network interdiction problem. There might be more on that later in the semester! I’ll kick off my first blog post with a basic overview of athletic scheduling, because everybody loves sports and equations. Athletic scheduling probably doesn’t save many lives, but it certainly is a tricky problem that is often done suboptimally.
As I briefly touched upon last week, I was employed as a modeler at the Center for Athletic Scheduling at UW – Stevens Point during my undergraduate career. This was my first experience using operations research to benefit others in a tangible way. After a schedule request from a collegiate conference was received, modelers like myself would accept jobs and begin working directly with conference commissioners and coaches to create a schedule within the provided parameters. After the initial model was built in AMPL, there was always some tweaking involved in fine-tuning the schedule to meet the commissioner’s tastes. It was a miracle to not hear “Oh, I forgot that School A has homecoming that weekend,” or “Can these two teams both be home on the second Tuesday?” after sending out a schedule for review.
Let’s look at the model, using the Big Ten Conference as an example. At its core, the model itself is pretty straightforward. We begin by defining a set of teams in the conference, and a set of allowable days for play. We’ll use days and a “round robin” model, so byes aren’t a factor ( for the Big Ten).
Our binary decision variables are intuitively if team hosts team on day , and otherwise, with .
An obvious constraint is that teams can play at most once each day, whether they are home or away.
In this fictional model, we will also impose the “round robin” constraint that requires each team to play every other team once.
Another consideration is that teams have roughly equal home and away games. We can do this in a single constraint that says each team has at least home games.
A final consideration is that teams cannot have too many home or away games in a row. The final schedule should be a healthy mix of home and away games. For example, we can require that at most two of any three consecutive games can be played at home. Similarly, at most two of any three consecutive games can be played away.
And just like that, our model is finished! Note that this is simply a feasibility problem; we aren’t attempting to minimize or maximize anything. Depending on the conference, we might try to minimize the number of times teams play two away games in a row, distance traveled, etc. A completed model, which introduces additional binary variables to minimize the number of times teams play back-to-back away games, is below.
There are only seven instances in the entire season of teams playing back-to-back away games. Not bad!