Category Archives: Applications

Fourth of July Logistics in Coral Gables: No OR, No Glory

After a six-year hiatus, the city of Coral Gables and the Biltmore Hotel decided to host the Fourth of July celebrations once again including, of course, a very nice fireworks display on the Biltmore 18-hole golf course. My wife and I had watched the Independence Day fireworks at Biscayne bay and on the beach the past two years, so we thought this would be a nice change.

At the outset, the event seemed to be very well organized with buses and trolleys departing from four different places in the city to take people to the hotel, as shown in the map below.

So we parked our car at the Andalusia garage (Garage 4 on the map) and took the 6pm trolley. There was going to be a concert starting at 7pm, while the fireworks would go off at 9pm. We found a nice spot to place our chairs and my wife’s camera tripod, so we sat down and relaxed. Numerous food trucks offered plenty of tasty choices, the concert was entertaining and, most importantly, we loved the fireworks. All in all, we were very pleased with the whole thing. The problems started once the fireworks ended. Take a look at this map.

The red arrows indicate the flow of people trying to exit the golf course through a single narrow path (people coming from all directions were converging to that point). The yellow arrows start at the trolley/bus stop (a single stop) and show the path the trolleys/buses would take to go back to the garages in the previous map.

By now you’ve already guessed what happened, but I’ll list some of the main problems: (1) large congestion to exit the golf course (bottleneck); (2) no organized lines were formed by the police; people simply aggregated as a large mass at the bus stop (forget about FIFO); (3) tons of people actually drove their cars and parked not only in the parking lot depicted above, but also all around the neighborhood surrounding the hotel. Therefore, the yellow bus path was full of pedestrians walking to their cars (or walking home) and the police did not allow trolleys/buses to come in or out while there were pedestrians on the road (that is, forever); (4) we were given no indication as to which would be the destination of the incoming trolley/bus until they were parked at the stop (crowd left in the dark = annoyed crowd).

After standing there for a while, my wife and I decided that it would be much faster and less stressful if we simply walked back to Garage 4 (a 1.3-mile, 25-minute walk). Yes, it was very hot that day, and we had to carry some heavy chairs and equipment, but it was better than suffering through the chaos.

As an Operations Research person, I couldn’t stop thinking of all the bad decisions that were made by the organization of this event. I know they meant well, but everyone’s experience would have been much more enjoyable if they did a few things differently. Some of my suggestions below require conveying information to the attendees ahead of time, but this could have been accomplished by handing out flyers to people as they arrived. (Arrivals were not a problem because they were spread out over 3.5 hours, between 5 and 8:30pm.)

  • Divide the crowd by telling people to exit the golf course through different paths depending on where they’re headed: those walking home exit through gate A, those walking to the Biltmore parking lot exit through gate B, those wishing to catch a trolley/bus, exit through gate C, etc.
  • Have multiple bus stops, reasonably away from each other.
  • Have barricades set up so that: (1) lines are properly formed at the bus stops, (2) pedestrians do not walk on the road and impede the flow of trolleys/buses.
  • Schedule the return trips of trolleys/buses in advance and tell people to come to the bus stop at their assigned time based on desired destination (à la Disney fast pass).

These are just some ideas that came to mind right away, but I bet more improvements are possible (what would you have done, dear reader?). Judging by how many of my friends who did not attend the event already knew it had had a chaotic ending even before I told them, I’m sure the city received plenty of feedback. I expect next year’s event to run much more smoothly. However, just in case they need a little extra help, I’d like to write a quick letter to the City of Coral Gables:

Dear City of Coral Gables:

I’m a professor at the University of Miami who specializes in using advanced analytical methods to help with decision making. If you need help with the logistics of your Fourth of July Fireworks or any other city-sponsored activity, I’m available. Here’s my contact information.

Sincerely,

Tallys Yunes.

To end this post on a happy note, here are some beautiful photos of the fireworks taken by my favorite photographer. Enjoy!

1 Comment

Filed under Applications, Holidays, Promoting OR

The “Real” Reason Bill Cook Created the TSP App

By now, most people are aware of the latest Internet meme Texts from Hillary which is, by the way, hilarious. You’re also probably aware that Bill Cook created an iPhone App that allows one to solve traveling salesman problems (TSP) on a mobile phone! If you like optimization, you have to give this App a try; and make sure to check out the Traveling Salesman book too!

Inspired by Texts from Hillary I finally figured out the “real” reason why Bill Cook created the App. Here it is:

1 Comment

Filed under Applications, Books, iPhone, Meme, People, Promoting OR, Traveling Salesman Problem

How Should Santa Pair Up His Reindeer?

