Wednesday, November 24, 2010

2G scam followup: True opportunity cost of misallocating scarce resources

Please see the most recent post for the preliminary analysis of this scam. This is a follow up tab posting. Per this article on

" .. The Comptroller & Auditor General has calculated in his official report that the exchequer lost the truly mind-boggling sum of Rs 176,645 crore (Rs 176.64 billion) .. "

So in case there was any well-intentioned doubt that the 1.76*10^12 number was cooked up, it is now very clear that this number is (sadly) official. Actually, i would expect the number to be even higher, when you compare the true opportunity cost (due to a miserably and deliberately bad mis-allocation) relative to the value of optimal allocation.

When we read about scams like this, we realize how important it is that solid OR models be built to perform exploratory studies and simulations be run prior to allocating almost priceless resources. The supreme court of India said that "the 2G scam puts all other scams [in the history of India] to shame". When so many in India are dying of starvation and are homeless, such giga-squandering of public money by a corrupt government is nothing short of a 'monetary holocaust'.

It must be made mandatory for governments and public organizations at any level to conduct an appropriate OR analysis before allocating any scarce resource that belongs to the public. If the government of India had funded an OR group to spent a exaggerated and gigantic (or microscopic if u compare with the final loss) sum of 10 million $ for an OR analytical study, it would have paid for itself many, many times over. Well-run OR projects typically cost much less while providing incredibly impressive value measured in terms of incremental-benefit/project-cost return ratios (read the Woolsey papers for more on this).

Side note
Statistically, #barkhagate is turning out to be the most continually tweeted phrase in virtual India. Ever. It is trending so hot, you can make a virtual omelet there. Social media is making its presence felt in a very real way wrt real world issues in the largest democracy in the world, and consequently, the manipulative mainstream English media in India that had previously closed ranks on this topic so far, is now being forced to cover this critical news.

Monday, November 22, 2010

Measuring the impact of corruption via OR models - the 2G scam in India

The recent 2G spectrum scam in India has taken corruption to epic levels. Large-scale theft is now being expressed as a percentage of India's GDP for convenience of notation. The amount of taxpayer money siphoned off due to the nefarious actions of certain senior ministers that resulted in an inefficient (non system-optimal) resource allocation wrt the 2G spectrum is estimated at 1760000000000 Rupees (1 US$ ~ 45 Indian Rupees), or 1.76 Trillion Rupees. This seems to be a conservative estimate.

If we compare the value of the corrupt allocation with that of the true system-optimal allocation, I wonder if that loss estimate would be even higher?

This large rupee number is something one usually throws out wildly, except that in this case, it is shockingly close to fact. Furthermore, well-known award-winning cable-news journalists (marketed as fair and balanced) have been implicated by an angry public and audio-tapes have surfaced that seem to allegedly point to their dual role as information-sharing lobbyists, working as mediators between coalition partners of the government to ensure a cover-up, as well as scripting and stage-managing TV shows and news articles to alter public opinion. This has been dubbed 'barkhagate' on the Internet - yet another a cliched 'gate' scandal, but this scandal makes Nixon look like an Eagle boy-scout. Twitter-istan is abuzz with #barkhagate.

Obama, during his recent visit to India, referred to the Indian Prime Minister as his 'Guru', partly due to the PM being an economics professor in a past life. Should he now be called the GGuru? He once was an admired man for pioneering India's economic reforms in the 1990s. Sadly, along with that has come scam after scam, and many in India get the feeling that the actual powerful core within the ruling coalition have this 80+ year old ex-professor set up as a fall guy for their series of epic embezzlements (2G is just the latest).

The fair bandwidth resource allocation problem is a very, very interesting OR challenge. Several cool mathematical models, including combinatorial auction, along with clever Benders decomposition based solution approaches have been invented to solve the resultant discrete optimization formulation (e.g., winner determination problem)

