LinkedIn and Operations Research

Don Kleinmuntz of Strata Decision Technology and USC has made a concerted effort to get people in operations research to join LinkedIn. Since Don was a founding co-editor of Decision Analysis and has been Treasurer for INFORMS among many other jobs, he has an extensive contact list, and a number of us have joined. I was a latecomer, just joining today. Don so far has found it interesting, but he is holding back a decision on its importance.

I was surprised how many people were on it. There are dozens of “Trick”s alone, which is unusual. It definitely has cornered the market on 30-something IT people. But a search on “operations research” tagged 177 people, so it seems there are some of our type there (or just Don’s buddies!).

If you are on it, send me (Mike Trick) an invite and we can get our our little social network going.

Famous OR Ph.D.s and authors?

I see that Brian May, guitarist for dinosaur rock group Queen (“Bohemian Rhapsody”, “We are the Champions”, etc.) is finishing off his doctoral dissertation in astrophysics. Nice to have something if that rock ‘n roll thing doesn’t work out.

At the recent “Georgefest” celebration of George Nemhauser’s 70th birthday, dinner conversation (for Ralph Gomory, Tom Magnanti, and me) came to “famous operations research Ph.D.s”. Of course, the interest was not those famous for OR, but famous for something else. Here is what we came up with, augmented with a bit of web search after dinner (either with a Ph.D. or with a well known OR paper):

Gates and Lamarr aren’t really OR, but they are close. There are a number of famous economists with OR backgrounds (for instance, my friend Finn Kydland, 2004 Nobel laureate is really an OR person in the guise of an economist — trust me, Finn, that is is compliment!) but economics is pretty close to OR at times. So who else has an OR PhD or a paper in the OR literature but is better known outside of our field?

OR in Comics

I sometimes fantasize about writing the Great American Novel (New Zealand version).  In such a novel, naturally the hero would use operations research to achieve success and insight.  But when I think about such a novel, my imagination fails me:  how can I possibly make OR interesting in the context of fiction?

She:  Oh Biff, How can we ever be together?

Biff: Well, if I just solve this Traveling Salesman Problem using Concorde, I will be there as quickly as I can.

She: My hero!

Ummm…. no.  But the comic xkcd periodically has an OR theme, like solving knapsack problems.  You know you are a nerd when you solve the instance given by the comic (hint:  they better like fruit in one solution, but the solution is not unique).

Getting dumber?

Stephen Baker at Business Week points to a post by Jeff Jonas on how companies are generating so much data so quickly that companies can’t make sense of it, leading to “enterprise-amnesia“.  Both use this as a call for faster, smarter algorithms.  Now far be it for me to be negative about such a cry (I like algorithms!) but I think they are missing an important step in the process:  the modeling step.  Modeling is formulating the objectives, constraints, and decisions in order for the algorithms to go to work.   We’ve had lots of algorithms hanging around for decades that would address business issues, if only people would create appropriate models to use them.  Not every problem needs a fancy new algorithm!

Jonas’ blog has a number of interesting posts on things like persistent analytics.  This is all from a heavily information technology perspective, but OR should have a role to play in the issues he brings up.

Conference reviews, in perspective

I am just back from Prague: after another 36 hour travel marathon, I think it will take a day or so for my brain to catch up with me!

While I was gone, Scott Aaronson, a graduating doctoral student in quantum computing, had a brilliant article on computer science conference reviewing. From the 1936 Foundations of Computer Science (FOCS) review process:

Dear Mr. Turing,

We regret to inform you that your submission
“On Computable Numbers, With an Application to the Entscheidungsproblem”
was not accepted to appear in FOCS 1936. The Program Committee received a record 4 submissions this year, many of them of high quality, and scheduling constraints unfortunately made it impossible to accept all of them.

The reviews would be a great satire of computer science reviews except they are far too close to the truth:

—————————————- review 1 —————————————-

seems like a trivial modification of godel’s result from STOC’31

—————————————- review 2 —————————————-

The author shows that Hilbert’s Entscheidungsproblem (given a mathematical statement, decide whether it admits a formal proof) is unsolvable by any finite means. While this seems like an important result, I have several concerns/criticisms:

1. The author defines a new “Turing machine” model for the specific purpose of proving his result. This model was not defined in any previous papers; thus, the motivation is unclear.

See Scott’s post for the rest of this and for the other reviews. Many OR conferences are not reviewed (IFORS, EURO, and IFORS conferences accept practically anything submitted on time), but there are some that I am involved with (like CP, CPAIOR, MISTA, and PATAT) that have a review process, and it is clear that the review processes are very hit-and-miss.

With the exception of Scott’s ill-tempered diatribe against babies at conferences (perhaps as forty-something father of three-year-old, I am a little more sympathetic to the pressures of combining parenthood and academia), the entries in Scott’s blog are something I look forward to tremendously: he is opinionated, intelligent, amusing, and self-deprecating by turns, and generally teaches me something when I read him. He is about to join the faculty at MIT: lucky MIT!

IFORS Distinguished Lecturer

I am at the closing session of EURO. This year’s conference was huge with more than 2000 participants. I did attend a good amount of the conference, though Prague has its own attractions.

EURO (along with INFORMS, ALIO, and APORS) have a plenary given by the IFORS Distinguished Lecturer (I chair the committee that recommends the selection to the President of IFORS). This conference’s IDL is Bob Bixby, from Rice University and ILOG. Elise del Rosario introduced Bob, and here are some quotes from her introduction:

The IFORS Distinguished Lecturer for this conference is
Dr. Robert Bixby, an outstanding researcher, innovator, and business
leader. Dr. Bixby received his Ph.D. in the early 1970s from Cornell
University, and looked like he would have a long and distinguished
career in research on combinatorial structures. A sharp turn in the
1980s led him to develop CPLEX, an outstanding large-scale linear
program optimizer. CPLEX led to CPLEX Optimization, Inc, marketing
algorithms for linear and mixed-integer programming. CPLEX was sold
to ILOG in 1997, a company in which Dr. Bixby has served a number of
roles and where he is currently Chief Science Officer.

Dr. Bixby has combined his business success with continued research
success. He, along with his colleagues David Applegate, Vasek
Chvatal, and Bill Cook have just published a book entitled “The
Traveling Salesman Problem: A computational study” that sum up their
20 years of work on solving large scale traveling salesman problems,
culminating the solution of TSPs with tens of thousands of cities.

Dr. Bixby has held a number of leadership roles in our field,
including the presidency of the Mathematical Programming Society, and
has received a number of awards for this work, including the
Beale-Orchard-Hays Prize for excellence in computational mathematical
programming.

The title of his presentation was “From Planning to Operations: the Devil’s in the Details”.  Unfortunately, I had to run out for a plane (for my 42 hour return to New Zealand) so I only got to see the first part, where he reviewed progress in linear programming and integer programming.  A few striking points:

  1. The speed improvement in linear programming from 1996-2004 is a factor of about 5.3 million (3600 due to algorithms and 1300 due to computing).
  2. Not much improvement in linear programming the last few years:  only computer speed improvements.
  3. (Mixed) integer programming is about 13 times fast over the same period.
  4. The next version of CPLEX provides another decrease in time required (by a factor of .6)
  5. The next version of CPLEX is much better at finding feasible solutions to MIP (a test set of about 1300 instances) went from 250 with no solution found in 100 seconds in CPLEX 10 to about 120 in the next version.

The main point of the rest of the talk is that MIP and other optimization models are going to be used increasingly for day-to-day decisions (not as an aid to decision making, but making the decisions directly) and that puts lots of pressure on our models and data.

EURO Gold Medal winner

The EURO conference in Prague has begun. I really like Prague: it is a beautiful city with great bars, restaurants, museums, and even an OK english-language bookstore or two.

The first order of business here is the opening session (somewhat after the truly first, 8AM technical talks). Awarded at the opening session is the EURO Gold Medal, bestowed as follows:

The EURO Gold Medal is the highest distinction within OR in Europe. It is conferred on a prominent person or institution, for an outstanding contribution to the Operational Research science. The award is officially bestowed in conjunction with a EURO Conference, if there is a suitable candidate.

One advantage of having a conference at a university (along with such disadvantages as funny room layout, confusing directions and an air of “this isn’t what we normally do”: I will say the organizers have done a great job in making things as easy as possible with transit passes, lots of student helpers and so on) is available wireless. So I am in the auditorium, ready to announce the EURO Gold Medal first on the blogosphere.

And the laureate is Aharon Ben-Tal of the Technion, Israel. He works in continuous optimization, so I am not particularly well versed in his work. This is from his web page:

Prof. Ben-Tal’s research work is mainly in the area of nonlinear optimization. His theoretical work is concerned with extremum principles for problems in a general setting, with regard to the underlying decision space, and the underlying smoothness of the functionals. He was among the first to develop a comprehensive theory of second-order optimality conditions for nondifferential problems.

Prof. Ben-Tal is also involved in research in stochastic mathematical programming. He introduced the concept of entropic-penalty for problems with randomness in the constraints, and developed a duality theory which established a link between stochastic programming and the Expected Utility principle in economics. Recently he developed, together with Prof. A. Nemirovski, the Robust Optimization methodology. The focus of Prof. Ben-Tal’s work in recent years is in computational methods for solving large-scale continuous optimization problems. The algorithms he develops are used in designing optimally complex engineering structures, water distribution networks, and techniques for medical image reconstruction. The above projects are carried out in the MINERVA Optimization Center, a 2 million DM endowed research center.

Prof. Ben-Tal was a member of the International Council of the Mathematical Programming Society. He served as Area Editor of the journal Mathematics of Operations Research, and is currently a member of the Editorial Board of the journals Convex Analysis and SIAM Optimization. He received Awards of Excellence from the Technion both for research and for teaching.

The work with the most impact is the work he did with Nemirovski in creating the area of robust optimization.

On my way to Prague

I’m in the Hong Kong airport on the way from Auckland to Prague. I have about 22 more hours to go before I arrive at my hotel. It is great spending a year in New Zealand, but it is definitely a long way from anywhere!

Hong Kong airport is beautiful and incredibly well organized. I compare this to the alternative routing through Los Angeles, and there is absolutely no comparison. LAX is chaotic, rude, and very difficult (in my admittedly limited experience). Here, transferring flights involved no formalities at all: just a quick security check and into the departure areas, absolutely full of shopping, lounges, bars and restaurants.

I am on my way to the EURO conference. It is too bad this conference conflicts with the INFORMS “International” in Puerto Rico. Both are conferences I would like to attend. But the IFORS executive is meeting in Prague, so that is where I am going. I’ll try to provide an update or two along the way.

Coordinating supply chains

I just attended a talk given by Tava Olsen from Washington University in St. Lous. The talk was held at the business school at the University of Auckland (who are building a spectacular new building nearby). Her talk was an overview talk on supply chain coordination. For a non-specialist like myself (albeit one who often attends supply-chain-oriented conferences), it was really useful to get an overview of how research in the area of supply chain coordination works.

Here is Tava’s “Make your own Coordination Paper” recipe for research in this area (as I interpret it):

  1. Find a supply chain and identify the actors
  2. Determine the optimal decentralized actions for the actors
  3. Determine the optimal centralized result (perhaps by pretending all the actors were one)
  4. Find an implementable contract so that the decentralized actions give the centralized result.

The example she gave was a simple two stage supply chain with a retailer ordering from a supplier in a single period, one order environment. The retailer’s problem is a simple newsvendor problem, with the amount ordered limited by the losses due to possible overordering. But if the supply chain was centrailized (think of the retailer and the supplier owned by the same company), then the loss of overordering is less (it is the production cost rather than the higher wholesale cost), so more is ordered. The result is more expected profit in the supply chain. But, crucially, that higher expected profit occurs at the supplier, not the retailer who does the ordering. How can the supply chain be coordinated so that the pair find the higher profits?

There are lots of possible solutions: a fixed payment from the supplier to the retailer for ordering the higher quantity would do, but that is rather inelegant (there are few contracts written of the form: “I’ll pay you $1000 for ordering exactly 621 items”) and requires a huge amount of information on the part of the supplier. “Better” solutions (more implementable, while still coordinating) might involve “buyback” contracts where the supplier agrees to take back unsold inventory at a particular value or quantity flexibility contracts, where the supplier agrees to provide any amount within a range of values.

