Saturday, October 3, 2009

What's your favorite Optimization Method?

To plagiarize the title of the latest mediocre movie from Bollywood is fair, I suppose. I have not linked to the movie in question on humanitarian grounds.

Ask any O.R person in academia this question (especially O.R Phds - the rest of the world want to improve the world, but these guys also know how to :-), and you will get a lot of impressive answers, ranging from "Ant colony optimization', 'Benders Decomposition'. ..., to Zangwill's convex simplex method. Let's look at 'E'. The ellipsoidal method is known to perform poorly in practice. However, another method in 'E' is a personal favorite.

Every O.R student hates enumeration and is in fact implicitly taught to hate Mr.E, every step of the way. But consider this. You create a new product with a built-in optimization app having a nice 'what-if' capability. It is still early days and business rules and requirements are changed as frequently as baby diapers. The potential customer tries to understand the behavior of the analytics within the app and works with small data sets to do that. Under these conditions, the only method that is guaranteed to work is enumeration! As you choke with indignation, i have more misery to inflict upon you. Welcome to the O.R heretic's approximation of the number scale.
Theorem: Early in the project, all numbers are less than that 101.
Proof: If you don't believe me, you can start with 1, 2.., and test it a hundred times.

As you begin to curse me into an infinite negative cost cycle, let me reassure you that after you have gained your customer's confidence and business rules crystallize, we can thankfully move beyond enumeration. Even then, there's no steady state, and your beautifully crafted MIP model that worked so well for 3 years can (and will) crumble after 3 years and one day. Not all constraints in real life show up as linear or convex. Some are nasty little buggers. So what works best? Well, for this tab, it is what ever method is smart and close to variable enumeration, i.e., variable generation, i.e., column generation. It's only a small lie to say that everything else in between is just band-aid :-)

I do not personally know Dr. Cindy Barnhart at MIT, but her work in this area sustains the career of many an O.R practitioner. A measure of the long-term success of an industry is if mediocre practitioners can find a decent job (e.g. Bollywood). If you love O.R, pray that i always have a decent job.

No comments:

Post a Comment

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