The Edelmans are here!

The January-February 2009 issue of Interfaces is now online, which means the papers from the 2008 Edelmans have now arrived.  My only disappointment is that my “OR Techniques for Consultants” course was moved up 7 weeks, so this year’s students had to make due with last year’s papers.

The papers include:

ACM Fellows and Operations Research

The ACM (the Association for Computing Machinery) has announced 44 new Fellows.  A number of them are well-known in the operations research community (some are just plain well-known:  can it be that Stephen Cook of NP-completeness fame was not a Fellow before now?).  These include:

  • Tuomas Sandholm, Carnegie Mellon.  Tuomas does an amazing number of things very well.  He is an ideal faculty member raising money, training students, and so on.  He also runs a company:  CombineNet.  Much, but not all, of his work is in combinatorial auctions, and he has really revolutionized that area.  He also windsurfs.  He is someone I am jealous of.
  • Michel Goemans, MIT.  Has done amazing work in approximation algorithms.  I am not a huge fan of approximation algorithms:  I like solving real problems and it is not clear that a factor of 2 approximation is of much use, much less a log x/log log x approximation.  And while many approximation papers give lip-service to the applications of the models they work with, very rarely are approximation algorithms implemented.  That said, Michel does what I admire more than anything:  he finds truly new and creative approaches to problems.  When Michel finds a new approach (which he seems to do every two years or so), it is worth learning about because his approaches generally lead to a very rich a productive research vein.  I am jealous of Michel too.
  • Sanjeev Arora, Princeton.  Unlike Tuomas and Michel, I do not know Sanjeev personally, so I cannot be jealous of him.  But I certainly know his work on randomized approaches to hard problems.

So congrats to all the new Fellows!

Doing Good with Good OR

INFORMS is sponsoring a student project competition for projects having significant societal impact.  I know there is a lot of great work going on using OR to do things like route Meals-on-Wheels trucks, site ambulances, improve blood collection practices and so on.  Let’s see what is out there!  Application deadline for the competition has been extended to December 15, so get those letters in!

Balas Honorary Doctorate

My colleague Egon Balas just received an honorary doctorate from the University of Liege. Yves Crama, Director General of the School of Management, introduced Egon with a wonderful and heartfelt introduction. Some excerpts:

For more than 40 years, Egon Balas has been one of the pioneers of all major theoretical developments and of the most innovative algorithmic approaches in optimization. His name is linked to numerous approaches with esoteric names – disjunctive programming, polyhedral methods, « lift-and-project », « shifting bottleneck heuristic », … I omit many of them, since his research has been the topic of over 200 scientific publications.

Beyond his theoretical and methodological contributions of highest importance, Egon Balas has broadly contributed to demonstrating the usefulness of mathematical models in the practice of management, by carrying out numerous studies relating to the optimization of production in the steel industry, in transportation, in telecommunications, in the oil industry or in finance. The algorithmic developments that he has initiated, or with which he was closely associated, are nowadays integrated in many corporate software packages which enable managers to optimize the efficiency of their production processes, most frequently without a full understanding of the complex algorithms upon which they rely.

Before starting this brilliant academic career, however, Egon Balas had already spent, and turned the page of several fascinating lives. He wrote about them in a captivating autobiography entitled: “Will to Freedom: A Perilous Journey Through Fascism and Communism”. I strongly recommend reading this book.

Born in Romania from a Hungarian family, Egon Balas has joined the ranks of the Hungarian communist party and of the anti-nazi resistance during World War II. His autobiography retraces his arrest by the nazis, his imprisonment, the sessions of torture he went through, and his escape shortly before the arrival of the Russian troops.

After the War, Egon Balas rapidly ascended through the ranks of the Romanian ministeries, and held a diplomatic position in London before being arrested once again, this time by the Romanian communist authorities inspired by the bad example of the Stalinist purges in USSR. Two years of solitary confinement and of barbaric treatments were not able to break down this personality made of hard steel, who stubbornly refused to cooperate in the staging of a fake trial. Freed after the death of Stalin, but disenchanted by the excesses of the communist regime, Egon Balas started his new life as an economist and self-made mathematician in Bucharest.

This reminds me of my favorite Egon story. He was called to jury duty here in Pittsburgh and was asked, during routine questioning, “Have you ever been convicted of a crime?” “Yes”, he replied. “And what crime was that?” “Treason!”. He got out of jury duty.

Europeans do a nice job of honorary doctorates. Here in the US, honorary doctorates tend to go to executives who give $100 million to a university. In Europe, they go to people truly admired by the university. I mentioned this to Egon, who replied “Yes, but then again, no one gives $100 million to European universities!” I rarely best Egon in conversation.

Netherlands Railway Edelman summary

I just got out of the “reprise” of the winning Edelman prize work by Netherlands Railways, and it was very, very good.

If you have been to the Netherlands, they have a very nice way of handling their trains:  every route repeats every hour.  So if you want to go from Utrecht to Amsterdam, there are trains at 13, 25, 43 and 55 minutes after the hour, every hour.  Of course, the size of the train changes depending on the expected demand.

