While working on a new retail optimization problem a few weeks earlier, a colleague was a bit disappointed that it turned out to be NP-Hard. Does that make it unsolvable? No. The celebrated Traveling Salesman Problem (TSP) is known to be a difficult problem, yet Operations Researchers continue to solve incredibly large TSP instances to proven near-global optimality, and we routinely manage small TSP instances every time we lace our shoes. Why did I bring up laces? In a moment …

Hundreds of problems that are known to be difficult are ‘solved’ routinely in industrial applications. In this practical context it matters relatively less what the theoretical worst-case result is, as long as the real-life instances that show up can be managed well enough, and invariably, the answer to this latter question is a resounding YES. The worst-case exponential ‘Simplex method’ continues to be a core algorithm in modern-day optimization software packages.

This issue of contextual optimization is not a new one. For some ancient people who first came across ‘irrational’ numbers, it was apparently a moment of uneasiness: how to ‘exactly’ measure quantities that were seemingly beyond rational thought. For some others, it was not much of an issue. Indeed, there is an entire body of Ganitha (the science of calculations, or mathematics) work in Sanskrit, the ‘Sulba Sutras‘, almost 3000 years old, where irrational numbers show up without much ado. ‘Sulba’ means rope or lace or cord. If we want to calculate the circumference of a circle of radius r, we can simply use (2πr) along with an approximation for ‘π’ that is optimally accurate, i.e., good enough in the context of our application. If we we did not have a good enough value for π, we could literally get around the problem: simply draw a circle of radius r, and line up a Sulba along its circumference to get our answer. For really large circles, we can use a scaled model instead of ordering many miles of Sulba. Not particularly hard. The discovery of a new NP-Hard problem can be a positive thing, depending on how we respond to it. This could well be an ORMS motto:

“When the going gets NP-Hard, Operations Researchers get going”.

And this November, many of the world’s Operations Researchers are going west, to San Francisco. Welcome to the INFORMS annual conference!

1 Comment