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.

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:

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):

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.