Category Archives: People

The Evil Twin and Other Fun Stories

Today marks Paul Rubin‘s retirement. To celebrate this special day in O.R.’s history, a few of us put together a nice collection of stories at http://paulsretirement.wordpress.com/ (very special thanks to go Mary Leszczynski). My personal contribution is here. If you know Paul, make sure to check it out! If you don’t know Paul…nah, everyone knows Paul.

Leave a comment

Filed under People

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

An O.R. Vocabulary Test for Non-Experts

I was talking to my wife the other day recalling how much fun she has while overhearing words from some of my research-related phone calls. We started to think about what comes to people’s minds when they hear an OR-related term whose definition is not obvious to them. I’m not talking about obscure and technical mathematical terms such as a “contrapolymatroid“, but terms at which a non-expert would actually be able to take an educated guess, such as “large-neighborhood search“. So I made a list of ten such terms and asked three friends (named A, B, and C) to define them to the best of their ability. The only rule was that they had to do it on the spot, off the top of their heads; no Googling allowed. Because none of them have training in OR, some of the answers turned out to be pretty interesting.

1. A global constraint.

A) All the stuff in the world that’s holding us back.

B) All the factors that prevent the open market from being truly open: laws, politics, foreign/domestic policy, national borders, etc.

C) Gravity.

2. Complementary slackness.

A) A dude who hangs out in a bar with no job, but complements the decor and vibe perfectly.

B) An equal and opposite reaction to whatever sectors are experiencing growth in the marketplace.

C) Time off from performing a task or responsibility granted by a superior or by oneself.

3. An odd cycle.

A) When you get your period unexpectedly; or that cycle on the washing machine that no one ever uses.

B) An economic cycle (quarter, fiscal year, etc.) which displays characteristics unlike the ones that preceded or succeeded it. In other words, in a sustained period of economic growth, it’s the one segment that shows recession.

C) A phenomenon with awkward tendencies and characteristics that is repeated every so often.

4. A spanning tree.

A) A tree that creeps from your neighbor’s yard to yours. Usually makes a huge mess in yours.

B) Has something to do with Ethernet networks.

C) A rather large plant with either a long branch span or time span on planet Earth.

5. A cutting plane.

A) A wood working tool that both cuts and planes.

B) No freaking clue.

C) A slice that intersects a 3D object in order to provide another viewpoint.

6. A shadow price.

A) The hidden cost of owning things. Like the extra cost of owning and maintaining a house or a luxury car.

B) The true representative value of goods and services, compared to the value dictated by the supply/demand of the marketplace.

C) A value for an item or service which can be obtained but that requires the buyer to perform an extensive search.

7. A comb inequality.

A) When you have a better comb than I do.

B) huh?

C) Inadequacies that persist despite efforts to eliminate them.

8. Duality gap.

A) The gap between personalities in someone with multiple personality disorder.

B) Again no idea.

C) A two-faced abyss. In other words, an alternative that may seem unfortunate but that possesses some advantages.

9. A feasible region.

A) The region where it is possible for you to live given your income, wants, and available houses.

B) Sounds like agriculture. Sorry, I got nothing.

C) An area or scope which could be a viable alternative for several purposes.

10. The first-fail principle.

A) When you get to repeat a class the first time you fail it, if approved by your high-school principal.

B) The idea that early adopters in a new sector of the market who fail will provide secondary adopters guidance through their failure. Not literal guidance, of course, but the secondary adopters will come into the marketplace and make decisions based upon others’ prior failures.

C) If you fail miserably the first time, don’t try again.

The first lesson I learned from this very non-scientific experiment is: if you’re at a party and somebody asks you what you do, you’re probably better off using an example. For instance: “Do you ever wonder how hurricane paths are estimated? That’s what I do.” You’d of course replace “hurricane paths” with your favorite problem. If the example comes before “scary” words, I believe the end result will be much better. If things go well, the ideal reaction by other person will be: “That’s so cool! What kind of training do you need to do that?” From that point on, you proceed to convince them that math is cool.

Secondly, the amusing nature of the answers above notwithstanding, this experiment got me thinking about how to make OR more visible and accessible to the general audience. That’s one of the goals of the INFORMS Public Information Committee (PIC), of which I’ve recently become a member. We already have some ideas and initiatives lined up, but I’m open to your comments and suggestions. Feel free to send me your thoughts by e-mail or via the comments section below. By the way, if you feel like doing this experiment with your own friends, feel free to send me their answers and I’ll add them to the bunch.

