O.R. Practice: Doomed by Success?

Did you hear about the dissident O.R practitioner who was sentenced to 'a death by a 1000 cuts' ? Legend has it that his body was found remarkably intact, integral ....

The claim here is that an commercial O.R solution to a real-life problem has a finite shelf-life. The graph of potential improvement for a product is concave, and follows the law of diminishing returns. Most of our recent posts have focused on the need to ensure that the first solution has the 'O.R. inside' stamp, since entrenched heuristics of unknown quality are surprisingly resistant to replacement by more smart-logic based O.R methods.

But what happens after you have something with O. R inside? As a former colleague's professor asked him 'So do you sit around waiting for the model to break?' The answer is sometimes yes. Other times, our twitching O.R genes compel us to keep improving upon the solution and after a while, the effort is not worth the improvement. The better the prior effort was, the less likely that you will be allowed to tinker with it any further. Pretty soon it's set in stone and it just becomes an automaton. After a while, it may even cease to be of much competitive value to a company and the functions are likely to be outsourced to a cookie-cutter vendor.

A car designer can spend an entire career endlessly tweaking cars, but an O.R practitioner has to diversify and cannot expect to retire with the same company by endlessly tweaking a product that she or he created and cherished much. O.R. is such a nebulous and ill-defined field in practice that your next manager or director may not have clue as to what the heck your field is, let alone what it is that you have been doing so far. Without strong backing from the highest levels within the management ("Edelman VPs"), the best O.R. efforts can come to nought or go straight to conference and we, the practitioners, have to move on to a different job.

Anyway, this is just one person's take. It would be instructive to hear the experiences of other practitioners.

Theory of Inadvertent Cutting Planes and 2-D LSP

The perils of employing heuristics of unknown quality are often disregarded in practice, all in the interest of 'time to market' and 'practical' solutions for NP-Hard optimization problems. See, for example, Dr. Gerald Brown's papers and presentations along with the late Dr. Rick Rosenthal on this topic. (also see old post on 'the paradox of optimality'). Importantly, Dr. Brown reminds us of the huge difference between 'known unknowns' and 'unknown unknowns', before we start to make the poor assumption that NP-Hard automatically implies a quick, randomized heuristic approach. Dr. Michael Trick's recent blog entry on NP-Hardness is illuminating. Such heuristics do have a role to play in O.R. practice, depending on the business problem at hand. We attempt to illustrate, to the non-technical audience in particular, using a simple example:
The 2-D Laughing Stock Problem

PICTURE 1: shows the feasible region (a polygon), the optimal solution, and the one the heuristic algorithm found.




PICTURE 2: shows the new constraint added by the user that reduces the feasible space. The previous heuristic solution is infeasible now. Solver re-optimizes.




PICTURE 3: shows the new heuristic solution that is near-global optimal. The bewildering user experience so far is that he/she has added a highly restrictive constraint, yet the app ended up with a dramatically better solution, one even better than the "optimal". Imagine driving a car that has such heuristics built into its steering response.

On decisioneering and dealing with sneering detractors

Part of an O.R practitioners job involves selling O.R to non-believers in the organization. Yet many of us in the O.R comfort-zone are firm non-believers that there even exist such non-believers. After all, isn't 'science of better' or its applied counterpart 'decisioneering' self-explanatory? It isn't. The 'analytics' bandwagon is going to ensure that. Last time we looked at the identity crisis facing the poor OR guy. Today, we'll examine more related aspects.

When we say a product has got 'O.R inside', what do we really mean? Is it because it's been autographed by that lost O.R scientist whose owlish ^oo^ spectacles always makes u think 'infinite loop', or, is it the bullet-proof C++ codes of O.R algorithms, the fiendishly reformulated optimization model, or the brand-new, low-latency, 16M$, 32-node, 64-bit, 128-GB SMP RAM parallel machine (yummy!) that smashes thru all your Lagrangian subproblems in a jiffy? or perhaps it's all in the GUROBI or CPLEX solvers that implements the fundamental algorithms?

