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.
Slashdot discussion on “High Paying Jobs in Math and Science”
Slashdot is having a very active discussion (naturally degenerating into nonsense at times, but generally pretty good) about high paying jobs for those will a college degree in math or science. Operations research gets a good plug or two among the discussants. One response (from “MoneyCityManiac”):
Applied math is a good bet. Operations Research (“OR”), as Wikipedia defines it, is “an interdisciplinary science which uses scientific methods like mathematical modeling, statistics, and algorithms to decision making in complex real-world problems which are concerned with coordination and execution of the operations within an organization.” It’s a mixture of math, stats, CS, and engineering.
There’s OR applications in areas such as health-care, environmental management, forestry management, transportation, and much more. Environmental management, in particular, is something that operations research is going to play a huge role as government and industry focus on reducing greenhouse gas emissions.
And because there’s such a practical role towards it, there’s plenty of support from government and industry, not just in terms of jobs at the end but also scholarships, fellowships, etc. Ask around a math, CS, or engineering department! I’m sure it won’t be hard to find someone who can point you in the right direction.
Operations Research in the New York Times and I am annoyed and depressed
The term “Operations Research” appears in the New York Times today (May 20, 2007) in an article entitled “Reaping Results: Data-Mining Goes Mainstream“. Here is the start:
RODNEY MONROE, the police chief in Richmond, Va., describes himself as a lifelong cop whose expertise is in fighting street crime, not in software. His own Web browsing, he says, mostly involves checking golf scores.
But shortly after he became chief in 2005, a crime analyst who had retired from the force convinced him to try some clever software. The programs cull through information that the department already collects, like “911” and police reports, but add new streams of data — about neighborhood demographics and payday schedules, for example, or about weather, traffic patterns and sports events — to try to predict where crimes might occur.
Later comes the “Operations Research” reference:
The desire to exploit computing and mathematical analytics is by no means new. In the 1960s and ’70s, “operations research” combined computing and math mainly to make factory production work more efficient. And in that period, “decision support” software was intended to help managers more intelligently use information in the big computing file cabinets — databases — that were becoming common in corporations.
That really burns my butt. I hate the idea that operations research is shunted into history and it is the new analytics that is the key. It is all Operations Research!
Otherwise, the article is great. Analytics are a key success path for companies. Here is a quote from Wired on why Yahoo! lost out to Google:
At Yahoo, the marketers rule, and at Google the engineers rule. And for that, Yahoo is finally paying the price.
On the personal side, I also cringed when I saw the following in the New York Times article:
“It’s really starting to become mainstream,” says Mr. Davenport, co-author with Jeanne G. Harris of “Competing on Analytics: The New Science of Winning” (Harvard Business School Press, 2007). The entry barrier, he says, “is no longer technology, but whether you have executives who understand this.”
This was really the theme of my Hood Lecture, and I had the inklings of writing something longish on the subject. I will have to see if this book does a good job on this.
OR, Poker, and Teaching
It is a lovely morning here in New Zealand, and the sun is rising over the bay that my house overlooks. So naturally I am wandering around the web.
Gary Carson’s Math and Poker blog is one that I regularly follow (not the least because he points to this blog). He writes about the role OR plays in understanding poker and about how OR is taught:
Part of the problem that operations research has in getting recognition is the way we teach it — it’s taught as a bunch of algorithms for the most part. Even when it’s taught as a bunch of models to be applied to real problems, the models are taught as members of a tool kit. Seldom do we teach OR as a process of using models to abstract or isolate the elements of a problem that are critical to decision making related to that problem.
…
I think OR education needs to put more of a focus on using the model and less focus on solving the model. I think students would form a deeper grasp of what OR is all about if that was done. Stuff like analysis of residuals and sensitivitey of LP solutions are just too important to be glossed over.
I teach at a business school and we have moved much more to teaching about using models for real-world business decisions. Things like sensitivity do end up taking a backseat, however, since without understanding the underlying algorithm/mathematics things like dual values are just mysterious black boxes. The challenge is, I think, how to get enough of the fundamentals across so people can confidently and correctly use the resulting models. And I think we are all over the map on this at the moment, to the detriment of the field.
Quantum Computing and Learning from Blogs
Ever since I heard about quantum computing (it arose in the 1970s, but most of the really visible stuff started in the mid 1980s, see the Wiki timeline), I have been skeptical. This skepticism arose from a view that quantum computers could solve NP-complete problems in polynomial time. I was randomly wandering the blogosphere when I can across “Shtetl-Optimized” by Scott Aaronson, with the subtitle “Quantum computers are not known to be able to solve NP-complete problems in polynomial time”. Well, perhaps everyone else knew that, but it was somewhat annoying that something I knew for two decades was dead wrong. While practical quantum computers still seem some time away (it seems the state of the art is factoring 15=3×5), trying to determine the effect of quantum computing on OR seems like an interesting question.
One post of Scott’s that I like very much is his “The Hiring Scott Aaronson FAQ“, where he lists some of the questions he was asked in his job search (he is a postdoc at my alma mater, the University of Waterloo’s Department of Combinatorics and Optimization). I’ve interviewed for a job or two in the couple years this blog has been going, but I have not been bold enough to talk about it. Scott uses the entry as a very quick survey of what he believes in, and the interviewers don’t come across like idiots (I guess I would have asked about half the questions myself).
Check out also his article “NP-Complete Problems and Physical Reality“published a couple of years ago in the SIGACT News complexity column. Having lived through an era when NP-completeness results were being churned out by the boatload with only a few providing real insight and advance (kinda like approximation results these days), I have not advanced very much beyond what I knew ten years ago, but Scott’s writing make this look pretty interesting again.
Finally, I am jealous of Scott’s ability to write well enough and intriguingly enough to generate dozens of comments on each of his posts. He points to the following review of his blog:
OK, on to the second breakfast link. Bill Gasarch has reviewed my blog for SIGACT News (scroll down to page 15), together with Lance Fortnow’s and Luca Trevisan’s. Favorite quotes:
Lance is Walter Cronkite. Scott is Stephen Colbert.
The name of the blog, ‘Shtetl-Optimized’ does not really say what it is about. With this in mind one can never say Scott has gone ‘off topic’ since its [sic] not clear what the topic should be.
Perhaps I am sticking to the topic too much!