Saturday, October 25, 2014

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" :)


  1. Great post, I appreciate you and I would like to read your next post. Thanks for sharing this useful information Useful Vastu Tips

  2. We Are The love problem solution baba ji. Ask Free Question Related to Love Problem Solution, Inter Caste Love Marriage, Love Problem Solution, Vashikaran Solutions, Business Problem, job problem etc. We Will Be Happy To Answer You Free Of Cost. All Days We Are Available To Help You. For More Information Visit Our Website

    Get In Touch With love problem solution baba ji +91 9915707766
    Are you in love with someone? Is your family not accepting your life partner? Love problem solution baba ji will help you here. He will give all the tips to get back your love. There are ways to make your family convinced as well. He understands your problem. Baba ji has solved many cases like this. All the clients of the love guru are very happy. They are staying happily with their loved one. Some of them are also married with the person whom they love. The love problem solution baba ji is the key for your solution.

    Background of love problem solution baba ji
    You must be eager to know about the background of Baba ji. This is properly mentioned in the website. Yes, the baba ji is having his official website. The history of love guru is mentioned there. He solved many cases just after his recognition as an astrologer. There are hardly any cases where he has proved to fail. The love problem solution baba ji has maximum success rate. Just visit his website and you will know everything about him.

    Behaviour of Love Problem Solution Baba Ji
    Many people are afraid to visit the astrologers. Do you know why? It is just because the words of astrologers are harsh. They may say some negative facts about you. Even the behavior of some aged astrologers may not be up to the mark. But, you don’t have to worry when the person is love problem solution baba ji. He is totally different. He is not like any other conventional astrologers in the market. He will speak with you just like a friend. You will automatically speak about your problems to him. You will understand very well about his manner and behavior. Call +91 9915707766