So how does corruption impact such OR models? It is an important as well as an interesting question that deserves more formal attention. If corruption is modeled explicitly within a model, then efficiency, cost-minimization, and revenue maximization are no longer the real objectives. Shadow prices and reduced costs will be misleading. Objective function cost coefficients are inflated or discounted based on the intent of the scam. A machine's throughput may be far less that what shows up on paper due to its unknown, substandard quality. The data will be really messy. Ethics-driven regulations and their corresponding constraints will be missing. By definition, optimization algorithms seek out extreme values and push the envelope. Unethically used, such methods will help maximize corruption.

Dubious organizations may simply place the blame on OR models and the analytics, rather than on the crooked ones who misuse it. Like journalism, whose reputation largely lays in tatters, corruption in analytics will have a devastatingly negative impact on the public perception of mathematicians and OR folks who have won respect as truth-seekers. Once lost, such hard-earned goodwill is almost impossible to regain. As OR people, we have a responsibility, both natural and inherited, to maintain high ethical standards and actively seek the truth (or in OR practice, 'the best obtainable version of the truth' as Carl Bernstein would say). After all, the entire theory of optimization and duality is ultimately based on the notion of fairness and rationality. The insidious noise that undermines fair duality has to be recognized early enough, and must be filtered out.

A question will be posted on OR-exchange to initiate a discussion on this important topic.

Sunday, November 14, 2010

OR practice tip: find and eliminate unnecessary constraints

A great example to illustrate this vitally important piece of practical OR would be this classic 1980's movie scene from the 'Policy Academy':

Always knew that cutting all those redundant classes at St. Joseph's in the 80s to watch a projection of a linear "English" comedy in the relaxed atmosphere within the bounds of the adjacent Brigade Road theater in Bangalore, India served the dual purpose of preparing one for a OR career. Is OR great or what :-)

There are many practice instances where a customer has been 'blindly' following the constraint "because". Opening the eyes of your customer (especially the upper management) to this fact could be a huge value add on your part. Furthermore, when it comes to optimization models, such insight into the actual business problem sometimes enables us to bypass a strongly NP-Hard MIP and instead work with something relatively simpler, like an integer knapsack formulation.

Take this wonderful real-world example from the book "The Art of Innovation", where IDEO was redesigning a major medical instrument for heart patients during balloon angioplasty. See the Google books excerpt here. The key observation here was that everybody assumed that the instrument was "supposed" to be operable by one hand. Why? well presumably because the old instrument makers marketed it as such, and after many years it became a "design constraint". By noting that the other hand of the operator was pretty much idle while firing up this instrument, the designers were able to eliminate this unnecessary constraint. This led to a much saner and user-friendly design that also helped eliminate the scary 'ratcheting' sound that used to come out of the older instrument as it booted up, which used to scare the gowns off heart patients! The new product eventually ended up as a win-win for both patients and therapists.

In practice, there are constraints, and then there are constraints.

Tuesday, November 9, 2010

MIP feasible completions and the wheel of fortune

First the 'talk of the town'. The miraculous wheel of fortune solution using a single letter.

Initial feedback suggests rigging etc, but to OR'ers this 'hole in one' should not come as a drastic surprise. After all, this occurrence is infrequent but not impossible. One can pose this puzzle as an MIP (or solve using constraint programming), using binary variables to represent letter-choices for every blank, along with additional constraints that ensure that words are selected from a dictionary, while also ensuring that the sentence is grammatically correct, and so on. Of course, it would be a rather unwieldy MIP and a pure generic-solver approach may take forever. However, by exploiting the language structure and leveraging our learning from prior experience with the kinds of phrases that typically show up in WOF, it should be possible to significantly reduce the number of combinations to be explicitly explored. Note that only one such feasible solution is the right answer to the original WOF puzzle and to guarantee this, one usually needs more letters to be exposed to break ties. Isn't that how the miracle workers at Bletchley park cracked the Enigma codes in WW2 and began solving 'puzzles' fast enough to make that information usable?

Real-world MIPs often have such hidden structures that our customers understand far better than pure OR types. I was constantly impressed that the resident real-time crew schedulers at United Airlines would routinely come up with remarkably good quality feasible crew pairings (partial schedules) at the drop of a hat that would make us OR PhDs look so stuffy! Such crew pairings have to satisfy a myriad of FAA and company-negotiated "nonlinear and non-convex" work rules to confirm feasibility.