The old bilateral debate of man v machine, in this context, starts with 'Math v Programming', and in true O.R fashion, cascades into some NP-complete combinatorial debate. heh. The obvious answer to many may be 'all the above', but called me biased - I feel that its the well-trained O.R grad, her/his model and solution approach that seals the deal here. Everything else is essentially a commodity, and can be quickly purchased, and therefore form the supporting cast (The real answer of course is 'none of the above'. It's the power point decks that made it all happen).

Seriously, a practitioner has to have all the soft skills to ensure that O.R gets some small share of credit in such projects, especially when things go right. After all, when its fails, its because of the O.R inside. It's because of you. Everything else was purchased and they work just fine! Suddenly, you alone know which constraint is hurting profits the most, or why a few more discrete variables kill run-times, or if the exponential service time assumption holds. Which brings me to probabilistic 'OR inside' models in practice (more on that another day). By design, its going to give you 'wrong' answers some of the time - unlike deterministic models that provide the illusion of correctness all the time. Good luck selling that!

Identity crisis for the O.R practitioner

If you work in an industry that is saturated by O.R, then this is not for you. Familiarity tends to breed contempt there, and like a bad Steven Segal movie, your work goes straight to conference, heh. It's fun working in an area that is barely touched by O.R, especially if you are a new OR PhD. Your graduate advisor sent you off on your way last week with words like 'remember, no cuts, no glory'. You cant wait to get started ..

"O.R." You realize the name doesn't help. All those rumours in grad school were true! You just go with a simple 'decision science'. Three months into your job, you launch a satyagraha to get your basic tools like Gurobi to work with. You begin your first project.

First off, the sales and pre-sales folks (science is anathema to them but they bring home the bread that allow desk-jockeys like us to tool with OR, so no quarrel) ask you 'so if you are going to solve this using CPLEX, why do we need you? If you can explain 'reformulation', 'NP-Hard' to them and save your new job, your next conference talk will be a piece of cake.

Fact: CPLEX or Gurobi cannot solve any real-life problem directly. Skilled O.R People do (duh!). MS word is just as useful for that purpose.

Next, your strategy folks ("where powerless science meets power point") ask you: why cant our competitor also use CPLEX to solve these problems. whats the big value in decision science?
Not surprisingly, its a bit more difficult to convince folks in the stratosphere that there's real magic in O.R. Heck, it doesn't matter anyway, since they are going to forget it in a couple of days and get back to their ethereal kingdom.

Fact: These tools have blazing fast, industrial strength implementations of fundamental algorithms. The secret sauce is in your business-specific meta-models and meta-algorithms that is independent of the vendor that implements the fundamental tools used inside them.

Facts aside, the word 'Meta' convinces them that you are on to something. Next, you deal with the IT guys. They play for the home team. Problem: OR guys cant code, even though every one of us is convinced otherwise. Your prototype C++ program looks so random, they cant believe that something deterministic comes out of it. The name 'Math Programming' doesnt help either. To save the company from you, they place their trust in their beautifully coded 30-class, 30-line randomized algorithm that everybody now believes will do just as well and go with that. What does the customer care about optimality? It's a battle for another day. Right now, you are getting ready to present your work at a conference ...

Disclaimer: This is a work of pure OR-fiction. Except for CPLEX, Gurobi, and O.R, everything else in this tab has no resemblance to reality.

-------------------------------------------
Here on forward, the Tooler's Tab will waste time solely on OR and analytic topics. For more serious stuff like cricket, fictional detectives, and Indian music, follow the link to my blog on the right panel.

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.

O.R in practice: Time to think small?

Applying sophisticated (LP/MIP-based) techniques in practice is a lot of fun. It's a creative process that brings as much as joy as say, publishing a well-crafted paper in a reputed O.R journal. However, bring such models to life is often a painful process. Unless the problem is "big", companies are unwilling to bring out the 'big guns'. Over a period of time, LP/MIP based models have acquired this (unfair?) reputation for being 'big guns'- During the initial scoping phase of a project, it is 'ruled in' only for mega problems. However, for every large problem in practice, there are 5 small problems for which OR methods are ruled out and replaced by randomized heuristics of unknown quality (so one doesn't have to pay royalty fees to 3rd party solver vendors, among other things). For more details, refer to an earlier post on "OR Practice with 19th Century Optimization Technology".

