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

3 comments:

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

    ReplyDelete

  2. My name is Neha Gupta. I run my independent Mumbai Escorts Service. I am an independent Mumbai escort girl. My service charge is low according the market price. My service is super, because I know very well the personal need of my each customer. I am comfortable to provide my Mumbai Escorts Service at your home or in Hotel. 24X7 I am available Call- +91 9OO4458359 Visit- http://www.nehagupta.biz/
    Enjoy Lovely Life With Mumbai Escorts Service +91 9004458359
    Ladies with sex appeal have a demand in society. Are you looking for a lovely night? Do you require a companion? The Mumbai Escorts Service are present to help. Moreover, when you are lonely, they are your best friends. Again, if you need a break from your daily schedule, pretty girls can give you a boost. One day outing with them is possible. If you want them for a night, they will agree with the same. There are more factors to hire the Mumbai Escorts Service. They are the complete piece of entertainment all around
    Fulfill Your Wish With Mumbai Escorts Service
    Wish remains unfulfilled for many people. There is different type of wish which one can think about. Are all the wishes fulfilled? Folks think a lot about what they want. But, they don’t work to get it fulfilled. Getting a good companion can be a desire too. But, most people stay alone. Neither do they try to stay away from it. But the Mumbai Escorts Service can be your friend. Your desire of getting true friend can be fulfilled. You can share everything with them. Moreover, they will act exactly like friends. Also, the pretty girls can keep secrets within themselves.
    Golden Moments With Mumbai Escorts Service
    Did you even feel the pleasure of moments? Some moments in the life are very special. It is possible with the loved ones. Happiness is all around. The Mumbai Escorts Service will treat you like their close friends. You can get the moment which you have never thought about. This is where you get the best feel. The togetherness is a feel all around. The closeness is also there within two of you. The happy moment is also there. The love and happiness are combined together. This is where you make the best with the petty girls. Call +91 9OO4458359

    ReplyDelete
  3. Contact Vashikaran Specialist in Mumbai.We Are the Vashikaran Specialist Astrologer. Ask Free Question about Love Vashikaran, Love Back, Inter-Caste Love Marriage, Black Magic. 24X7 We Are Available. Call +91 9915707766 Visit- http://www.lovevashikaranexpert.in/

    Ask Free Question With Vashikaran Specialist In Mumbai, 09915707766

    The art of astrology has many branches. Each astrologer takes up the special task. They go deep into the facts and figures. This bring out conclusion. Vashikaran is one of such expert art. Very few astrologers can do it. This needs in-depth studies and special drill. Years of skill with constant practice are vital. The Vashikaran Specialist in Mumbai has the ultimate success rate. This art is based on calculations. The experts should be good in maths. It is based on movement of planets. The phone number is available to reach the vashikaran expert.

    Knowledge Of Vashikaran Specialist In Mumbai

    The learned person can do Vashikaran. He can win over the mind of another person. The other person will perform all the actions according to his instructions. This art is very effective when you wish to fulfil your desire. You can ask the Vashikaran Specialist in Mumbai to bring your love. He will be quite efficient in this. There are some instructions which you need to follow. This can make your love come back to you. Get the great satisfaction with the effort of Babaji. He studied many cosmic views. His guru taught him almost everything.

    Vashikaran Specialist In Mumbai – Away From Bad Companion

    Sometimes you may also get good advices from the vashikaran expert. Human- being make mistakes. Even when you are willing to get something that can be positive or negative. There are instances when people go for criminal offences. The Vashikaran Specialist in Mumbai will give you advices to stay away from it. When you approach him with a cunning thought, he will understand immediately. The specialist babaji will warn you about this. What harm can you come across due to this action will be made clear by him. Some of the clients are very stubborn. They wish to get the vashikaran even after the warning. In such a situation, vashikaran specialist in Mumbai is not responsible at all.

    ReplyDelete

Note: Only a member of this blog may post a comment.