It’s almost Christmas time and Santa is probably very busy with some last-minute preparations before his longer-than-7.5-million-kilometer trip around the world. One of the many things he has to worry about is how to pair up his reindeer in front of the sleigh. We all know that Rudolf goes right in front of everyone else because of his shiny nose, but what about his other eight four-legged friends? The traditional Christmas carols tell us that the reindeer are typically arranged in four pairs, front to back, as follows:

Dasher, Dancer

Prancer, Vixen

Comet, Cupid

Donner, Blitzen

Therefore, we are going to assume that this is an arrangement that works pretty well (after all it’s been working since 1823). As someone with a degree in a STEM field (he wouldn’t reveal which, though), Santa can’t stop thinking about this interesting question: “Are there other good ways to pair up my reindeer?” Before we can answer that question, we need to define what a “good” pairing of reindeer is. After working tirelessly on Christmas eve, Santa’s reindeer have all the other 364 days of the year to hang out and get to know each other. As in every group of friends who spend a lot of time together, some friendships become closer than others. So it’s reasonable to expect that Rudolf’s eight friends will have a favorite companion for side-by-side galloping, a second favorite, a third favorite, etc. In addition, there’s one more important detail when it comes to reindeer pairings, according to Mrs. Claus: some of them like to be on the left side (Dasher, Prancer, Comet, and Donner), while others prefer to ride on the right side in front of Santa’s sleigh (Dancer, Vixen, Cupid, and Blitzen). Before you mention that I should also consider that male reindeer would rather be side-by-side with female reindeer, there’s scientific evidence that all of Santa’s reindeer are female, so we don’t have to worry about that.

After a nice conversation in front of his cozy fireplace, Santa was kind enough to provide me with the following lists of pairing preferences for each of his reindeer; though he vehemently asked me not to show any of this to his furry friends. I’m counting on you, my readers, to keep these lists to yourselves! The names in each list are sorted in decreasing order of pairing preference. The lefties appear in blue, while the righties appear in red (any resemblance to US political parties is a mere coincidence):

Dasher: Dancer, Cupid, Vixen, Blitzen

Prancer: Vixen, Blitzen, Dancer, Cupid

Comet: Cupid, Dancer, Blitzen, Vixen

Donner: Blitzen, Vixen, Dancer, Cupid

Dancer: Prancer, Comet, Dasher, Donner

Vixen: Dasher, Donner, Prancer, Comet

Cupid: Prancer, Dasher, Comet, Donner

Blitzen: Comet, Prancer, Donner, Dasher

Note that if we were to adhere to the lefties’ first picks, we’d end up with the traditional line-up. We are now ready to define what a good pairing is: a pairing is good (a.k.a. stable) if no one has an incentive to change pairs. In other words, if A is paired up with B, and A prefers C to B, it so happens that C, who is paired up with D, prefers D to A. (Note: this problem is known in the literature as the stable marriage problem and it arises in real life, for example, in the context of the National Resident Matching Program, which pairs up medical residents with hospitals every year in the United States.) Obviously, the traditional pairing shown above satisfies these goodness/stability conditions, given the reindeer’s preferences.

What Santa would like to know is whether or not there are other good pairings in addition to the traditional one. If so, he can add some variety to his line-up and the reindeer won’t get so bored by galloping side-by-side with the same companion every year. How can we help Santa answer this question? Using Operations Research, of course! More precisely, Constraint Programming (CP).

Constraint Programming is a modeling and solution paradigm for feasibility and optimization problems that allows one to represent complicated requirements (such as the stability condition above) in ways that are often easier and simpler than using traditional O.R. techniques such as Integer Programming. For example, indexing variables with variables and expressing logical constraints such as implications are a piece of cake in CP. Here’s a CP model written in the Comet language (not to be confused with Comet the reindeer) that answers Santa’s question. It essentially enforces the stability condition for every choice of A, B, C, and D.

The good news is that, in 3 milliseconds, that CP model finds all of the five different stable pairings. Here they are:

Update (1/1/2012): Here’s an AIMMS version of the CP model, kindly created and provided by Chris Kuip. Look for this reindeer example, including an accompanying graphical user interface, in an upcoming update to the set of examples in AIMMS.

I hope Santa reads this blog post before Christmas eve, but in case he doesn’t, please tell him to check this out if you run into him this holiday season. I’m sure his reindeer would appreciate a little change after 189 years.

9 Comments

Filed under Applications, Constraint Programming, Holidays, Modeling, Traveling Salesman Problem

Choosing Summer Camps for Your Kids

Today I’m going to write about a decision that’s made by many American families each year: how to pick summer camps for our kids. There are several issues to take into account, such as cost, benefit, hours, and kids’ preferences. I’ll introduce an optimization model for summer camp selection through a numerical example. The example portrays a large family, but the same ideas apply if a few smaller families want to get together and solve this problem. This way they can take advantage of the discounts and take turns driving the kids around.