Why Open source solvers is not used in many practical situations has already been discussed in this tab before. Basically, all these *PL licenses (e.g. EPL, GPL) are simply not worth the potential legal hassles and therefore are of limited use to an OR practitioner. This means that these 'open source' solvers are mainly useful in academia - where researchers already have access to CPLEX/Gurobi, so this whole situation is self-defeating. Something like the Apache license is very usable. Google's Gooplex toy solver is a very positive step in this direction.

I believe there is a strong business argument for making a high-quality Linear-Programming solver freely available for commercial use (maybe an older version that runs twice as slow, but converges correctly). Doing so will boost the use of OR methods in the aforementioned 'small problems' that account for a majority of decision science problems solved in practice, which leads to increased purchases of the premium LP solver and premium MIP solver offering.

Finest Moments of Operations Research - This Day 8 years ago

The second half of September in 2001 was among the finest moments for Operations Research practitioners. For various reasons, these fact is unknown even within the OR community, so this story is worth retelling, even if it has to be from this insignificant virtual outpost of O.R. This story is about a bunch of unknown OR guys in United Airlines. Similar stories are likely to told about other large US carriers as well (Continental has even published some of this in a conference/journal).

There is chaos everywhere on Sept 15th, 8 years ago, since many are uncertain if there are going to be more attacks. In an order with little precedent, no planes are allowed to fly in the U.S for three days. Planes over North America on 9/11 are forced to land at the nearest feasible airport, and thus crews and aircraft are strewn all over the continent (For example, a small airport/town in Newfoundland played host to thousands of passengers and many large airplanes during those days and many were accommodated in people's homes. There was an interesting movie about this on Canadian television).

The larger Airline carriers chalked up huge losses with little to no revenue coming in. Around the 15th of September, flights are allowed to resume. Airlines are faced with mammoth decision problems. How to build a new airline schedule from scratch for thousands of flights, and crew schedules for tens of thousands of crew members to safely get through the next few days?

How to do all of this in the safest and most cost-effective manner?

Airline planning/optimization tools in Airlines are typically designed toward building schedules a month or two in advance. Since these schedules are built so early, the actual pilots and aircraft that operate these schedules are assigned much later by other systems. So the O.R guys in the airline were brought together and given these tasks:

a) building a new optimization model that would construct a new airline and crew schedule

b) such that the schedule was feasible, safe, and bring all the crew members back from all these remote airports to their domiciles in a safe and cost-effective manner and then reassign them to new flights

c) assign all pilots by name to these schedules

d) solve this O. R problem that is about 100 times more complex than what is normally seen in airline business, and do all this in 3 days

e) hook up the model to the on-line (real-time) database for input, and to the real-time crew-recovery system residing in main-frame computers for output in a seamless manner

