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.

OR Forum Paper on Influenza released

As one of my hats, I am the Area Editor for Operations Research responsible for the OR Forum. This area tries to attract contentious or provocative papers on topics in OR of broad interest. We have just published our second paper in the Area: a work by Dick Larson of MIT on influenza modeling. You can read the paper and join the discussion at the OR Forum.

New Computer Coming

I just ordered a new computer to replace this one. mat.tepper.cmu.edu has done a great job over the last five years, but it is showing its age. The operating system is woefully out of date, causing ever-increasing security problems. Of course, if it gets out of date enough, the machine becomes “secure by obsolescence” as a buddy of mine (who runs HPUX 9 or so, circa 1995) has deemed his “security measures”.

I ended up going a little crazy on the new machine, ordering a dual quad-core system (that is eight cores). It is amazing how these multi-core systems have taken over. It also means something important for us operations research people: parallelism is important. I have often been down on the COIN-OR people for all the bells-and-whistle they put in their code (I just want a branch-and-cut code: I don’t want to dig through all the stuff about “computing on multiple heterogeneous machines” and so on). But much of their code is already set up for multiple machines (and multiple processors on one machine) and that is going to be important. Multicore is of little use if the software doesn’t take advantage of it. And expecting the operating system to automatically parallelize a complicated optimization program is currently a pipedream. As this article points out, for a lot of software, more cores does no good whatsoever. So hurray for the COIN-OR people for thinking ahead on this.

It is interesting to compare the speed of this system with the listing of supercomputers, as given by Top500 Supercomputers. I can’t get a clear reading on the speed of the machine I am about to buy, but it may be in the 40-80 Gflop range (can this be? Correct me if I am wrong). Based on the historical graph, such a machine would have been the fastest supercomputer in 1993 and would have hit the top 500 at late as 2000. Now under US$7000.

Is most published operations research false?

Seed Magazine has an excellent article entitled “Dirty Little Secret” with a subtitle of “Are most published research findings actually false? The case for reform.” (Thanks to the Complex Intelligent Systems blog for pointing to this). The article begins with some amazing statistics:

In a 2005 article in the Journal of the American Medical Association, epidemiologist John Ioannidis showed that among the 45 most highly cited clinical research findings of the past 15 years, 99 percent of molecular research had subsequently been refuted. Epidemiology findings had been contradicted in four-fifths of the cases he looked at, and the usually robust outcomes of clinical trials had a refutation rate of one in four.

Why has this happened?

The culprits appear to be the proverbial suspects: lies, damn lies, and statistics. Jonathan Sterne and George Smith, a statistician and an epidemiologist from the university of Bristol in the UK, point out in a study in British Medical Journal that “the widespread misunderstanding of statistical significance is a fundamental problem” in medical research. What’s more, the scientist’s bias may distort statistics. Pressure to publish can lead to “selective reporting;” the implication is that attention-seeking scientists are exaggerating their results far more often than the occasional, spectacular science fraud would suggest.

Ioannidis’ paper “Why Most Published Research Findings are False” goes into a more in-depth examination of why this happens. This is no surprise to those who understand statistical significance. If 20 groups do similar research, it is pretty likely that at least one group will have a finding “at the 95% significance level” just by blind luck. And if that is the group that gets to publish (since proof of significance is much more interesting than non-proof), then the scientific literature will, by its nature, publish false findings. This is made worse by issues of bias, conflict of interest, and so on.

Ioannidis continues with some corollaries on when it is more likely that published research is false:

Corollary 1: The smaller the studies conducted in a scientific field, the less likely the research findings are to be true.

Corollary 2: The smaller the effect sizes in a scientific field, the less likely the research findings are to be true.

Corollary 3: The greater the number and the lesser the selection of tested relationships in a scientific field, the less likely the research findings are to be true.

Corollary 4: The greater the flexibility in designs, definitions, outcomes, and analytical modes in a scientific field, the less likely the research findings are to be true.

Corollary 5: The greater the financial and other interests and prejudices in a scientific field, the less likely the research findings are to be true.

Corollary 6: The hotter a scientific field (with more scientific teams involved), the less likely the research findings are to be true.

This got me thinking about the situation in operations research. How much of the published operations research literature is false? One key way of avoiding false results is replicability. If a referee (or better, any reader of the paper) can replicate the result, then many of the causes for false results go away. The referee may be wrong sometimes (in a statistical study with a true 95% confidence, the referee will get the “wrong” result 5% of the time), but the number of false publications decreases enormously.

Most major medical trials are not replicable: the cost of large trials is enormous, and the time required is too long. So you can expect false publications.

Much of OR is replicable. For more mathematical work, the purpose of a proof is to allow the reader to replicate the theorem. For most papers, this is straightforward enough that the field can have confidence in the theorems. Of course, sometimes subtle mistakes are made (or not so subtle if the referees did not do their jobs), and false theorems are published. And sometimes the proof of a theorem is so complex (or reliant on computer checking) that the level of replicability decreases. But I think it is safe to say that the majority (perhaps even the vast majority) of theorems in operations research are “true” (they may, of course, be irrelevant or uninteresting or useless, but that is another matter).

For computational work, the situation is less rosy. Some types of claims (“This is a feasible solution with this value to this model”, for example) should be easy to check, but generally are not. This leads to problems and frustrations in the literature. In my own areas of research, there are competing claims of graph coloring with k colors and cliques of size k+1 on the same graph, which is an inconsistency: I am putting together a system to try to clear out those sorts of problems. But other claims are harder to check. A claim that X is the optimal solution for this instance of a hard combinatorial problem is, by its nature, difficult to show. Worse are the claims “this heuristic is the best method for this problem” which get into many of the same issues medical research gets into (with bias being perhaps even more of an issue).

I think this is an issue that deserves much more thought. Very little of the computational work in this field is replicable (contrast this to my review of work of Applegate, Bixby, Cook, and Chvatal on the Traveling Salesman Problem, which I think is much more open than 99.9% of the work in the field), and this leads to the confusion, false paths, and wasted effort. We are much more able to replicate work than many fields, but I do not think we do so. So we have many more false results in our field than we should have.

The Traveling Salesman Problem: A Computational Study

The Traveling Salesman Problem: A Computational Study is a new book by David Applegate, Bob Bixby, Vasek Chvatal, and Bill Cook (published by Princeton University Press) and it is terrific. I was asked by OR Letters to provide a review, which I have done. I won’t spoil the review for the journal, but here is my final paragraph(before editing):

At one level, this book may appear to be about a particular computer code for a particular combinatorial optimization problem, but I believe it is far more. Much of the research we do is incremental, involving a small step on a subproblem of a subproblem of a subproblem. Rarely do we step back and see the big picture. This book is, fundamentally, about the big picture. The authors, in their computer code and in their writings, have taken the best from the extensive literature and shown how we as a field have moved forward. At this point, algorithms, implementation, and computing have advanced sufficiently that almost any instance of practical interest can be solved to optimality with sufficient, but reasonable, computing resources. The incremental improvements add up to a tremendous success. By bringing together the best work from a wide array of researchers, describing it in a book, and implementing it in a code, the authors show how research in computational combinatorial optimization should be done.

I really like the book. And I particularly appreciate the publisher for putting it out at a reasonable price: under $50.

Six Key Ideas of Operations Research?

For most of us, teaching a first course in operations research involves trotting out our old friends linear programming, sensitivity analysis, integer programming, and so on. Twenty years ago, we used linear algebra; today, we concentrate more on modeling. But it is not clear that students get the Big Picture. Like “Modeling is useful” or “Decisions can (sometimes) be made on marginal information” or even “If you add constraints, the best solution gets worse”.

Steven Baker, whose Blogspotting I regularly visit and which often provides material here, has a posting entitled Economics and Braille Keyboards pointing to an interview with the economist Robert Frank. Frank has a new book out based on the idea that there are really only about six key ideas in economics, and if you can get students to think about and apply those six ideas, then you have really had a successful introductory course. The title comes from a student essay on why drive-through banks have braille on the keyboard. If blind people can’t drive, why provide braille? The answer is in cost-benefit analysis: it would cost more to have two types of keyboards, so standardization is better (assuming putting on those dots is not costly in itself). As for benefits, this holds even if the benefit is zero. If the benefit is positive (blind people in cabs, say), then it holds even stronger.

What would be the six key ideas/insights about operations research? I listed a few above. Some others might include “If there is randomness, systems without slack run out of control” and “Nonbinding constraints don’t affect the optimal solution” (these are more insights than key ideas). As a prescriptive science (rather than the descriptive science of most economists), it is not clear that this method of teaching works as well, but it is useful for us to think about what we really want to get across in our classes.

Google’s search algorithm

There is an article in the New York Times on Google’s algorithm for returning pages after a search. It is remarkable how complex it has become. At its base is a concept called Page Rank (named after Larry Page, one of the founders of Google), a very simple concept that every operations research student can understand (Wikipedia has a short outline of it). You can see Page Rank as the ergodic state of a markov chain, or as an eigenvector of a particular matrix (as described by Kurt Bryan and Tanya Leise).  But the system has gone far beyond that:

Mr. Singhal [the subject of the article;  the Google engineer responsible for the rankings] has developed a far more elaborate system for ranking pages, which involves more than 200 types of information, or what Google calls “signals.” PageRank is but one signal. Some signals are on Web pages — like words, links, images and so on. Some are drawn from the history of how pages have changed over time. Some signals are data patterns uncovered in the trillions of searches that Google has handled over the years.

“The data we have is pushing the state of the art,” Mr. Singhal says. “We see all the links going to a page, how the content is changing on the page over time.”

Increasingly, Google is using signals that come from its history of what individual users have searched for in the past, in order to offer results that reflect each person’s interests. For example, a search for “dolphins” will return different results for a user who is a Miami football fan than for a user who is a marine biologist. This works only for users who sign into one of Google’s services, like Gmail.

Lots of operations research projects end up looking like that.  A sharp, clean model at the core, augmented over time with more and more additions to better fit reality.