The Joneses have six kids: Amy, Beth, Cathy, David, Earl and Fred (yes, their first names are alphabetically sorted, matching their increasing order of age; Mr. and Mrs. Jones always knew they’d have six kids and hence named their firstborn with an ‘F’ name). This year, they’ve narrowed down their list of potential summer camps to the following ten: Math, Chess, Nature, Crafts, Cooking, Gymnastics, Soccer, Tennis, Diving, and Fishing. The Nature camp takes kids on a hike through the woods with the guidance of a biologist; they make frequent stops upon encountering specific plants and animals, during which a mini science lecture is delivered (pretty cool!). The Cooking camp involves cooking chemistry instruction, à la Alton Brown (also pretty cool).

The following table contains some data related to each camp:

The Cost column indicates the cost per child. The Discount column indicates the percentage discount that each child enrolled after the first would receive on the cost of each camp. For instance, if three children are enrolled in Math camp, the first would cost $1100, and the second and third would cost $770 each (30% less). The Hours column is self-explanatory and the last two columns indicate whether or not that particular camp develops mental and physical abilities, respectively (a value of one = yes, zero=no).

The next table shows some of the child-specific requirements:

For example, the Joneses want Fred to attend at least 3 camps that develop mental abilities, and at least 1 camp that develops physical abilities. The last two columns in the above table indicate the minimum and maximum number of camp hours for each child over the 9-week summer break.

The next thing parents need to take into account are their children’s preferences. So here they are:

The smaller the number in the above table, the more desirable a particular camp is. For example, Amy is a bit of a math nerd, and if we were to flip David’s preference scores for Math and Tennis, he could be classified as a bit of a jock. Some conflicts exist, in the sense that not all camps are compatible with each other in terms of time schedules. In this particular case, let’s assume that no child can attend both the Soccer and Tennis camps, or both the Nature and Soccer camps. Here’s how we are going to use this preference table to create a sense of fairness among the children: whenever a child that prefers camp X to camp Y goes to camp Y and doesn’t go to camp X, nobody else gets to go to camp X either. For example, if Amy goes to Nature camp and isn’t sent to either Math or Chess camp, none of her siblings are allowed to go to Math or Chess either. Conversely, if the Joneses decide to send Earl to Chess camp and Fred to Tennis camp, they must also send Earl to Tennis camp (because Earl prefers Tennis to Chess, and “Fred is going! Why can’t I go too!”). Clearly, there are other ways to use/interpret this table, such as trying to send everyone to at least one of their top N choices, but we won’t consider those alternatives here.

After taking all of the above issues and conditions into account, here’s a solution that satisfies all the requirements while resulting in the minimum cost of $22,180.00 (You guessed it…the Joneses are probably *not* among the 99%):

Amy goes to Math, Crafts, Cooking, and Tennis; Beth goes to Math, Cooking, Tennis, and Fishing; Cathy goes to Math, Crafts, Tennis, and Fishing; David goes to Math, Cooking, and Fishing; Earl goes to Math, Tennis, and Fishing; and Fred goes to Math, Crafts, Cooking, and Tennis. Mmm…interestingly, everyone goes to Math camp. I think the Joneses are on to something…

Depending on your own requirements, preferences, and costs your solution may differ, of course. But this should give you an idea of how this simple problem can easily become very complicated to solve. No need to fear, though! Operations Research is here!

Food for Thought: Here’s an interesting question that helps illustrate how high-quality solutions can be counterintuitive: by looking at the preferences table, we see that everyone prefers Soccer to Tennis. In addition, Soccer camp is less expensive than Tennis camp. So how come we send almost everyone to Tennis camp? Isn’t that strange? Let me know what you think in the comments below! That’s one of the advantages of using an analytical approach to decision making: it helps us find solutions we wouldn’t even consider otherwise because they don’t seem to make sense (at least not at first).

If you’re curious about how I managed to find the optimal solution, read on!

Details of the Analysis:

To find the minimum-cost solution, we can create a mathematical representation of the problem, a.k.a. a model, and then solve this model with the help of a computer. Let’s see how.

The first obvious decision to make is who goes where. So let the binary variable x_{ij} equal 1 when child i goes to camp j, and equal to 0 otherwise. We’ll also need another binary variable y_j that is equal to 1 when at least one child goes to camp j and equal to 0 when none of the children go to camp j. We are now ready to write our objective function and constraints. I’ll refer to the problem data using the column headings of the tables above. The subscript i will always refer to a child, and the subscript j will always refer to a camp.

To minimize the total cost, we write the following objective function:

\displaystyle \min \sum_i \sum_j (1-\mathrm{Discount}_j)\mathrm{Cost}_j x_{ij} + \sum_j \mathrm{Discount}_j \mathrm{Cost}_j y_j

