Operations Research in Summertime Reading

I am just back from attending the PATAT (Practice and Theory of Automated Timetabling) Conference in Belfast, a conference I will write about in the next few days.  During the trip, I was never without my trusty itouch.  I used to travel with a Kindle, but since I started downloading my Kindle books to my itouch, my Kindle sits beside my computer with a forlorn “Your battery is empty” message on it.  While I like the Kindle screen, the itouch works much better for me for two reasons.  First, the itouch is much smaller, so it fits in my pocket.  I have a great fear of being without a book to read, and it is comforting to know that I always have a half-doze on me at all times.  Second, I often read in dark bars, and the backlight of the itouch means I can always read, albeit while looking more nerdy than normal.

On this trip, I had a good opportunity to get through some guilty pleasures:  books that are fun, without being particularly challenging.  I’m not talking Dan Brown territory here, but these are not exactly Proust’s À la recherch du temps perdu.  But I got a surprise in two of the books I read.

The first came from Tongues of Serpents by Naomi Novik.  This is a series that combines Napoleonic era naval combat with dragons (kind of Patrick O’Brian meets Anne MacCaffrey).  The initial books in the series were a revelation.  At book number six, Tongues no longer has the ability to astonish, but I still find the series enjoyable.  Early in the book, the heroes of the book receive a letter from the dragons back in England who have had to find work in order to support their prodigious appetites.  The letter goes:

But we contrived:  Majestatis suggested we should send Lloyd to Dover, to inquire after carting work, and we have worked out than men will pay a great deal just for us to carry things to London, and other Towns,  as we can do it much more quickly than Horses; and I have worked out a very nice Method by which one can calculate the most efficient Way to go among all of them, taking on some goods and leaving off others; only it grows quite tiresome to calculate if one wishes to go to more than five or six places.

It is not clear whether this is the Prize Collecting Traveling Salesman Problem or a Pickup and Delivery Problem, but it is clear that the dragon-author has found a difficulty in solving NP-complete problems.

The second appearance of operations research occurs in the Fuller Memorandum, a comedy/horror/science fiction/spy novel by Charles Stross.  This is not my normal type of reading (I don’t do suspense very well) but this series is fun and creative.  In this scene, the girlfriend of the main character is discussing a research result with a scientist.  The scientist has shown that the world is about to end due to an infestation of “class three abominations” who do all the normal things abominations do:  suck out brains and the like.  The scientist explains:

You must understand previous models all seem to have looked at how possession spreads through a sparse network, like classical epidemiological studies of smallpox transmission, for example.  But that’s flawed:  if you posit an uncontrolled outbreak, the people can see their neighbors, random strangers, being possessed.  And that in turn weakens the …[another paragraph in the same vein]

Wow!  It looks like Stross has been reading Punk Rock Operations Research!  But then we get the killer line, which suggests he really does read Laura McLay’s blog:

I modeled it using linear programing and the results are, well, they speak for themselves.

Sometimes people laugh at me and say “You see operations research everywhere!”.  While that is true, sometimes it is pretty obvious!

Another Operations Research Dean

Sunil Kumar, currently at Stanford, has been named Dean of the University of Chicago Booth School of Business.  Sunil’s research has been in manufacturing, stochastic control, queueing networks, and related areas, making him clearly an operations research person (and of course he is a member of INFORMS).  He is an area editor of Operations Research, a position I suspect he will be giving up shortly.

It is amazing how often the field of operations research leads to academic administration.  Congrats Sunil!

A Kiwi on the Move

I spent 2007 visiting the University of Auckland, living on the wonderful (and strange) island of Waiheke, and I have about a thousand pictures online to prove it.  We had a wonderful year, and loved the university, the island, the city, and the country.  So it is with some jealousy that I note that Tava Olsen, formerly of Washington University, St. Louis, has taken up a position at the University of Auckland as the Ports of Auckland Chair in Logistics and Supply Chain Management.

Tava’s family also lived on Waiheke and we visited with her on the island a couple times during the year we were there.  David Ryan, who has done great work in airline scheduling and branch-and-price, has a place on the island.  Garrett van Ryzin lived on the island during his sabbatical year.  With just under 8,000 people, Waiheke has to have one of the larger “output of operations research per capita” values in the world!

I think to celebrate her new Chair, Tava should invite all of us to Waiheke for a nice glass of wine.  Congratulations, Tava!

Eating Better and Better Routing

For the last year or so, my wife and I have decided to eat better by doing more “real” cooking.  A great help in this has been a magazine “Real Simple“.  Every month, the magazine publishes a series of recipes, each generally requiring only 20-30 minutes of preparation time.  We like these recipes because they use real ingredients:  none of this “Pour a can of cream of celery soup over everything”.  We’ve agreed to cook everything, whether it sounds appealing or not, and of the dozens of recipes we have gone through, essentially all of them were edible, with most very good and a few definite keepers (*).   The authors of the recipes do seem to have a fondness for leeks and fennel, but we have grown used to that.   Alexander, my six year old son, eats the same food of course, and generally approves of what we are cooking.

I was delighted with this month’s issue where they had a short blurb on the website route4me.com.  The description appeals to their readership:

You need to get to the library before closing, but you also have to pick up the dry cleaning, the kids from school (don’t forget that one), and the inevitable snack along the way.  Enter up to 10 addresses on this site and it will calculate the shortest route to get it all done, complete with driving directions.

The Traveling Salesman Problem makes an appearance in our cooking magazine!  Naturally I went over to the site, and checked it out by putting in a few cities (seems a limit of 6 but maybe signing up gets you more): Pittsburgh, Cleveland, Atlanta, Winnipeg, Minot (ND), and Los Angeles.  Clicked “round trip” to get back home and ended up … with a somewhat surprising route:

Hmm… that crossing in Illinois is a little suspicious.  This doesn’t look like the optimal route.  Is it? Maybe it is hard to get from Cleveland to Winnipeg due to the lakes?  Perhaps here was an example were the underlying road network really has a strong effect on the optimal tour.

I checked things out, and compared this route to the route going from Pittsburgh-Cleveland-Winnipeg-Minot-LA-Atlanta-Pittsburgh.  Turns out the route from route4me is about 10 hours (driving) longer than the crossing-free route.  What kind of optimization is this?

It took a bit more playing around before I figured out what route4me was doing.  Their definition of a “round trip” is the minimum path visiting all the cities from the starting point, followed by going from the final city back to the starting point.    The best path is Pittsburgh-Cleveland-Atlanta-Winnipeg-Minot-LA;  they then just add in the LA-Pittsburgh leg.  Kind of a funny definition, but I am sure they document it someplace.

Overall, I think I will stick with Real Simple for telling me how best to prepare kale, and leave the traveling salesman information to other sources.

[Thanks to Ilona for pointing out the blurb in the magazine.]

(*)  Our favorite recipe so far has been “Scallops with Sweet Cucumber and Mango Salsa”.  Call it the official recipe of Michael Trick’s Operations Research Blog!

Serves 4 Hands-On Time: 25m Total Time: 25m

Ingredients

  • 1 cup long-grain white rice (such as jasmine)
  • 2 mangoes, cut into 1/2-inch pieces
  • 2 Kirby cucumbers or 1 regular cucumber, peeled and cut into 1/2-inch pieces
  • 1 tablespoon grated ginger
  • 2 teaspoons fresh lime juice
  • 2 tablespoons extra-virgin olive oil
  • 1/2 cup fresh cilantro, chopped
  • kosher salt and pepper
  • 1 1/2 pounds large sea scallops

