Sunday, July 22, 2012

Ekthetikophobia: The Fear of the Exponential

More specifically, the fear of having to solve an NP-Hard optimization problem to save your job. 

Do you or anyone else in your organization exhibit symptoms of Ekthetikophobia?

Sample Responses by Ekthetikophobes
1. Resign: Capitulation is by far the most common response, especially if the person does not have an ORMS background and is oblivious to the 'science of better'. Throw hands in the air, lose faith in humanity, and slurp spoonfuls of the nearest meta-heuristic algorithmic prescription provided by bees, ants, bacteria, squeaky wheels, mutant turtles, ... any nature cure that uses pseudo random numbers. This response is best captured by the Hindi proverb "Naach Na Jaane, Aaangan Teda",i.e., a bad dancer blames the uneven floor.

2. Controlled Panic. This is pretty typical of a generation of OR practitioners weaned on CPLEX. Like MDs trying to decode a deadly new strain of flu, the overriding urge is to throw money at the problem by ordering the latest versions of the baddest bunch of industrial strength optimization solvers in the market with matching supercomputing accessories to run massive benchmarks, and generally scare the pants off their IT managers who work with depression-era budgets.

3. Code. This is relatively more common to programming gurus and follows exactly one rule: If you throw sufficiently well-written code at any problem, it must work. This is so crazy, these guys are on to something here.

4. Publish. The median response from E.phobic research folks is to put this exhibit on a pedestal for everybody to gaze at. It's akin to a biologist discovering a new specie or an astronomer sighting a new planet that shouldn't have been there. Half of these people (surely OR types) will go on to demonstrate the monstrosity of this new problem based on diabolical worst case instances that even a God who plays dice would not inflict on mankind. The other, more elegant half (theoretical CS E.phobes) propose 'factor of 2' approximations that cover all remaining difficult instances missed by the Muggles, yet just as useful practically, before declaring victory. Then over the next two decades: keep shaving of that factor; rinse & repeat; it's a veritable cottage industry.

Exaggerations aside, ranked at the top of the most systematic, resourceful, innovative, and practically useful responses toward 'new' NP-Hard optimization problems must be the approach adopted by Dantzig, Fulkerson, and Johnson (1954) to tackle a 49-city Traveling Salesman Problem using 1950s computing technology and fearless minds that dared lasso the exponential.

July 22: minor fix: added missing text.

No comments:

Post a Comment

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