Interaction of Computers and People

In a few days, I give a “public lecture” as part of the requirements for my Hood Fellowship that the University of Auckland gave me (I would have visited here anyway – New Zealand is wonderful – but the Fellowship was a very nice addition). Rather than trot out a version of my “sports scheduling” talk, I am giving an overview of OR talk. It is really quite a challenge. These overview talks can be quite a snooze for those in the audience who know OR, so I am thinking hard about the role OR has in the world, and the challenges the field faces. The “Science of Better” initiative of INFORMS has been very helpful in this regard.

One aspect I am exploring is the appropriate role of OR in decision making. While optimizers like me tend to be a bit impatient with this (“The best answer is this! Stop arguing with me and do it!!), the real-world is full of stuff that doesn’t appear in our models. In many (most?) applications, OR is an adjunct to decision making, not a replacement. Slate has an interesting article about this in the context of chess-playing programs that I may try to work into my talk.

Apologies in advance: the next few posts may be me trying to work through my thoughts in preparation for the talk.

Large Storage Research

Gene Cooperman (Northeastern)Gene Cooperman of Northeastern University received an NSF grant in order to put together a system that can store 10-20 TB of data, as reported by Computerworld. This grant is getting some press since one application he talks about is storing configurations of a Rubik’s Cube. From the Computerworld article:

Cooperman, director of the Institute for Complex Scientific Software at Northeastern University in Boston, is studying Rubik’s Cubes as a way of setting up machines to study combinatorial problems in science and operations research. He wants to record as many different states of the Rubik’s Cube as possible, which he says will exceed the 20TB of capacity the $200,000 National Science Foundation grant recently afforded him.

Cooperman said that what he learns about the cube could be applied to operations research problems with business applications, such as determining the most efficient way to move goods to consumers.

“Operations research is about efficiently using resources,” he said. “The Rubik’s Cube is the same kind of mathematical problem.”

The article doesn’t go into detail of why one might be interested in storing such a thing. The reason is, as always in operations research, how one would use such storage. Gene’s annotated bibliography of his research (a very handy thing that we should all be doing), gives a bit better insight:

I was led to issues of groups of transformations, groups of symmetries, and presentations (defining equations for a group). Since Larry Finkelstein at Northeastern University was kind enough to give me an introduction to the field of computational group theory, which was still at a relatively early stage when I entered it, and I found much to do in building up the appropriate computational tools. These tools were sharpened and tried on some large applications. There were some early successes. For example, a one Megabyte data structure was pre-computed by which any state in Rubik’s 2 x 2 x 2 cube (Rubik’s cube with corners only) can be solved, and the shortest sequence of moves can be written out in a few milliseconds. (I found that Rubik’s cube can always be solved in at most 11 moves.)

So by storing configurations of the cube, algorithms can be applied to precompute solution approaches.

These issues of computational group theory have many other applications in operations research. My colleague here at Carnegie Mellon, Francois Margot, uses approaches like this to try to handle symmetries in integer programming formulations. I wonder if I can talk him into getting a 30TB machine?

Poker and Airline Scheduling

There is a nice post on the Math and Poker blog on the importance of identifying key variables and the flexibility that is available for many decisions in a process. The example begins with a standard critical-path type scheduling example, making the point that jobs not on the critical path have some flexibility. This point is extremely well known, of course, but it is interesting to think about what to do with this flexibilty. In poker, the author of the blog (I can’t see who it is), notes that there are a lot of situations where the difference between the best and next best decision is not a lot, but can be used to set up the opponents in particular ways (EV in the following is Expected Value):

The way that most people think about EV in poker is like treating each of these tasks independently. If I bet this hand what happens? Things like folding when the pot is small even if calling is +EV for this hand are ignored even though doing so might set up other players, or that player, to make a big bluff on some other hand.

If you really want to optimize your stratagy and maximize your win, they you just have to look at the game in a global sense. A strategic Expected Value of a collection of actions is what you need to consider, not a tactical Expected Value of one action.