Directions

  1. Cook the rice according to the package directions.
  2. Meanwhile, in a medium bowl, combine the mangoes, cucumbers, ginger, lime juice, 1 tablespoon of the oil, the cilantro, 1/2 teaspoon salt, and 1/8 teaspoon pepper; set aside.
  3. Rinse the scallops and pat them dry with paper towels. Season with 1/4 teaspoon salt and 1/8 teaspoon pepper. Heat the remaining oil in a large skillet over medium-high heat. Add the scallops and cook until golden brown and the same color throughout, about 2 minutes per side. Divide among individual plates and serve atop the rice with the salsa.

Open source replacement for Solver in Excel

Andrew Mason, who I got to know very well during my year in Auckland, has put together an open source Excel add-in that extends Excel’s built-in Solver (a product from Frontline Systems) and replaces the underlying optimization engine with the optimization code CBC from COIN-OR.  OpenSolver allows the solving of models without limits to the number of variables or constraints.  Andrew has also provided some enhancements including a model visualizer and the capability for fast reoptimization.

OpenSolver works with linear and (mixed-)integer programming models, but not with nonlinear models.  So keep those @IF and @POWER functions away from it!

This add-in a great illustration of both the strengths and weaknesses of open source.  On the plus side, all the work that people put into CBC can now find a much wider audience through the efforts of someone else.  No coordination was needed:  people like Andrew are able to use their own creativity and drive to put together something useful.

However, it is important to note that there are different open source licenses, and that Andrew has licensed this under GPL, while most of COIN-OR is licensed under CPL/EPL.  For most, this licensing difference is not of importance, but any work that is derivative of Andrew’s work can only be distributed under GPL.  Trying to figure out what is a derivative work is beyond me, but is important to those who would like to further develop systems based on Andrew’s work.  I note this fully respecting Andrew’s right to pick whatever license works best for him!

For me, this will be great to point to in class:  MBA student’s love Solver, but get frustrated with size limits.  I can now point to an easy to use add-in that removes those limits without requiring any changes in models.

Watch the Edelmans!

I have said numerous times that the Edelman Prize presentations and papers are my favorite part of the operations research world.   It is fantastic to see and read about such great work in operations research.  The presentations often feature a Cxx of the firm.  Watching business leaders explain the importance of operations research never gets old to me.  And some of them actually read the script with feeling and (seeming) understanding (others look like they are reading under duress, with uzi’s pointed at them from just offscreen).

The Edelman’s have all been recorded through the years, and INFORMS (the professional organization that runs the Prize)  has experimented with how best to distribute the results.  We have gone from video tapes to DVDs to YouTube snippits.  There was always an issue of monetizing the presentations.  If this is our field’s best work, surely we can make money on it!  But making money limits distribution.

At least for now, INFORMS seems to have given up the money aspect, and even any membership aspect, and offers the most recent Edelman presentations for the low, low cost of a site registration.  Once you register, you can see all sorts of neat videos.  In addition to the Edelman finalists, there are Richard O’Neill’s talk on energy markets  (he is the chief economic adviser to the Federal Energy Regulatory Commission), Chris Tang’s talk on supply chain risk management, and the Wagner Prize finalists.  For all, there is a proprietary presentation which shows both the powerpoint slides and the speaker.

I do have one big complaint about this setup, however.  The system, as currently designed, appears to fall into a trap that operations research often sets for itself.  If you know you want what the system offers, it is easy to work with:  registration is fast and relatively non-intrusive.  But the listing of the videos is “behind the wall”, so someone interested in, say, energy markets, has no idea that this site would have a great talk on the subject.   Why aren’t all the talk titles and abstracts freely available?  Better yet, why bother with registration?  Based on the privacy agreement, it does not appear that INFORMS can even market to those who register.  Why hide anything?

For those of us in the know, this is a tremendous resource!  For those of you who have not yet discovered the beauty, fun, interest and (particularly) importance of operations research, I strongly urge you to go to the site and explore.  It might change your life.

Become Rich and Famous at INFORMS Online

Well, not rich in the financial sense, but rich in social capital and other rewards.