5 Comments

Filed under INFORMS Public Information Committee, People, Promoting OR

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

There and Back Again: A Thank You Note

There were sub-freezing temperatures, there were snow flurries, there was a hail storm, and there was a tornado watch. No, I’m not claiming that my visit to Pittsburgh last week was as full of adventures as Bilbo Baggins’s journey, but it was very nice indeed.

I had the great pleasure of being invited by John Hooker and Willem-Jan van Hoeve to give a talk at the Operations Research seminar at the Tepper School of Business. Since John, André Ciré, and I are working together on some interesting things, I took the opportunity to spend the entire week (Mon-Fri) at CMU; and what a joy it was.

The Tepper School was kind enough to have a limo service pick me up from, and take me back to, the airport. I guess this is how the top business schools roll. It’s a great way to make a speaker feel welcome. Besides, my driver turned out to be an extremely friendly and easy-to-talk-to fellow. Thanks to him (and his knowledge of off-the-beaten-path roads), I managed to catch my return flight. Otherwise, a cab driver would have sat through miles of Friday rush hour, and I’d certainly have missed the flight.

I walked to campus every day and actually enjoyed the few minutes of cold weather (wow! I can’t believe I just said that!). Stopping at the Kiva Han to grab an almond biscotto and a small coffee, right across the street from Starbucks, was a daily treat. Walking around campus brought back great memories from my PhD-student days. It’s nice to see all the improvements, and all the good things that remain good. Upon leaving Miami, I had the goal of having Indian food for 10 out of my 10 meals (excluding breakfast). Although I managed to do it only 4 times, I’m pretty happy with my gastronomic adventures in Pittsburgh. The delicious semolina gnocchi served at Eleven is definitely praiseworthy.

Work-wise, it was a very productive week. We had interesting ideas and conversations. I’m very grateful to all of those who took time off their busy schedules to meet with me, be it to catch up on life, talk about research (including some excellent feedback on my talk), or both. Thank you (in no particular order) to Alan Scheller-Wolf, Javier Peña, Michael Trick, Egon Balas, Sridhar Tayur, Masha Shunko, Valerie Tardif, Lawrence Rapp, and of course John and Willem. Many thanks also go to André, David, and all the other PhD students who joined me for lunch on Friday. I really enjoyed meeting all of you and learning a bit about your current projects.

I noticed that John got rid of his chalk board and painted two of his office walls with some kind of glossy white-board paint. It’s pretty cool because it allows you to literally write on your wall and erase everything with a regular white-board eraser. Now I want to do the same in my office! (My white board is pretty small.) But I’m not sure if they’ll let me. Gotta check on that!

Overall, it was an awesome week and I hope I can do this again some time.

1 Comment

Filed under People, Research, Travel

The Joy of Baking (Optimally)

‘Tis the season of baking all kinds of things: cookies, cakes, breads, brownies, pies, and my favorite Brazilian dessert “pudim de leite moça“, which is depicted below. Click here for the step-by-step recipe.

Many OR bloggers, such as Laura McLay and Anna Nagurney, actually enjoy baking, and they both have written posts on the subject (e.g. here and here). I happen to include myself in this group and, yes, I made the pudim shown above (using  my mom’s recipe).

My goal today is to approach the art of baking from an optimization point of view. Let’s say you have a long list of items to bake. Perhaps you’re hosting a mega party at your house, or you’re helping your local church or favorite charity with their holiday cooking. You have an oven that can only fit so much at a time (think of area, or volume). Each item to be baked occupies some space in the oven and needs to bake for a specific amount of time. In what order should you bake your items so that you finish as soon as possible? (Side note: it may not be obvious at first sight, but this is the same problem faced by a container port that needs to decide the order in which to unload cargo ships.)

In the OR world, this is a job scheduling problem with a cumulative machine. The jobs are the tasks to be performed (items to bake), the machine (or resource) is the oven. We say the oven is cumulative, as opposed to disjunctive, because it can deal with (bake) multiple items at a time. The unknowns in this optimization problem are the start times of each job (when to begin baking each item). The objective is to minimize the makespan, which is defined as the finish time of the last job (the time at which it’s OK to turn off the oven). Finally, this is a non-preemptive problem because, typically, once you start baking something, it stays in the oven until it’s done.