Note how we are using the y_j variable to handle the discount for sending more than one child to camp j: we charge every child the discounted price in the double summation and add the discount back in only once if y_j=1.

Now we have to deal with the four requirements: minimum and maximum hours, mental activity, and physical activity. For every child i, we have to write the following four constraints:

\displaystyle \sum_j \mathrm{Hours}_j x_{ij} \geq \mathrm{MinTimeReq}_i

\displaystyle \sum_j \mathrm{Hours}_j x_{ij} \leq \mathrm{MaxTimeReq}_i

\displaystyle \sum_j \mathrm{IsMental}_j x_{ij} \geq \mathrm{MentalReq}_i

\displaystyle \sum_j \mathrm{IsPhysical}_j x_{ij} \geq \mathrm{PhysicalReq}_i

Next, we enforce the preference rules. Let’s recall the example involving Earl and Fred: if Earl goes to Chess camp and someone else (it doesn’t matter who) goes to Tennis camp, then Earl has to go to Tennis camp as well. Here’s what this constraint would look like:

x_{\mathrm{Earl},\mathrm{Chess}} + y_{\mathrm{Tennis}} - x_{\mathrm{Earl},\mathrm{Tennis}} \leq 1

Of course, we have to repeat this constraint for every child i and every pair of camps j_1 and j_2 such that child i prefers j_1 to j_2 in the following way:

x_{ij_2} + y_{j_1} - x_{ij_1} \leq 1

The camp compatibility constraints say that no child i can attend both Soccer and Tennis, or both Nature and Soccer, therefore:

x_{i,\mathrm{Soccer}} + x_{i,\mathrm{Tennis}} \leq 1

x_{i,\mathrm{Nature}} + x_{i,\mathrm{Soccer}} \leq 1

Finally, we need to relate the x_{ij} and y_j variables by stating that unless y_j=1 , no x_{ij} can be equal to 1 . So we write the following constraint for all values of i and j :

x_{ij} \leq y_j

And that’s the end of our model. Here’s a representation of this mathematical model in AMPL in case you want to play with it yourself. This is the model I used to obtain the numerical results reported above. Enjoy!

5 Comments

Filed under Applications, INFORMS Monthly Blog Challenge, Integer Programming, Mathematical Programming, Modeling, Motivation, Promoting OR, Summer camp

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

Can We Use Social Networks to Identify Poor Decision Making?

While suffering through the usual air travel woes recently, I felt compelled to tweet my feelings:

I was pleasantly surprised to see that Paul Rubin and Matthew Saltzman followed up with an interesting exchange:

Although I tend to agree with Paul that an outsider probably does not have enough information to decide whether or not the actions he/she sees are reasonably good given the situation (especially when it comes to the incredibly complex world or airline operations), I like Matthew’s general idea of an experiment to identify whether or not the outcome of a black-box decision making process is “good”.

Can that be done? Can we observe a black-box situation (or process) long enough to be able to tell whether the analytic machine inside the box could do better?

A large number of people carry smart phones these days, with constant connectivity to the internet. Twitter, Facebook, and FourSquare (to name a few) can determine our location, and there are other Apps that tell us which of our friends (and even non-friends) are close by. With all of this connectivity and location awareness, we can think of human beings as sophisticated sensors that collect and share information. We see a fire, a car accident, a traffic jam, an arrest, a fight, and immediately share that information with our network. In addition, human sensors are much better than electronic sensors because they can detect and interpret many other things, such as: the mood in a room (after the airline changes your gate for the third time), the meaning of an image, and so on.

Consider a hypothetical situation in which a crowded venue has to be evacuated for whatever reason. Perhaps some exits will be blocked and people will be directed to go certain places, or act a certain way. Human observers may notice a problem with the way security is handling the situation from multiple locations inside the venue, and from multiple points of view. The collection of such impressions (be they tweets, Facebook status updates, or something else) may contain clues to what’s wrong with the black-box evacuation procedure devised for that venue. For example, “avoid using the south exit because people exiting through there bump into those coming down the stairs from the second floor and everyone has to slow down quite a bit.”

In a world where Analytics and OR specialists struggle to convince companies to try new ideas, could this kind of evidence/data be used to foster collaboration? “I noticed that you did X when Y happened. It turns out that if you had done Z, you’d have achieved a better outcome, and here’s why…”

Is the airline example really too complicated to be amenable to this kind of analysis? I’m not sure. But even if it is, there may be other situations in which a social network of human sensors can collect enough information to motivate someone to open that black box and tinker with its inner workings a little bit. Those of you working in the area of social networks might be aware of something along the lines of what I (with inspiration from Matthew) have proposed above. If that’s the case, I’d love to read more about it. Please let me know in the comments.

1 Comment

Filed under Applications, INFORMS Monthly Blog Challenge, People, Social Networks, Travel

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