The Dutch have had the same schedule since 1970, but it was time for a change.  Demand has doubled in that period, and there was little opportunity to increase the infrastructure.  So could a better schedule reduce costs and improve service?  Of course, or it wouldn’t be an Edelman Prize winner!

There were three pieces to the system:  the timetabler, the crew assignment system, and the rolling stock assignment system.  The timetabler was very interesting.  You can formulate the problem as a mixed-integer program, but the cyclic nature of the hourly schedule requires the use of “mod” constraints.  They tried MIP for a while (and even called in the big gun Lex Schrijver to look at it:  I saw a talk by Lex a decade or more ago on work he did with Netherlands Railway on purchasing rail cars that is still one of the nicest applications talks I have ever seen), but eventually went over to constraint programming.  From the talk, it appears they used constraint programming primarily to find a feasible solution, and then did some local improvements, but I will have to wait for the paper to be sure what is being done.

The other problems were solved with specialized integer programming methods.

The best part of the talk was their discussion of the implementation, which is where the models really came through.  The plan was to have an important length of track doubled to coincide with the new schedule.  That doubling didn’t happen, so they had to reschedule the crew essentially at the last minute.

The results have been really impressive.  Crew costs are down 4% and rolling stock usage is down 6%, combining for an annual benefit of $75 million.  As is not uncommon in OR projects, the system is both cheaper and works better.  Punctuality is at an all-time high, and customer satisfaction is similarly improved.  The increase in punctuality allowed them to increase fares by an additional 2%, for further profits of $30 million.  Other than the fare increase, this looks like win-win:  better service, more convenient times, cheaper operating costs.

At the end there was a nice video clip of the Minister of Transport saying how important OR is.

A worthy Edelman winner!

INFORMS Prize 2008

The INFORMS Prize is given to an organization for “effective integration of operations research into organizational decision making”.  It is given to organizations for sustained use of operations research.  The criteria are

  1. Variety of Applications of OR
  2. Competitive Advantage to the Organization
  3. Business Impact
  4. Business  Model for Success
  5. Endorsements (from top-level management)
  6. Overall Quality of the Application

INFORMS just announced at the INFORMS Practice Conference the 2008 winner to be GE Global Research, Risk and Value Management Laboratory, with Intel and MITRE as the honorable mentions.  The CTO of GE gave a very nice speech about the role OR plays at GE.

Edelman Finalists Announced

The finalists for the 2008 Franz Edelman Award for Achievement in Operations Research and the Management Sciences have been announced. The Edelman Awards are a big thing in OR. The prize is given to the best use of operations research in practice. Even getting to be a finalist is a lot of work: this is not just a matter of submitting a paper and seeing how it goes. The finalists have to work even harder. They need to prepare a highly professional presentation, with the best presentations getting the support of a firm’s very top management (one year, the South African defense department was a finalist, and President Mandela provided a letter of support). Each finalists is assigned a coach to help them prepare their presentation (the late Rick Rosenthal was proud of the role he played as a coach, and I think finalists working with him may have had a bit of an advantage). And the projects have to be real, not hypothetical. Without verifiable and significant effect, a project cannot be a finalist, let alone a winner.

INFORMS has jazzed up the competition quite a bit in the last years, with fancy presentations at the Practice Meeting. I think this is great: these projects save, often, hundreds of millions of dollars, or improve many lives. They deserve a celebration.

This year’s finalists are an interesting bunch:

1. Federal Aviation Administration, for a project entitled “Airspace Flow Programs,” which gives the FAA greater ability to control the nation’s skies at times of peak consumer usage and flight congestion.

2. Netherlands Railways, for “The New Dutch Timetable: The O.R. Revolution,” a solution that improved on-time performance and capacity for more than a million daily train passengers.

3. StatoilHydro, one of the world’s largest gas producers, and Gassco, the independent Norwegian network operator, for “Optimizing the Offshore Pipeline System for Natural Gas in the North Sea.”

4. The City of Stockholm, Sweden for “Operations Research (O.R.) Improves Quality and Efficiency in Social Care and Home Help,” a program that has brought improvements to the complex scheduling of more than 4,000 providers who help the sick and the elderly.

5. U.S. Environmental Protection Agency, for “Reducing Security Risks in American Drinking Water Systems.”

6. Xerox, for “LDP Lean Document Production® – Dramatic Productivity Improvements for the Printing Industry,” which has bettered production and reduced costs for print shops and document manufacturers. The total impact to date on Xerox profits from the utilization of the LDP is about $200M. Xerox has filed 48 patents on this methodology and so far 11 have issued.

That’s three international organizations and only one traditional manufacturing finalist. The Swedish finalist in particular represents a strong trend in OR: using OR in the service sector.

I am looking forward to seeing the presentations at the Practice Meeting.

INFORMS and YouTube videos

INFORMS has some videos on YouTube from the recent Edelman Awards. This is great for the field. The three videos are

  1. General OR, and the Edelman Award
  2. The 2007 Award (on more efficient ways to attack prostate cancer)
  3. A detailed video on the 2006 award (Warner Robbins on repairing planes)

So far the videos have been accessed a couple of dozen times each. Pass along the pointers, and let’s get that count up!