Tava continued with a very nice example of supply chains like those between automobile manufacturers and suppliers whereby parts absolutely must be provided on time (penalties of thousands of dollars per minute late are common). In such cases, suppliers must expedite parts in the case of possible shortages, which can be a very expensive process. Coordinating across such a supply chain means having the manufacturer make decisions that keep in mind the expediting costs.

I was very happy to get such an overview talk: it put a lot of supply chain research into perspective.

Queue or Queues

I am spending this year visiting the University of Auckland. New Zealand is a wonderful, beautiful country filled with very friendly people (see our personal blog for pictures and stories). It is not, however, a particularly efficient country. Service standards are not quite up to US standards. This is made worse by our living on an island. We love living on Waiheke, but any outing often results in “island efficiency”, which tests our relaxed, island mentality to its fullest. For instance, last night we went to a costume ball (medieval style). Beautiful converted barn, wonderful food, perfect music. And exactly one porta-potty for 200 guests at this four hour affair. Island efficiency.

Of course, operations research is about making things work better. And to an OR person, there is nothing more frustrating than seeing things work inefficiently. Grocery stores really stress me. I will not go to a busy store, since the lines and hassles will eventually give me a stroke. Instead, I shop at the off-off times whenever possible.

Some of this annoyance is completely avoidable, however, using just a bit of OR. In queueing, there are a few basic ideas. Here are a couple that even a two hour introduction to queueing should get to:

  • Assuming variance in either service or arrivals, if the service rate equals the arrival rate, the queue will explode.
  • All else being equal, one line leading to a bunch of servers is better for the customer than a bunch of lines each leading to one server.

So why is it that (almost) every grocery store has individual lines? Grocery stores are some of the most sophisticated users of techniques like data mining and logistics optimization, so they aren’t or-phobic. Why can’t they get this right?

One company does get this right, and that is Whole Foods, which gets a whole lot of things right in its operation (why else would we enthusiastically pay their prices?). The New York Times has an article entitled “A Long Line for a Shorter Wait” (thanks to Brian Borchers for pointing this out to me):

For its first stores here [New York City], Whole Foods, the gourmet supermarket, directs customers to form serpentine single lines that feed into a passel of cash registers. Banks have used a similar system for decades. But supermarkets, fearing a long line will scare off shoppers, have generally favored the one-line-per-register system. By 7 p.m. on a weeknight, the lines at each of the four Whole Foods stores in Manhattan can be 50 deep, but they zip along faster than most lines with 10 shoppers. Because people stand in the same line, waiting for a register to become available, there are no “slow” lines, delayed by a coupon-counting customer or languid cashier.

Now there is the psychological effect to avoid: the lines look long! So Whole Foods added some bells and whistles:

Perhaps the most important role players in the Whole Foods system are the “line managers,” who monitor the flow of people, direct them to a cash register and, when needed, hold up signs saying how long it will take to check out. In another innovation, color-coded digital screens are now replacing those humans.

To give an idea of how effective the single line is, suppose you have a single queue with 20 customers arriving per hour. If the cashier can handle (on average) 22 customers per hour (close to saturation, but probably roughly what “efficient” managers would aim for), then the queue will grow so long that the average wait will be 27 minutes! Five such queues would end up with about 50 people waiting in line on average. If you go over to one line (with 100 arrivals/hour) being served by five cashiers, the average wait goes down to under 5 minutes, and the number of people waiting in line is only 12 on average. Thanks to Armann Ingolfsson for putting together the Queueing Toolpack that makes these calculations easy.

There are a lot of assumptions in this analysis, and you can play around with input and service distributions, reneging, balking, queue hoping, and so on, but the result is robust to any of this: a single line to multiple queues is better than a bunch of single lines (about the only interesting aspect of multiple queues is the ability to have an express line for customers with just a few items). Every OR person knows this, and Whole Foods uses it. Every grocery store should.

I think it goes without saying that on Waiheke island, every line is a bunch of lines each being served (or not) by a single server. Even in banks.