Dick Lipton of Georgia Tech has a very nice blog on the theory of computation (though it ranges broader than that). He has a fascinating post on “Mathematical Embarrassments”. A “Mathematical Embarrassment” does not refer to the mistaken proof I had in a real analysis course twenty five years ago (that still causes me to cringe) or a similar goof. Instead, it is defined as:
A mathematical embarrassment (ME) is a problem that should have been solved by now. An ME usually is easy to state, seems approachable, and yet resists all attempts at an attack.
This contrasts with a Mathematical Disease (MD), which is harder to define but has a number of characteristics:
1. A problem must be easy to state to be a MD. This is not sufficient, but is required. Thus, the Hodge-Conjecture will never be a disease. I have no clue what it is about.
2. A problem must seem to be accessible, even to an amateur. This is a key requirement. When you first hear the problem your reaction should be: that is open? The problem must seem to be easy.
3. A problem must also have been repeatedly “solved” to be a true MD. A good MD usually has been “proved” many times—often by the same person. If you see a paper in arXiv.org with many “updates” that’s a good sign that the problem is a MD.
So, in operations research we see many people catch the “P=NP (or not)” disease, but I would not call the problem an embarrassment.
Lipton has a number of good examples of mathematical embarrassments, some of which overlap with the skills/interests of more mathematically inclined operations researchers, but none are “really” operations research. For instance, it seems that proving that both the sum and difference of pi and e are transcendental would be a homework problem from centuries ago, but it is still open. That is an embarrassment!
So what would be an operations research embarrassment?
On the computational side, I think of the Traveling Tournament Problem as a bit of an embarrassment (embarrassment is too strong for this: perhaps this is an “operations research discomfiture”). It is a sports scheduling problem that is easy to state, but even very small instances seem beyond our current methods. It was a big deal when the eight team problem was solved!
Just this month, I received word from New Zealand that the three 10-team examples (NL10, CIRC10, and Galaxy10) have all been solved (by David Uthus, Patricia Riddle, and Hans Guesgen). This is huge for the couple of dozen people really into sports scheduling! Proving optimality for this size takes 120 processors about a week so I would say that the problem is still a discomfiture.
But a discomfiture is not an embarrassment. The problem, though simple to state, is too small to rank as an embarrassment. So what would an “operations research embarrassment” be? And are there other “operations research diseases” other than P=NP (though one could argue that by causing people to spend computer-years in solving Traveling Tournament Problems, I may have infected some with a mild disease).
It’s a coincidence, but this weekend I made a diagram explaining the traveling tournament problem for Drools Planner. I posted a blog about it on our blog:
http://blog.athico.com/2009/12/planning-traveling-tournament-problem.html
IMHO, In our community it is the other way. We were so focused on solving mathematical embarrassments that we actually forgot to work on real problems that could make an impact to people’s lives.
Here are a number of problems that I believe are solely OR questions and we have failed to even think about them (these are more modern OR theory, including game theory). HIV in Africa, drug and food delivery to poor rural areas, civil wars, middle east crisis, spread of SARS and Swine flue (and how to quarantine carriers)
We have become slaves for corporates, a bunch of toys, a bunch of tools. We simply got disconnected from people. We became corporate tools for wall street and developed Copulas!. Our whole profession has become an embarrassment. Let’s drop all the P=NP crap! it tears my heart when I think that greatest minds in our world are wasting their time on reducing problems to SAT. Let’s get real people. Let’s have a purpose. Let’s be more involved with people’s lives. Stop donating money to corrupt NGO’s. Donate your minds and time to solve their problems. People get diseases and die everyday. Let’s put our blackboards in our offices to use for something bigger than P!=NP. We can. We should.
We are OR
Thanks for pointer. I did not know about the sport scheduling problem. Great example.
The market split problem was a embarrassment for a while. Same for the Job Shop.
The problem with OR is that Moore’s law ends getting rid of most of the embarrassing problems by brute and exponential force.
Brute and exponential force by Moore’s law doesn’t work. Try the math.
The examination problem with a 1096 exams, 80 period and 28 rooms has 10^3671 possible solutions. If we can do 10^9 per millisecond today (= totally not possible), we can do 10^20 per year.
So starting today, it would only take 10^3651 years.
Every 18 months the computer power doubles. So when will it take only a year to solve by brute force? In 20 000 years the computer power will have improved by a factor of 10^3521.
So if we have a computer faster then we have today and we wait over 20 000 years and we can wait a year for an answer, then brute force and throwing hardware at is the perfect solution 🙂
What happens if there are 2000 exams by then?
See my movie for the math 🙂
http://beta.parleys.com/#st=5&id=1714
Though there’s one calculation mistake in that movie.