The O.R guys (comprising of more than 10 nationalities) responded in an amazing manner. working day and night shifts on a 24 hour clock, a group of about 10 O.R PhDs just out of college invented brand-new airline scheduling models (unpublished to this day - they don't look pretty but were darned effective and had several cool innovations). IT engineers hacked away to rig up a flawless I/O hookup. Their effort was no less amazing as they had to overcome many unforeseen challenges. For example, it was found that many of these airports where crews were stranded were minor ones using alphanumeric codes, whereas in 2001, large US airlines served airports that no numeric characters in their names!)

There were lucky breaks and heartbreaks along the way. It was discovered that the real-time crew recovery system could not delete existing flight attendant assignments, and therefore, our new optimization models were 'over-covering' many flights. However, in the days after 9/11, flight attendants (mostly women) had no protection against terrorists in the main cabin and therefore, about 60% called in sick. This canceled out the over-covering effect and some how, the whole thing worked. It was an amazing sight to see the very first United flight come back home to Chicago after 9/11. The pilot obtained permission to fly over the United HQ and dip his wings in a show of unity, and it was beautiful.

In between, there were bomb threats that led to at least two evacuations. Then the grim reality that the junior OR guys would lose their jobs due to crippling airline losses. Despite all this, an unassuming bunch of young OR practitioners saved the day for United. After that experience, no real-life O.R problem was scary enough.

Everybody fights terror their own way, but the OR way is likely to be the most efficient.

The amazing computational world of DIY Simplex

Operations Research students seldom get to look into details of sophisticated implementations of a sparse simplex solver for linear programming. The same is true for O.R practice where your focus is how best to use such tools. But if you work for a setup that cannot afford the steep royalty you have to pay for such tools, you can build your own in a few months. Its more likely to be about 100 times slower than Gurobi or CPLEX on large problems. If your LPs are small sized (less than 50,000 rows), it may do a decent job, but hey, the experience is quite amazing, and I highly recommend it. For one, the system of linear equations that you solved since high school will never seem the same. And you can read a couple of important journal papers authored by Suhl and Suhl (i kid you not). The dual method is the best default choice. If you have starting trouble, trying using 'Gooplex', google's first draft LP solver. Its a toy solver, but the code implementation looks professional and is a good starting point.

On the other hand, there's always COIN-OR, the good quality open source repository.

The tool cycle

Fictional Amateur detectives represent the ultimate in tooling. you solve a case in an hour (or as long as your book or tv show lasts) and take a break for the rest of the week. Sherlock Holmes had no other work. He played the violin badly and morphine had little effect on his deductive powers. Mrs. Hudson does the cooking, cleaning, washing, and Dr. Watson is there to lend a ear and keep a watch on his health and boost his ego. And when the right case comes, you turn on your industrial strength detective-lights and save the day and have an immediate impact on ground reality. No nagging women at home. The rest of the time, you polish your skills by publishing 'monographs' on bees, cigar ash, and other important stuff. You have just enough clients to keep this tool-cycle going.

Sounds like a nice job description.

Top-10 detectives in fiction - updated

This tab returns to what it does best. tool. In the spirit, we see some seismic shifts in our old top-10 detectives list that was released a few months ago.

Firstly, reviewing some of the old episodes of Sherlock Holmes boringly confirms his position at the top. He's good enough to publish analytic monographs on bees and cigar ash. no contest.

Ok, we add to our list, the brilliant native Tamizh-speaking detective from Kerala, Mr. Sethurama Iyer (or SRI). Sri comes to us from a cool sequence of plot-driven movies in Malayalam, brought to life by the eminent Indian actor Mammootty. Or ma2m2o2ty if u are into alphanumerics. In a judicial system dominated by self-servers, stupidity, and sloth, SRI brings scientific temper, vigor, and a devotion to the truth. He can also debate Vedanta and Hindu philosophy with the best.

Next, we go all the way to Sweden to meet Mr. Wallander. This TV series (check out pbs.org) is so dark, and the character so bleak and driven, the economic recession is a relative piece of cake for that one hour.

Our updated list with geographical locations looks like this now. We have booted out the Law-Order duo of Brisco and Green, and Indian favorite Karamchand, who were tied at 10, as well as the sole female representative, Miss Marple.


10.Goren (USA, NY city)
9. Cadfael (England, Shrewsbury)
8. Monk (USA, Frisco)
7. Wallander (Sweden)
6. Der Alte, The Old Fox (Germany)
5. Sethurama Iyer, (India, Kerala)
4. Byomkesh Bakshi, (India, Bengal)
3. Hercule Poirot (Belgium)
2. Columbo (USA, Los Angeles)
1. Sherlock Holmes (UK, London)

Kargil represented the first positive change in fortunes in the war against terror

It's been ten years since more than 500 of India's bravest gave their lives fighting desperate, uphill battles, in sub-freezing cold in the highest battlefields of this planet against well-entrenched Pakistani regulars and afghan mercenaries within Indian sovereign territory. If the first ten years of the Pak Army-ISI-taliban nexus (PIT) terrorist agenda (1989-1999) went PIT's way in terms of changing ground reality and world perception, Kargil resulted in the first positive change, with the world finally becoming aware of PIT's crazy designs, and the last ten years have increasingly opened the world's minds to the ever increasing threats emanating from the PIT nexus.

From the frozen battlefield of Rezang-La in 1962 (among the most heroic, last-ditch military battles recorded in India's multi-millenial history) to the battle for Tiger Hill, the Indian Jawan, like every honorable soldier in the free world fighting on the side of democracy, has fought fairly, and in the end, prevailed, and if he had to, died, but never backed down. This tab salutes them on Vijay divas.

Optimizing the Health-Care Reform Package of Obama using Operations Research

In his press conference yesterday, President Obama used the word "unconstrained" while talking about the escalating costs within health care system. He later used the term "constrained system" (or was it "constrained model") when talking about financial regulation. Is one of his advisors an OR guy??

Another interesting aspect that he mentioned was that some democrats wanted some additional provisions in the healthcare package that would address their regional interests, which would then cost additional money, so some chopping and changing has to be done and the August deadline is flexible as well. To an Operations Research person, it seems a sin not to optimize and automate the fine-tuning of the package, which would lead to savings in time and money. So after adding all the fundamental (must-have) provisions, the remaining 10-20% of the contentious provisions (bids) can be optimized to save taxpayer money.

If a new health-care provision i brings in v(i) net votes and net cost c(i) and removing a pre-existing provision j results in v(j) net votes at a net cost of c(j), and defining binary decision variables:
xi = 1 if new provision i is added, 0 otherwise
yj = 1 if existing provision j is removed, 0 otherwise

index set i runs over the set of new provisions, while j corresponds to existing provisions that are candidates for removal.


the bill optimization problem becomes:

Minimize sum(i) ci. xi - sum (j) cj. yj
subject to:
sum(i) v(i). xi - sum(j) v(j). yj >= MINIMUM_VOTES_NEEDED_FOR_CONSENSUS
x, y binary

The aim of this optimization model is to minimize the total cost of fine tuning the package, subject to meeting the minimum approval needed to get the package approved. Obviously, this is a simple linear integer knapsack problem and in practice, there may be more constraints and objectives in the world of politics and governance. Furthermore, we assume linearity and a simple model to start off with. To improve acceptance, one can also add constraints based on other provision attributes. e.g, to satisfy budgets by area of Health-care. Alternatively, one can maximize the number of votes in favor of the package and add a constraint on the total incremental cost of fine-tuning.

Conceptually, the model is quite interesting. While it will generally aim to keep the best bang-for-buck provisions, it also recognizes that these provisions cannot be split into 'half-measures' to meet constraints and therefore a greedy selection based on bang-for-buck may be suboptimal.

Duality of Indic religious philosophies: Do they sink or swim together?

Dr. Hari.J has an interesting blog post on this subject. He quotes Swami Vivekananda who opined that Hindusim and Buddism cannot survive without each other. On the other hand, as Dr. HJ rightly mentiones, there are few places in the world where the two religions do exist independently, without the other.

Geographically yes, but perhaps they are not intellectually and philosophically independent. I suspect the Swami meant the latter. Indeed, Indic religious philosophies (Hinduism, Buddhism, Sikhism, Jainism) are all joined at the hip and generally thrived up until a few 500-odd years ago due to healthy competition (i.e., very vigorous discourse and debates. Presumably, changing 'religions' in India (one cannot be sure if they thought of it as a religion as defined today in the western world), during those days was perhaps as easy as the switch between windows, Linux or Mac. These debates had an impact on the ground reality and "optimized" the Indic religious philosophies better. For example, Adi Sankara of Kerala is credited with having "upgraded" Hindu philosophies that eventually allowed Hiduism to survive in India. This he did via vigorous debates with Buddhist leaders.

That process is dead now and perhaps the Swami implied that he did not want this process of discourse and debate to stop. Not surprisingly, a lot of the angst in the world today stems from frustration with entrenched harmful practices within ones own religion, in tandem with of a lack of mutual respect for how the other religion's core philosophies are the same and how they are different.

[Edited on 7/22/09 for typos]