Another important aspect of real world decision problems is that the line between feasibility and infeasibility is often blurred. For example, look at the snippet from this email i received recently. It's one of those that get forwarded around and comes back to haunt your inbox once every two years.

I cdnuolt blveiee that I cluod aulaclty uesdnatnrd what I was rdanieg. The phaonmneal pweor of the hmuan mnid, aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it dseno't mtaetr in what oerdr the ltteres in a word are, the olny iproamtnt tihng is that the frsit and last ltteer be in the rghit pclae. The rset can be a taotl mses and you can still raed it whotuit a pboerlm. This is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the word as a wlohe. Azanmig huh? Yaeh and I awlyas tghuhot slpeling was ipmorantt! If you can raed this forwrad it "

Posed as an MIP, almost every one these partial solutions (words) is tragically infeasible, and yet, can be perfectly interpreted by the end user in real-time and combined into a wholly understandable paragraph.

The point is that many abstract MIPs may be hard to solve, but in almost all real life instances, there is plenty of additional information from the real world that typically helps us generate meaningful business answers via such math models. If we do it the right way, NP-Hardness rarely leads to a business issue. The combination of good OR skills, MIP solvers, and domain expertise can solve complex business decision problems in real-life quickly enough to let customers gain a tangible competitive advantage.

Monday, November 1, 2010

Power-point has no place in an analytics presentation

Most of us have heard about the 'paralysis by power point' in the US Army and how it has resulted in miscommunication and a lack of attention to detail. The display of statistics and results has become a scientific discipline in itself, and for us O.R./analytics practitioners, there is much to learn, and quickly.

Most of us in the world of O.R. run our optimization models, simulations and statistical programs and once we are done, we pay scant attention to how it is presented to an executive or non-technical audience. Boring and static charts, mind-numbing M x N matrices of numbers culled from spreadsheets accurate to the 3rd decimal place, all embedded within power-point slide after lifeless slide only serves to underwhelm the audience. Worse, it threatens to undo all the months of hard work we OR types have put in and undermine the cool results we obtained. The audience tends to shut down and fall asleep after the first couple of ppt slides. The art of the analytical presentation is by far the most neglected aspect at O.R. graduate programs, where unlike the real world, a PhD (candidate) only present results to another PhD, and then mostly within the same department.

O.R. does not end with model building and numerical results. It ends only when we can de-mystify analytics so our customers can truly comprehend what all this means to them in the limited amount of time we have to make our case. Toward this, smart people are coming up with innovative ways of displaying data, results, and statistics. For example, you may not grasp what "4.3689 meters" really means, but if I told you "twice the height of Kareem Abdul-Jabbar", that would give you a better picture.

Let's look at three great examples of presentations of analytical and statistical content.

Exhibit One: Hans Rosling, founder of gapminder, doing a presentation that in less in 20 minutes of power-packed slides and animation, gives the audience a fantastic and insightful overview of socio-economic and standard-of-living data for the world from the past (all the way from 1858) to the present. He then extrapolates this information to predict future economic prospects of key Asian countries (India, China, Japan) relative to the U.S. and the U.K. Watch it till the end. There is a wealth of useful information packed into each slide that integrates into a vivid narrative that is easy to understand. Within a few minutes, he has the audience eating out of his hand.

Exhibit 2: This is a simpler one that in a single picture shows the true size of Africa in way that most of us immediately grasp. The 'relative size' approach again works well. As a side note, the way the different countries fit into the continent of Africa seems to be a great approximate solution to the corresponding non-convex set-packing problem!

Exhibit 3: The well known single chart of Napoleon's disastrous Russian campaign of 1812-1813. Recognized by many as the "best statistical graphic ever drawn". It tells you pretty much everything relevant to the topic. Now imagine the mayhem that would have been caused by using 57 power-point slides filled with numbers and separate charts for attrition, time, temperatures, geography, etc. to show this same thing.