Lassoing the Exponential

An abbreviated version was blogged for the INFORMS 2014 annual conference as 'Not Particularly Hard'.

-------------------------------------

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 the work unpublishable? I don't know know, but 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 but elegant '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. Encountering a really difficult optimization problem can be a positive thing, depending on how we respond to it.  Often, there are alternative approaches to business problems that at first glance, appear to have  insufficient data: this tempts us to throw in the towel and send the problem back to the customer and say "infeasible" or "unbounded". Instead, we can use a Sulba and Lasso our decision variables. This could well be an ORMS motto:

"When the going gets NP-Hard, Operations Researchers get going" :)