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]

Test Cricket rises from the Ashes

After the heartbreaking sight of seeing half-empty stadiums during the thoroughly exciting India_Aus test series in India, 2008, it is great to see the support in England for the ashes. T20 has its place for the instant-fun factor, but test cricket is the real deal. Facing multiple spells of hostile bowling from 'freddie' Flintoff at speeds up to 95mph, with the crowd against you, is quite a test, and a thrilling spectacle for everybody else. Test cricket at its best is a series of bone jarring, uncompromising gladiatorial contests involving brute strength as well as subtle guile, waged within a chess-series-like intellectual campaign at the higher level, all of which is encoded using myriad gentlemanly rules of engagement, spread over five days. After all the hard work, you may not get a decisive result at the end of it.

The whites of the uniforms and the greens of outfield dominate the view, but at its core, cricket is bloody red. More than any sport (golf comes close), the injuries to the psyche of a test cricketer are hardest to recover from, as Greg Chappel said. If you get out, you are out of the test match for a couple of days before a second shot at redemption, if at all there is one. Indeed, test cricket is the most realistic reality show the world has invented. And yes, you can tool for hours watching it. Lets hope for many more riveting contest during the ashes and may Test cricket prosper.

Recalling the Sunny Days - He wore India on his sleeve

Hail Sunil Manohar Gavaskar, the world's greatest opening batsman across eras! Sunil Gavaskar was born on July 10th 1949. Feels like he just retired a few years ago after that masterful near-double in the unofficial (Bicentennial?) test at Lords. Never wore a helmet against the W.Indian Quicks in the 70s-80s and never backed down, ever. Today's NFL-style padded up millionaire cricketers on benign pitches resembles a Bollywood poor-joke compared to those days of real cricket. One of the Windies fans (Lord Relator) even wrote a calypso in awe of his batting ....

I recall his jokes during his lecture at IIT-Madras a decade and half go.
Q. Why did you refuse the MCC membership ?
A. That's incorrect. I love the Madras Cricket Club and am happy to be an honorary member" (laughter among the entire campus who turned up on the occasion, well after his retirement).
Q. Sir, we meant the Marylebone Cricket Club ..
A. Oh that. Who cares about some Firangi Cricket club. I'm honored to be a part of MCC this week. (chuckles). Audience goes nuts and eats out of his hands afterwards.

Many may not agree with some of his potshots at the Aussies (especially the one against Hookes), and his commentary may sometimes put u to sleep, but every thing else that Sunny does is just fine with me. If only that idiotic owner of the Kolkata KR T20 circus had listened to SMG and fired Buchanan before this year's edition, instead of after ...

And yes, Buchanan has conferred with England before the ashes. He's even spilled secrets. Any chance of an English victory is now extinguished. A clever Aussie plot!

GooPLEX: Go Google! Wake up COIN-OR!

The first release of Google's open-source simplex solver (which this tab dubs 'GooPLEX') appears to be a simple toy version of the simplex method for Linear Programs. GooPLEX appears to be missing all the basic ingredients of a practically viable solver such as the revised simplex method, dual simplex, sparse LU factorization, etc. The good news is that we finally have an open-source solver whose license (Apache) is actually useful in the real world.

COIN-OR has a dedicated team, and a fantastic repository of solvers and other OR stuff. Unfortunately, its licensing (CPL and now EPL) is still uncomfortably and frustratingly restrictive for companies to use commercially, and thereby also improve by contributing to it. Consequently, it is likely that COIN-OR is going to be popular mainly within the OR-academic bubble. Ironically, most OR/IE departments will already have GUROBI or CPLEX licenses and thus wont be dependent on such *PL license based LP/MIP solvers. We OR folks need to stop shooting ourselves in the foot.

The smartest course of action for IBM and the COIN-OR team is to do what Google did and make the COIN-OR available under Apache/BSD. On the other hand, one hopes Google's developers and the OR community will improve upon GooPLEX and make it a scalable product. Go Google, and welcome to the world of O.R!

Google releases open-source Simplex Solver

good news for O.R practitioners. I wish COIN-OR would make their license as friendly as google's simplex solver. We'll have to look into the code to see if it's an efficient and effective implementation (e.g., dual simplex with LU factorization) for large LPs.


Here's the license details cut-and-pasted from the source.

1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */