Scheduling the Big Ten

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 M in the conference, and a set D of allowable days for play.  We’ll use |D|=13 days and a “round robin” model, so byes aren’t a factor (|M|=14 for the Big Ten).

M := \{\text{1, \dots, 14}\}

D := \{1, \dots, 13\}

Our binary decision variables are intuitively x_{ijt}=1 if team i\in M hosts team j\in M on day t\in D, and 0 otherwise, with i\neq j.

An obvious constraint is that teams can play at most once each day, whether they are home or away.

\displaystyle\sum_{\substack{j\in M: \\ j\neq i}} \left( x_{ijt} + x_{jit} \right) \leq 1 \phantom{XXXXX}\forall i\in M, t\in D

In this fictional model, we will also impose the “round robin” constraint that requires each team to play every other team once.

\displaystyle\sum_{t\in D} \left( x_{ijt} + x_{jit} \right) = 1\phantom{XXXXX}\forall i\in M, j\in M : i<j

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 \left \lceil{\frac{|D| - 1}{2}}\right \rceil home games.

\displaystyle\sum_{\substack{j\in M: \\ j\neq i}} \displaystyle\sum_{t\in D} x_{ijt} \geq \left \lceil{\frac{|D| - 1}{2}}\right \rceil \phantom{XXXXX}\forall i\in M

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.

\displaystyle\sum_{\substack{j\in M: \\ j\neq i}} \displaystyle\sum_{\substack{s\in D: \\ t\leq s \leq t+2}} x_{ijs} \leq 2 \phantom{XXXXX} \forall i\in M, t\in D: t\leq |D| - 2

\displaystyle\sum_{\substack{j\in M: \\ j\neq i}} \displaystyle\sum_{\substack{s\in D: \\ t\leq s \leq t+2}} x_{jis} \leq 2 \phantom{XXXXX} \forall i\in M, t\in D: t\leq |D| - 2

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.

big10_objective_screenshot

There are only seven instances in the entire season of teams playing back-to-back away games.  Not bad!

Advertisements

7 thoughts on “Scheduling the Big Ten

  1. I always enjoy posts about sports 🙂 It was great that you had this opportunity as an undergrad and that it was actually used. It was interesting to read about how you iterated with the commissioner to come up with the schedules. This behavior is pretty typical – decision makers often know a “good” solution when they see it but have trouble putting the requirements in words and forget other requirements. Real applications with multiple stakeholders can be much more frustrating. We’ll talk about that in class later!

    Like

  2. I thought this entire post was really interesting! I had never thought about it before, but conference scheduling is such a great application of OR. I bet Athletic Directors at the high school level spend countless hours trying to figure out their schedules, so it’s good to know that most universities are using a more sophisticated approach.

    Here are two questions I had after reading your post:

    1. How did you end up working on these models? Is the “Center for Athletic Scheduling” a part of the Department of Industrial Engineering/OR in Stevens Point? Is it typical for undergrads to work there? It sounds like a cool experience, so I’d be interested to know how you originally got involved with it.

    2. Did ever need to consider the previous year’s schedule in your model’s constraints? In football, for example, I know the Badgers alternate between playing home or away each year with teams like Minnesota, so I’m curious if multiple years are considered when solving instances of these models.

    Like

    1. Good questions!

      1. The Center for Athletic Scheduling is a brainchild of one of the professors of mathematics at UWSP. He started it as a way for students to get experience applying their operations research skills in a real-world setting. Undergraduate students are recruited from the operations research courses he teaches, which have an emphasis on modeling in AMPL. An IE/OR department would be a more appropriate place for this little operation, but Mathematical Sciences is the closest thing you’ll find at UWSP.

      2. Previous years’ schedules were definitely a consideration when building these models. This was often for the reason you stated; a matchup between two schools should not always be played at the same location. In fact, it was not uncommon to work on multi-year, multi-sport schedules for conferences. Some teams wanted two of their sports to travel together as often as possible to reduce travel costs. Others wanted two of their sports to not play at home on the same days because of facility constraints. In these extreme cases, our decision variables represented whether or not a team played another team at home…on a certain day…in a certain sport…in a certain year. A veritable alphabet soup of subscripts.

      Like

  3. I’m wondering how this kind of approach could be applied on a very large scale to block course registration for university freshmen. For example, ensuring that each one takes certain gen-ed classes at times that don’t conflict with one another. How might models also be used to impact the course offering times that the university chooses to offer, and even the number of seats made available?

    Like

    1. I’ve definitely seen integer programming applied to department course scheduling at a university level. To the best of my knowledge, UWSP’s Mathematical Sciences department still employs a mathematical model to schedule courses. It takes instructors’ preferences (preferred time to teach, preferred days to teach, etc.) and course overlap into account. Similar models seek to balance these, or any number of different objectives.

      For the problem you describe, I think a good model would use a data set that shows the general education courses each student would like to take in a particular semester. The university has a set of courses to offer, available time slots, and available rooms with given capacities. The model’s decision variables would be whether or not to offer a general education course at a particular time slot in a particular room. The model’s objective would be to minimize the total number of general education courses that students “miss out on”; course capacity constraints or overlap between two desired courses define a “missed” course. Alongside basic logical constraints (only one course in a room at a time), university-specific constraints would help define the model (how many of each course can feasibly be offered).

      Survey-based data seems the most reliable. Historical data from past semesters will not accurately reflect students’ course preferences, as the courses taken by students were naturally restricted by the university’s timetable. We’ll never know how many students wanted to take both Math 105 and Biology 101 last semester. They were only offered at overlapping times!

      Depending on how intricate the model is and how many general education courses a university is trying to coordinate, the model could be very large and difficult to solve to optimality.

      That said, modeling in a timetabling context is not my area of focus. It’s likely that others have published papers outlining solution methods for your described model.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s