So what does this have to do with airline scheduling? A lot of work is being done right now to combat the fragility of airline schedules. David Ryan of the University of Auckland gave a talk last week at the EURO conference on his work with New Zealand Air (my plans are to visit David for most of next year, so I was particularly interested in his work). In this work, David had a measure of fragility of a schedule (generally due to crews changing planes with a short layover: one late plane could quickly affect many others). David showed that there were near-optimal solutions (based on the main objective of minimizing cost) that had much better properties with regards to fragility. Things got even better if the schedule could be modified slightly.
The problem with both the poker example and crew scheduling is that the objective is much “fuzzier” than the underlying main objective. And that makes it much harder to “optimize”.

Google Scholar and OR

One issue in faculty reviews is trying to determine the effect the research of a faculty member is having. For that, we do things like get outside letters, read papers, and so on. In the past, we also checked things like the Science Citation Index for counts on how often a paper is referenced. Recently, Google Scholar has taken on that role, for better or worse. It is better than SCI in the sense it lists very recent references that may not be in the published literature yet. It also is very wide ranging, catching things SCI doesn’t catch. Of course, it may also catch garbage, but that is the tradeoff. It also undercounts older papers that don’t have as strong an online presence.

One surrogate for “effect” is number of references in Google Scholar. I thought it would be interesting to see the OR work with the most references. Here are a few I found:

  • Dantzig (Linear Programming and Extensions): 1384
  • Garey and Johnson (Computers and Intractibility): 12334 plus other editions
  • Nemhauser and Wolsey (Integer Programming): 2199
  • Rockafellar (Convex Analysis): 4470
  • Schrijver (Theory of Integer and Linear Programming): 1866
  • Papadimitriou and Steiglitz (Combinatorial Optimization): 2364
  • Ahuja, Magnanti, and Orlin (Network Flows): 2037
  • Karmarkar (16th ACM Polynomial Time Linear Programming): 1329
  • Trick (hah!, Cliques, Coloring and Satisfiability): 126

So I have Papadimitriou and Steiglitz (deciding Rockafellar and Garey and Johnson are not “really” OR) as the most referenced book and Karmarkar as the most referenced paper. Anybody beat that?

IBM’s Center for Business Optimization

I am in New York to give a talk to IBM’s Center for Business Optimization. Bill Pulleyblank is heading this activity. Bill has had a really interesting career: he started in academia, and did really fundamental work in combinatorial optimization. He then moved to IBM, starting at Watson Research and moving on to doing things like heading the Blue Gene Project, which created the world’s fastest supercomputer. CBO is a startup with IBM that tries to merge the assets of IBM (software packages, etc.) with the consulting skills of IBM Business Consultants (formerly PriceWaterhouseCooper’s consulting arm).

It is exciting to see a company like IBM take optimization seriously. The projects I have chatted with people about look like “real” optimization and business analytics: data mining and modeling approaches to fraud dectection (both tax fraud and Medicare fraud), supply chain optimization, marketing design, and so on. They have a number of case studies that outline their various projects.

David Simchi-Levi Presentation


David Simchi-Levi is here at CMU today speaking on inventory systems where the decision maker is not risk neutral. David is a professor at MIT and Editor-in-Chief of Operations Research. He also runs his own company, LogicTools. I think he has given up sleep.

It is surprising that there is so little research on risk-averse decision makers in the operations management context. This clearly is a useful integration of economic theory and operations research and also involves the interface between finance and operations in a firm. In David’s work, even marketing comes into play since prices can be set in the model in order to influence demand.

Work like this often spends time in pages of greek letters with subscripts, and this paper is no different (though David is an excellent lecturer, so it was not as mind-numbing as some lectures like this).

With fixed costs for ordering, even models with risk neutral decision makers are hard to solve. Normally, the optimal decisions are set with an (s,S,p) policy: if inventory is under s, order up to S, and set price p. But suppose the inventory level is a bit above s. Should price be set high in order to decrease demand or should the order go up to S, and price be set low. This example shows that the price has a discontinuity, making it hard to get characteristics of the solution.

With risk aversion, things get more complicated. For the case where there is no fixed ordering cost, the optimal policy is a base stock policy, but the base stock level depends on the wealth level of the decision maker. With fixed costs, for exponential utility, the optimal inventory policy is independent of wealth, making things a bit easier (though it is still hard to figure out the exact policy).

One interesting aspect of this that came up in Q&A is the need to combine pricing and inventory decisions. Most companies are not aligned this way: marketing sets price, while operations sets inventory. Even in these complicated models, though, the results generally look like “Operations, do (s,S); Marketing, set price p”. This suggests very tight integration is not needed: coordination is enough.

When you add financial hedging aspects, there is still this decoupling aspect: the financial decisions do not affect the operational decisions.

It would take someone more skilled than I to explain these results to a general audience, but I find it interesting that models that contain all of marketing (price setting), operations (inventory setting) and finance (hedging) are amenable to analytical solution. This seems a very rich research area.

Doing research already done?

The New York Times has a nice article about how research is often rediscovered. The lead begins about operations research:

In 1996, Rakesh Vohra, a professor at Northwestern University, and his colleague Dean Foster published “A Randomized Rule for Selecting Forecasts,” a paper in the journal Operations Research. It illustrated how a random investor could outperform a group of professional stock pickers simply by following a “buy and hold” investment strategy.
Skip to next paragraph
Alain Pilon

It was important research, the authors believed, until they learned that the same discovery had been made at least 16 times since the 1950’s. And no one, Dr. Vohra said, ever realized they were not doing original work.

As a referee, there are certain things in sports scheduling that I get quite often (generally some variation of de Werra’s work on minimum break scheduling) and I recently went a long way on a paper before de Werra pointed out to me that the results were included in a somewhat more obscure publication of his. I wonder if online search will make it easier to find these duplicate results before it makes the literature?

Christmas and OR

It is Christmas time, so lots of people are waiting in line, and talking about it. Naturally, this leads to some OR related articles. Ivars Peterson in his Math Trek column at Science News talks about parking strategies: do you park and walk, or cycle through hoping for a better spot (seems the better is generally the better strategy). And the Birminham News is the latest to talk about Dick Larson’s work on queue behavior.

OR and Suicide Bombs

This past weekend, the NY Times Magazine in its annual Ideas issue reports on Ed Kaplan’s work with Moshe Kress on damage done by suicide bombers. Here is an excerpt:

Even if you manage to detect a suicide bomber, what do you do next? This question was taken up by Edward H. Kaplan, a professor of public health at Yale, in a paper he published in July, written with Moshe Kress of the Naval Postgraduate School in Monterey, Calif. Kaplan and Kress investigated the physics of a belt-bomb blast and reached some unexpected conclusions. It turns out that very few people are killed by the concussive force of a suicide explosion; the deadly weapon is in fact the shrapnel – the ball bearings, nails or pieces of metal that the attacker attaches to the outside of his bomb. The explosions, though, are usually not powerful enough to send these projectiles all the way through a human body, which means that if your view of a suicide bomber is entirely obscured by other people at the moment of detonation, you are much more likely to escape serious injury. Because of the geometry of crowds, Kaplan found, a belt bomb set off in a heavily populated room will actually yield fewer casualties than one set off in a more sparsely populated area; the unlucky few nearest to the bomb will absorb all of its force.

The authors used these calculations to question some assumptions about what authorities should do if they detect a bomber. The International Association of Chiefs of Police issued guidelines this year suggesting that police officers who find a bomber in a crowd should fire shots into the air to cause people near the bomber to scatter or hit the deck. But Kaplan’s calculations demonstrate that in many cases, this would make things worse – as a packed crowd ran away from a bomber or dropped to the ground, the circle of potential victims around him would get wider and thus more populous, and more lives could be lost.

Amazing what a little OR will teach you!

Rothkopf’s Rankings of University Contributions to the Practice Literature

Mike Rothkopf has just published his sixth ranking of universities in publishing in the practice of operations research in the journal Interfaces (subscription required to access full paper). The definition of “practice” is naturally a complicated thing: most OR people (myself included) claim relevance to practice on pretty slim connections. For this ranking, “practice” means publishing either in Interfaces or in the OR Practice area of Operations Research. My own school, Carnegie Mellon, came out on top with 10 such publications (1998-2004). The next part of the rankings are
2. University of Pennsylvania
3 (tie). Georgia Institute of Technology and Naval Postgraduate School
5. Cornell, Stanford, University of Texas at Austin, and University of Virginia

Non-US schools are ranked separately. Top is Erasmus University with 7 papers (same as Cornell, etc. on the US list).