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

4 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
  4. We Are Vashikaran Specialist Astrologer. We Are Famous As Vashikaran Specialist in Delhi
    . Contact Us Ask Free Question about All Type Love Vashikaran, Love Back, Inter-Caste Love Marriage, Black Magic. Get Positive Result In One Hour. 24X7 We Are Available To Answer Your Questions. Call +91 9915537976 Visit- www.vashikaranhelps.com
    Vashikaran Specialist in Delhi: +91 9915537976
    Delhi, the capital of India has many positive points. It is one of the populous cities with many inhabitants driving in. The scopes for job and education are good. Folks can get tourism benefit here. Staying in Delhi, if you wish to fulfill your dreams, and then approach the Vashikaran Specialist in Delhi
    . They are the experts of this trade. Moreover, you many get them online. You don’t have to visit them in person. Also, they can bring happiness back to life. In the light of above statement, experts have high demand.
    Pick Up Right Vashikaran Specialist in Delhi
    You may find many people with vashikaran solution ad. Are they are worth? This is an important fact to look out. If you are staying in Delhi, then the experts are at your service. Delhi is the city with both positive and negative people. Not only will you find the real people but also the cheaters are present. Research is equally important to find the right Vashikaran Specialist in Delhi
    . Our website can help you here. Also, we are the genuine place to get your every solution. Not to mention all factors, these factors are very important.
    Best Vashikaran Specialist in Delhi
    Folks received great help in every problem. Some issues are one time but others are persistent. Of course you will get solution for all. The expert Guru in Delhi has the talent. Moreover, their focus is high. Additionally, you may get many other benefits. If you wish to know about the future, Vashikaran specialist in Delhi will speak about it. Also, what he say is correct. Folks have received the clue in many cases. All the hard time can go away. Their expert help is there for people with all ages.
    Countless Help with Vashikaran Specialist in Delhi
    The vashikaran specialist not only has solution for one problem, but also he has the real zeal to solve all types of problem. For him, all the problems become no problem. The health solution is also with him. In many cases, folks with deadly disease approach the Vashikaran specialist in Delhi. It is the stage when doctors have lifted their hand. Only the experts in vashikaran can give you the remedy. In the same way, you can check it online. The services which they can provide are many. He can make everything easy. It is the time to check the major strength. Call +91 9915537976


    ReplyDelete