This problem occurs so often in practice that the Constraint Programming (CP) community created a global constraint to represent it. It’s called the cumulative constraint (what a surprise!). Here’s a reference. For example, let’s say that we have a 10-cubic-foot (cf) oven and we need to bake five items. The baking times (in minutes) are 20, 25, 40, 30, and 30. The space requirements in cf are, respectively, 6, 4, 5, 6, 4. If the time at which we begin baking item i is denoted by the variable s_i, we can write the following in a CP model:

\mathrm{cumulative}([s_1,s_2,s_3,s_4,s_5],[20,25,40,30,30],[6,4,5,6,4],10)

The above constraint makes sure that the start times s_i are such that the capacity of the oven is never exceeded. To minimize the makespan, we have to minimize the maximum among s_1+6, s_2+4, s_3+5, s_4+6, and s_5+4.

It’s easy to incorporate some real-life details into this model. For example:

  • Not every item will be ready to go into the oven at time zero. After all, you’re making them as you go. To take care of this, add a ready-time r_i (i.e. a lower bound) to the appropriate variable: r_i \leq s_i.
  • If a given item does not occupy the entire oven, but you still prefer to bake it alone, just artificially increase its space requirement c_i to be equal to the oven’s capacity C.
  • If you’re baking both savory and sweet things, you probably don’t want to mix them up in the oven. In that case, simply solve the problem twice.
  • If, for some reason, item i must be finished before item j starts baking (e.g. they need different temperatures), just include the constraint s_i + p_i \leq s_j, where p_i is the baking time of item i.

We could, of course, have approached this problem from an Integer Programming point of view. In that case, we’d have binary variables x_{it} that are equal to 1 if you start baking item i at time t, and equal to zero otherwise. For more details on this formulation, including model files and some pretty tough instances, take a look at the CuSPLIB web page.

In the spirit of holiday baking, I will close with some pictures of past baking jobs ran on my house’s machine (a.k.a. oven). Enjoy! :-)

Key Lime Pie

Carrot Oatmeal Cookies (recipe here)

Sparkling Ginger Chip Cookies (recipe here)

Irish Soda Bread

Six-Seed Soda Bread (recipe here)


11 Comments

Filed under Applications, Constraint Programming, CuSPLIB, Food, Holidays, INFORMS Monthly Blog Challenge, Integer Programming, Modeling, People

Awaken Your Creativity

I recently returned from a trip to Brazil (which was followed by a trip to the CORS-INFORMS meeting in Toronto). It was great to spend those 2 weeks at UNICAMP. But why? Could it be because…

(a) I was sharing a room with graduate students and I was motivated by rubbing elbows with hard-working people.

(b) I spent two weeks thinking about a single problem.

(c) I felt at ease wearing shorts, a T-shirt and a hoodie to go to work.

(d) Seeing old friends and being in my undergraduate department brought me memories of the “good old times”.

(e) All of the above.

This whole experience made me think of a related topic. Everyone has their productivity trigger. Some little thing that you do that improves your performance, or some place to which you go that awakens the genius inside you. When I was an undergrad student, I remember spending long hours on my way to and from school (long walk + bus ride) thinking about homework problems. Often, my best ideas would come to me during the commute. Later in life, I gathered more substantial evidence that good ideas come to me when I think about a problem as I walk (increased blood flow to the brain?). I should do that more often.

I wonder if anyone out there has a quirk of this sort. What is it that you do that fuels your creative mind? I’m willing to try new methods!

Leave a comment

Filed under People, Research

Doing OR in Brazil

unicampDuring the first two weeks of May, I’ll be visiting the Institute of Computing (IC) at the University of Campinas (UNICAMP) in Brazil. That’s where I got my BS and MS degrees before coming to the US. I’ll be working on some fun integer programming stuff with my former Master’s advisor Cid de Souza. (Cid spent a year visiting the Tepper School while I was doing my PhD there.)

Despite being a CS department, IC hosts some of the OR people at UNICAMP (the others are spread around in the Math and EE departments). I’m looking forward to working with Cid again, visiting the city of Campinas and seeing some old friends. I’m wondering if I should stop by to see my mother, who lives 2 miles away from campus and whom I haven’t seen in almost 2 years…hmm…such a dilemma… :-)

Leave a comment

Filed under People, Travel