Category Archives: Heuristics

Improving Traveling Umpire Solutions the Miami Heat Way: Not one, not two, not three…

Those who know me are aware of my strong passion for basketball, so I had to find a way to relate this post to my favorite sport. Fans of basketball in general, and of the Miami Heat in particular, might be familiar with this video clip in which LeBron James makes a bold prediction. Back in 2010, when asked how many titles the Heat’s big three would win together, he replies “Not one, not two, not three, not four, not five, not six, not seven, …” While I’d love to see them win 8 titles, it sounds a bit (a lot) unlikely. But I can’t complain about their record so far. Winning 2 titles in 3 finals’ appearances isn’t bad at all. But what does this have to do with baseball umpires? Let’s get back to OR for a moment.

A couple of years ago, I wrote a post about scheduling baseball umpires. In that same article I co-authored with Hakan Yildiz and Michael Trick, we talked about a problem called the Traveling Umpire Problem (TUP), which doesn’t include all the details from the real problem faced by MLB but captures the most important features that make the problem difficult. Here’s a short description (detailed description here):

Given a double round-robin tournament with 2N teams, the traveling umpire problem consists of determining which games will be handled by each one of N umpire crews during the tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team or venue too often.

And when I say difficult, let me tell you something, it’s really hard to solve. For example, there are 16-team instances (only 8 umpires) for which no feasible solution is known.

Two of my Brazilian colleagues, Lucas de Oliveira and Cid de Souza, got interested in the TUP and asked me to join them in an effort to try to improve the quality of some of the best-known solutions in the TUP benchmark. There are 25 instances in the benchmark for which we know a feasible solution (upper bound) and a lower bound, but not the optimal value. Today, we’re very happy to report that we managed to improve the quality of many of those feasible solutions. How many, you ask? I’ll let LeBron James himself answer that question:

“Not one, not two, not three, … not ten, … not eighteen, … not twenty-three, but 24 out of 25.”

OK, LeBron got a bit carried away there. And he forgot to say we improved 25 out of the 25 best-known lower bounds too. This means those pesky optimal solutions are now sandwiched between numbers much closer to each other.

Here’s the approach we took. First, we strengthened a known optimization model for the TUP, making it capable of producing better bounds and better solutions in less time. Then, we used this stronger model to implement a relax-and-fix heuristic. It works as follows. Waiting for the optimization model to find the optimal solution would take forever because there are too many binary decision variables (they tell you which venues each umpire visits in each round of the tournament). At first, we require that only the decisions in round 1 of the tournament be binary (i.e. which games the umpires will be assigned to in round 1) and solve the problem. This solves pretty fast, but allows for umpires to be figuratively cut into pieces and spread over multiple venues in later rounds. Not a problem. That’s the beauty of math models: we test crazy ideas on a computer and don’t slice people in real life. We fix those round-1 decisions, require that only round-2 variables be binary, and solve again. This process gets repeated until the last round. In the end, we are not guaranteed to find the very best solution, but we typically find a pretty good one.

Some possible variations of the above would be to work with two (or more) rounds of binary variables at a time, start from the middle or from the end of the tournament, etc. If you’re interested in more details, our paper can be downloaded here. Our best solutions and lower bounds appear in Table 10 on page 22.

We had a lot of fun working on the TUP, and we hope these new results can help get more people excited about working on this very challenging problem.

Leave a comment

Filed under Applications, Heuristics, Integer Programming, Research, Sports, Traveling Umpire Problem

What Do Locker Rooms, Airplanes, and Urinals Have in Common?

If you go (or have ever gone) to a reasonably large gym, you might have encountered the typical locker room changing area. It looks like this:

locker

If you go to the gym regularly (or have been a regular gym goer at some point in your life), you might have noticed an issue that arises with some frequency: the locker you’re trying to access is very close to one in front of which someone else is standing (because their locker is right next to yours). I’ll refer to this phenomenon as interference. Interference is annoying because it creates that awkward situation in which you stand there trying to be polite and wait for the other person to finish, while at the same time getting upset because you’re wasting your precious time: “Man, I was hoping to be finished with my workout in 45 minutes. I gotta go back to the office and work on that integer programming model. Why does this guy take so long to tie his shoes?”

Interference occurs in other places, of course; hence the title of this post. When boarding planes, airlines try to be as efficient as possible, that is, they try to get everyone in their seats and ready to go in the shortest possible time. What is interference during the boarding of a plane? It’s when passengers that are standing in the aisle (e.g., because they’re still trying to put their carry-on in the overhead bin) block the passage of other passengers whose seats are further down the aisle. You might think that the obvious solution is to board everyone starting from the back of the plane towards the front, right? Well, maybe. Back-to-front boarding is intuitively good, but there are other issues at play: some passengers have priority, not everyone is there when boarding starts, etc. Another strategy that seems to work well is a hybrid of back-to-front with window-to-aisle. As you might have guessed, people have used optimization and simulation to try and come up with good boarding strategies. One of these studies was published in the journal Interfaces in 2005: “America West Airlines Develops Efficient Boarding Strategies”. This is an interesting read, and I recommend it.

Where else does interference occur? This XKCD blog post talks about the International Choice of Urinal Protocol:

…the basic premise is that the first guy picks an end urinal, and every subsequent guy chooses the urinal which puts him furthest from anyone else peeing.  At least one buffer urinal is required between any two guys or Awkwardness ensues.

Randall then proceeds to analyze this protocol and concludes that it suffers from a problem of underutilization of the available urinals, depending on how many of them there are. However, if guys are smart when picking urinals, they can achieve the optimal utilization (50%).