INFORMS is looking for the next editor of INFORMS Online.  I was the founding editor of IOL, with a term from 1995-2000, and it was one of the formative experiences of my life.  I learned a lot about operations research, INFORMS, organizing things, inspiring people, and myself during that time.  In that time, the IOL team took INFORMS into the internet age.  A person I admire greatly said that the best part of the merger of ORSA and TIMS (the predecessors of INFORMS) was that something like INFORMS Online could happen and I am very proud to have been part of that.

Back then, in the dark ages, the job of Editor was very hands-on.  The editorial team and I hand-coded much of the visible portions of IOL.  We installed database programs and wrote codes that handled the membership directory and the conference database.  In short, we did a lot of grunt work.  You can still see some remnants of that period:  if you go to IOL and check the tab on your browser, you will see a little square icon saying “OR/MS” in white and blue (you can see it on the graphic next to this post).  I hand-created that, picking out the blocks using a freeware icon editor in 1997 (when Internet Explorer 4 was released, supporting such icons).  It is still there:  my little bit of fame on the internet.

The job of editor of IOL is a lot different now.  Between INFORMS’s wonderful staff and IOL’s content management system, there is little actual coding done by the editor.  Instead, the editor and his or her team gets to think of all the ways that IOL could be used to advance INFORMS and the field of operations research.  How can we create real communities?  What services do subdivisions need that IOL can provide?  How can we better advertise all the wonderful things our field does?

Being Editor of IOL lets you meet with a wide variety of people in operations research (and become a little famous along the way).  It does take work:  we estimate it takes around 4 hours per week, but the effort depends on the goals and aspirations of the Editor.

If you are interested, nominations are due by the end of August.  And self-nominations are perfectly fine, and even expected.

ALIO/INFORMS Talk on Benders

My talk at the ALIO/INFORMS Conference in Buenos Aires was on combinatorial benders’ approaches to hard problems.  I really think this approach is an important one that is not yet utilized enough.  You can get the talk here (apologies for the powerpoint:  I wanted to convert to beamer but was too latex-stupid to get things done quickly enough).  A paper on benders for sports scheduling is here, while one for transportation planning will be added when I get back.

The talk went well, I thought:  people seemed engaged, and I had fun giving the talk.  No wireless mike, so I opted to go without a microphone, so I hope those in the back could hear me.  Generally I prefer if people use microphones, but this was not the first time I did not take my own advice.

Off to Buenos Aires

I am off on Friday to Buenos Aires (via Atlanta)  for the ALIO/INFORMS conference.  I am giving a tutorial Monday on combinatorial Benders’ approaches and am tearing my hair out trying to get a structure to the talk.

If anyone else is going down (particularly a fellow blogger), drop me a note:  we can do a “Bloggers (and Readers) Beer” together.

I’ll try to blog some of the interesting activities at the conference:  INFORMS doesn’t seem to be organizing things the way they do at the annual meeting so the blogging will be a bit more informally done.

Correction… Operations Research is Not Taking Over the World, Yet

After trumpeting the glorious news that Japan had an operations research-educated Prime Minister, I suppose I should note that Prime Minister Yukio Hatoyama is resigning after eight months of rule.  With operations research in his arsenal, perhaps he simply fixed everything in those eight months.  But that does not appear to be the case (according to CNN):

In his first speech as Japan’s 92nd prime minister, Hatoyama made promises that he would conduct a clean and transparent government, launching a task force to monitor government spending.

But soon afterwards, allegations of illegal campaign financing tarnished his administration’s image. Some of his cabinet members were investigated for corruption.

His approval rating took further hits over his failed promise to move a major U.S. Marine base off Okinawa to ease the burden of the island, which hosts the majority of the United States military presence in Japan. Earlier this month, calling his decision “heartbreaking,” he announced that the base would remain on Okinawa, although relocated to a different part of the island.

C’mon Yukio, it is a facility location problem!  We’ve been solving those for decades!

Let’s hope the less-than-stellar past eight months don’t tarnish all of us in operations research who aspire to higher office.

[Thanks to my former doctoral student Ben Peterson who called me out on this issue.]