# 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.

Filed under People

## 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

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

Six-Seed Soda Bread (recipe here)

## 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!