Now back to the locker room interference problem (which is the one that bothers me most lately). Let’s try to figure out the source of the problem and propose a solution to it. When you arrive at the University of Miami gym (known as the Wellness Center), you hand in your ID to an attendant who, in return, hands you a key that’s taken from a set of drawers that look like this (men’s lockers on the left, women’s on the right):

keydrawers

A key comes out of the drawer and your ID goes in. Interference is created because the attendants do not (and cannot) remember which keys they have handed out recently and what the layout of the locker room looks like. (By the way, locker numbers are not in perfect sequence in the Wellness Center; numbers jump around and you frequently see people who are lost looking for their lockers.) Ideally, what we’d like to happen is for keys to be handed out in such a way that they send the next person to a locker that is far away from the last few lockers that were given away. There are other complicating issues, of course, such as the fact that you cannot control the people who are returning from their workouts, but at least you can reduce interference among new arrivals.

We don’t need to write a mathematical model for this (or do we?). Why not pre-calculate an optimal sequence of locker hand-outs (based on the locker room layout), sort the drawers in that sequence (left to right, top to bottom), and have the attendants hand out keys in this order, cycling back to the top after they reach the last drawer? It won’t be perfect, but it sure will be better than the current system.

5 Comments

Filed under Applications, Heuristics, Modeling

MLB Umpire Scheduling

There are two purposes to this post. First, I’d like to follow-up on Michael Trick’s post on the importance of teaching and its relationship with research. One of the points Mike makes is that your next exciting research or consulting project may come from current or former students. Those of us who teach undergraduate and MBA classes have the opportunity to network with (future) managers and practitioners who will eventually put their training to the test, producing actual answers to real-life problems. And if one of those problems requires more OR knowledge than what they had the opportunity to learn in school, they might remember their friendly neighborhood OR professor. Another way research can come out of teaching is during hands-on projects. Back in 2006, Mike was in charge of an elective OR-project class that allows MBA students to try their hands on a real-life problem; in that case umpire scheduling. To my delight, Mike invited me to be the TA for that course and I gladly accepted. The rest is history.

The second purpose of this post is to help myself keep track of the recent news stories about our umpire scheduling paper. Thanks to an excellent job by the PR departments at the University of Miami School of Business (thanks, Catharine!) and Michigan State University, the story has appeared in numerous outlets. As a matter of fact, I’m very excited to report that Scientific American had a 60-second science podcast about our work:

August 18Scientific American: Researchers Tell Umpires Where to Go (PDF version)

Here are a few other news outlets that covered the story (I’m trying to keep this list up-to-date for my own sake). I’m also providing a link to a PDF version of each story in case the web pages are taken offline:

April 2012, The Spring issue of Business Miami Magazine has an article about our work entitled Road Trip (PDF version).

October 19, WAMC Northeast Public Radio Academic Minute. I recorded a 1:45-minute explanation of the problem, approach, and results which aired as one of WAMC’s Academic Minutes on the same day of the first game of the World Series. That was a lot of fun! Click on the link to listen. If the link doesn’t work, here’s the MP3 file.

September 6, Miami New Times: Tallys Yunes, UM Professor, Solves MLB’s Umpire Scheduling Dilemma (PDF version). This article also appeared in print, in the September 8-14 issue of Miami New Times. Here’s a PDF scan of that.

August 3, PhysOrg: University of Miami Business Professor Helps Create a Successful Scheduling Method for Umpires in Major League Baseball (PDF version)

August 3, HPCwire: Business Prof Solves Traveling Umpire Problem for Major League Baseball (PDF version)

July 31, University of Miami School of Business: School’s Management Science Research Resolves Major League Baseball’s Umpire Scheduling Challenges (PDF version)

July 21, ScienceDaily: Scholar Helps Make Major League Baseball Umpire Schedule a Hit (PDF version)

July 21, ThePostGame: MLB Umpires Have a Turkish Secret Weapon (PDF version)

July 20, PhysOrg: Michigan State Scholar Helps Make MLB Umpire Schedule a Hit (PDF version)

July 20, Michigan State University News: Michigan State Scholar Helps Make MLB Umpire Schedule a Hit (PDF version)

I greatly enjoy the teaching side of my job because I believe it complements the research side quite well. I’m looking forward to bringing articles like the ones above to my classes in the Spring and I’m sure they’ll be well received.

Further acknowledgments: thanks to those who also helped spread the word about the umpire scheduling problem on Twitter, especially Paul Rubin (@parubin), Aurélie Thiele (@aureliethiele), and @INFORMS (is that you, Mary Leszczynski? :-).

3 Comments

Filed under Applications, Heuristics, Promoting OR, Research, Sports, Teaching, Traveling Umpire Problem

Rescue Mission, Part 3 of 3

Make sure to read part 1 and part 2 first!






Notes:

The Edelman Award presentations are available here.

The INFORMS Public Information Committee (PIC) web page is here.

A long list of real-life applications of Analytics and O.R. is available here.

The topographic maps above are actual maps of Mars.

2 Comments

Filed under Applications, Heuristics, INFORMS Monthly Blog Challenge, Promoting OR

Rescue Mission, Part 2 of 3

Make sure to read part 1 first!





TO BE CONTINUED… Read part 3 here!

Notes:

The paper by Trick et al. is available here.

The Science of Better podcasts are available here.


Leave a comment

Filed under Applications, Heuristics, INFORMS Monthly Blog Challenge, Promoting OR

Rescue Mission, Part 1 of 3







TO BE CONTINUED…  Read part 2 here!

Note: The topographic map above is an actual map of Mars.


1 Comment

Filed under Applications, Heuristics, INFORMS Monthly Blog Challenge, Promoting OR