Thursday, September 24, 2009

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.

Tuesday, September 15, 2009

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.

Wednesday, September 2, 2009

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.