Analytics and Cricket - VII : Does DRS have a False Positive issue?

The last post related to cricket was quite a while ago (that the Indian cricket team has been repeatedly thrashed since then is a mere coincidence). This post focuses again on the Decision Review System (DRS), a technology-aided analytical decision-support system to aid cricket umpires. The toolkit includes a set of multiple video cameras,  heat-sensing 'hot spot' technology, and ball-tracking devices that record the point of impact, as well as an additional set of predictive algorithms to forecast the counterfactual trajectory of the cricket ball (you can be forecasted 'out' in cricket). Despite the best efforts of cricket's custodians, considerable user unease with the DRS persists. In fact, it has been recently acknowledged that the use of the decision support system has had a significant impact on the game (user response: altering playing styles and inducing more 'OUT' decisions from umpires), something which this tab predicted a year ago.  Reasons for discomfort also include the lack of uniformity in its deployment, the incremental dollar cost of the DRS versus incremental returns, and equally importantly from a fan and player perspective, DRS reliability (both real and perceived). This post will focus on the last two issues.

The International Cricket Conference (ICC) has focused almost exclusively on improving the technology (e.g. increased number of video frames per second, etc). The main argument here is that while an improvement in the unconditional success rate for the DRS may seem impressive, it would be more helpful if statistics are calculated and presented conditional on the corresponding human decisions made. Toward this, let's look this MBA-ish 2x2 decision matrix (sorry). Strictly speaking, the terms 'correct' and 'incorrect' in the matrix mean 'almost surely correct' and 'almost surely incorrect', respectively .

1. The ICC has a wonderful set of umpires in their 'elite panel' that referee the most important inter-nation test matches (these elite umpires are a scarce resource, and their globe-trotting schedule optimization is yet another operations research problem - perhaps a good topic for part-8 of this series). Prior to the DRS, the umpires achieved a respectable success rate of more than 90%. Consequently in such situations, the DRS getting it right is a relatively uninteresting event. This situation is denoted as the neutral zone (top-left box). Therefore the focus is on the remaining 7-10% of the time when the decisions are contentious.

2. Clearly the case where the umpire is wrong and the DRS is right (as judged by video and predicted-trajectory evidence) is a win-win for the DRS and players. This is the green-zone (bottom left) and appears to be the exclusive area of ICC's focus as far as technological improvements. However, it is not necessarily desirable to accord top priority to the goal of achieving further improvements in this statistic.

3. The problems arise when the DRS occasionally produces visibly and audibly confounding results. This is represented by the top-right box, the 'high conflict zone'. In some instances, it could be because of technological gaps or operator error (there was a recent example where an umpire whose sole job consisted of watching the TV replay and hitting one of two buttons managed to hit the wrong one). However, in other instances, the predictive component of the DRS that is used to probabilistically judge LBW (leg-before-wicket) 'OUT' decisions appeared to be flawed or incompatible because:

a. Greater the required length (or duration) of the predicted values, the more noisier the forecasted trajectory.
b. Lesser the observed portion of the ball trajectory available for 'training' (especially after spinning and bouncing off the cricket pitch), the less reliable the prediction.

The years of prior refereeing experience of the umpire, and other human cognitive powers that help him arrive at the decision is pitted against hardware and algorithmic prediction prowess. The challenge is to be able to be aware of the many degrees of freedom involving a rotating cricket ball in motion while also taking into account the effect of the cricket pitch and local conditions.

4. There may be rare irritable cases where despite best efforts, uncertainty prevails and both the umpire and DRS manage to get it wrong (bottom right box).

If the ICC can provide data on the frequency of observations that fall in each of these 4 boxes, we can of course calculate the conditional probability of a correct decision given the DRS response using well-known conditional probability models and compare with the corresponding results for the manual system. For example, how likely is it that the batsman is actually OUT given that the DRS overruled an umpire's original 'NOT OUT' decision? Such analyses helps figure out the impact of false positives and false negatives that comprise the conflict zone observations. In particular, the false-positive rate, i.e. the case where a batsman tests positive ('OUT') using a DRS when he is actually NOT OUT, should be minimized given the nature of this sport.

Recommendations
The biggest stumbling block appears to the the top-right box (high-conflict zone) that erodes user trust every time the DRS wrongly overrules what appears to be a sound cricketing decision by the umpire. As a priority, the ICC should isolate and eliminate those components that increases the occurrence of such situations. The likely candidates for culling will be the trajectory-predictor and existing flawed versions of 'hot spot'. These innovations should be reintroduced at a later stage only after sufficient improvements have been made (and while also keeping the resultant cost down) to ensure that the expected failure rates are well under control. Viewed from this perspective, a recent decision by the Indian cricket board to do away with the predictive component of the ball-tracking technology is actually the right one.

@dualnoise on twitter

Gender Shaping - II

This tab examined the issue of 'gender shaping' last year and we continue the discussion here. This time we analyze simple probability models related to this issue. Imagine a population in a geographical area where parents adopt a policy of 'stop having children after the first boy'. Surprisingly (or maybe not), this practice in itself cannot really 'shape' or affect the stability of the population, as neatly explained by Prof. Thomas C. Schelling in his book 'Micromotives and Macrobehavior':  no “stopping rules,” like stopping after the first boy, can affect the ultimate proportions. At the first round, half the babies will be boys. At the second round, only half the families have children, but they will be half boys. The half with only girls will proceed to the third round and again, by the 50–50 hypothesis, half will have boys and half girls. If at each round half are boys and half girls the total—no matter where it stops—will be half boys and half girls. (A corollary is that we know, without adding, how many children will be born. In the end, every family will have one boy; girls will equal boys; and, the average will be two children per family.)

Dr. Schelling also mentions: "It has occasionally been proposed that this motivation might explain a slight excess of boys over girls in some populations. Where female infanticide is practiced it is bound to have that result."


Thus when one sees F-M ratios like 89:100 in some pockets of Northern India, it's a scary indicator that a sizable percentage of baby girls have been murdered (the Gov of India has had in place a strict ban on sex-determination tests for many years now). Female infanticide is a relatively recent phenomenon in certain sections of society within India's 7000+ year culture where women were typically accorded an equal (perhaps higher) status compared to men. Russel Ackoff has discussed a related issue in his classic book many decades ago.

Although the boy-driven stopping rule does not affect the stability of the population and the resultant average family looks pretty normal, the internal distribution is asymmetric (another example of the flaw of averages?). For example, a boy will either be the only kid or the youngest kid in the family. In the latter case, the parents are 'focused' on producing a boy and then tending to his needs and thus more likely to ignore the needs of their girl babies, and as the family gets bigger, this situation, on a per-capita basis is likely to get worse. These conclusions are largely confirmed in a recent NBER econometric/statistical study that uses data-driven analytical models to answer the question "Are boys and girls treated differently". Girls brought up to adulthood in such a biased environment may well help perpetuate this vicious cycle in certain parts of India. The U.S. does not appear to suffer from the problem of gender-shaping, although the pro-abortion groups have required some deft arguments to enunciate their stance on the selective gender-based abortion question posed by anti-abortionists. On the other hand, there may be some issues to be overcome with respect to investments in girl children as far as their career choices, as very briefly touched upon in a prior post.

The King and the Vampire

Read this Wikipedia entry if possible to enjoy the format of this 'fun' post a bit more.

(pic source link: Wikipedia)

Every Indian child has grown up listening to the stories of King Vikram and the Vetaal (some kind of vampire spirit who  often clambers up a drumstick tree). It used to be particularly exciting to read these tales in the children's magazine Chandamama, where the first paragraph went something like this:

Dark was the night and weird the atmosphere. It rained from time to time. Eerie laughter of ghosts rose above the moaning of jackals. Flashes of lightning revealed fearful faces. But King Vikram did not swerve. He climbed the ancient tree once again and brought the corpse down. With the corpse lying astride on his shoulder, he began crossing the desolate cremation ground. "O King, it seems that you are firm about the decision you've taken. But it is better for you to know that there are situations where an O.R decision optimization project invariably results in complaints, which apparently requires another O.R project to fix! Let me cite an instance. Pay your attention to my narration. That might bring you some relief as you trudge along," said the vampire possessing the corpse. 

The OR vampire went on:
Years ago in a bankruptcy protected U.S airline in a windy city, a well-paid MBA consultant for the Onboard Services department (OS) approached our OR team to pitch a new R&D project to manage an inventory problem on a network. Apparently, OS was hit by a surge of complaints in recent times that contractually purchased hotel room inventory in several U.S cities served by the airline were left puzzlingly and 'dangerously underutilized' in the last few months, way off their usual levels. Could we help match supply and demand using our OR bag of tricks by moving things around in some optimal manner?

No, ..These complaints were not coming from Flight-Attendants (FAs), but from management folks in OS. If anything, the FAs were happier and chatty about the quality time they were spending with family and kids. FA's don't make the kind of money that pilots do but since there's roughly about 2-3 FAs for every pilot, he wondered if our team's OR-based crew scheduling system was giving away expensive 'happy hours' at company expense? .. yes, this problem started 3 months ago, How did we know? ....

It wasn't a guess. We deployed a shiny new optimization system for planning monthly crew schedules for OS just 4 months ago. Things were not looking good. Where did we screw up? We investigated the reasons for this and within a couple of days found the answer that had the entire team laughing and celebrating. We gave the consultant a brief answer that he was satisfied with. The 'network imbalance' project was shelved.

So tell me King Vikram, what do u think happened and why did my team laugh and celebrate? Answer me if you can. Should you keep mum though you may know the answers, your head would roll off your shoulders!"

Forthwith King Vikram replied: "Vetaal, this is one of your easier ones. The answer is in three parts.

1. A significant portion of the senior FA population were married women who were happy because they got to spend more weeknights at home. Their work-hours per week is upper-bounded by federal regulations and remains fairly constant if optimized well enough, which must mean that these FAs were spending a lesser proportion of time away from home than ever before while still making the same kind of money.

2. Since FAs don't get paid as much as pilots, a relatively expensive portion of their schedules is likely to be the hotel room and transportation costs associated with their overnight layovers. I suspect that the new algorithms in the scheduling system managed to uncover improved schedule patterns among those trillion trillion possibilities by identifying near-optimal daytime airport connections that yield a denser work-day in tandem with a shorter TSP sub-tour traveling pattern that brings them back home more frequently. Doing so must have also maintained or slightly improved the weekly productivity levels (otherwise management would not have bought into this model in the first place).

3. This result is a win-win for all stakeholders once the longer-term agreements with hotel chains are favorably renegotiated to sync with this newly realized reality. This is precisely what you must have told the consultant. Since all this was accomplished without additional capital investment using OR, 'The Science of Better', your team probably felt that their algorithm's practical effectiveness was validated by this 'complaint'.

No sooner had King Vikram concluded his answer than the vampire, along with the corpse, gave him the slip.

(pic source link: Chandamama.com)

Book review: Choke

This post reviews Sian Beilock's recent book:  
"Choke: What the Secrets of the Brain Reveal About Getting It Right When You Have To"  from an O.R. perspective, as well as from the p.o.v of Dharmic philosophy that has some deep connections to some of the mind-training techniques mentioned in the book.

Scholastic/Intellectual test situations
In addition to aspiring sport stars and business leaders who certainly want to avoid 'choking' at any cost, this book can be particularly useful to students who plan to take competitive scholastic tests. Beilock characterizes 'choking' as suboptimal performance, which implies the existence of a clearly superior level that becomes feasible via practical mind-training techniques. When it comes to tests like SAT and GRE, 'worry' can negatively affect the parts of the brain that are most involved ("working memory" in the prefrontal cortex) in the Q&A process and this can directly result in choking due to a suboptimal allocation of brain power. In fact when constrained by 'worry', lab experiments show that smarter students who routinely ace practice tests are likely to drop to a more seriously suboptimal level relative to 'average' students who face a similar worry. In particular, the book presents evidence that shows that the effect of negative gender stereotyping (e.g. "girls can't do math") has been devastating in the US, inducing a lot of female exam takers to 'choke' in such situations. Subsequently, many of these candidates reconsider their original choice of a STEM career. The author presents a systematic rebuttal of Larry Summers' controversial gender-related remarks in Harvard a few years ago that looks compelling.

An important technique that is proven to minimize the chances of choking during intense time-constrained testing situations is the ancient Indian method of Yoga and meditation that is freely available to anybody (Vipasana in particular, is recommended by the author. Even three months of adopting such methods are known to have beneficial effects). Now if one were to, over an extended period of time, move along this positive Yogic meditation gradient to maximize its benefits, one can practically experience higher states of consciousness and self-realization. This is a central truth-claim of the Dharmic thought system (DTS) of India. The 2011 book 'Being Different' by Rajiv Malhotra is a scholarly and well-researched book that expounds on DTS and is particularly useful for western minds that seek to understand what Yoga and Sanskrit (the language of Yoga) truly mean.

Sports  
Finely honed motor-skills and fluid movements are critical to achieving optimal performance. Here, one can think of the task of winning a contest as constantly solving two nested decision optimization problems. The meta-problem is to manage tactics and overall strategy, while the inner problem is how best to 'operationalize' the chosen objectives in real-time. A conclusion in this book is that one must certainly think about the meta ("what") problem using working memory. On the other hand, it is better not to (like Yogi Berra said) intellectually analyze the "how" part where a player makes real-time play decisions and executes a sequence of precise movements since these have been optimized (objectified?) over years of careful practice and then 'outsourced' to the brain's 'procedural memory'. It's like trying to analyze your legs as you descend a staircase in a hurry.

When it comes to crunch free-throws in basketball, it appears that an important 'choke' statistic is the conditional probability that a player will make the shot given that his/her team is one point behind. Apparently, this conditional probability differs by about 7% on average from its unconditional counterpart. As far as crunch-time soccer penalty kicks, well-established European league stars are more likely to choke and have a success rate of 65%, which is much less than future stars, whose conversion rate was above 90%. In baseball, home teams that are a game away from winning a series, win that game only about 38% of the time. Clearly, heightened expectations from supporters increases the chances of choking.

 

A useful point to remember that will help minimize the chances of suboptimal performance in any situation is present in a Sanksrit Mantra that was uttered after what can be viewed as the world's first ever choke, when Arjuna, the hero of the Mahabharatha, on the eve of battle, is consumed by self-doubt and initially decides against fighting the good fight and plans on simply walking away, before Krishna who was selected by Arjuna to be his charioteer in this battle, reminds him of his Dharma (a Sanskrit untranslatable, roughly means 'fundamental duty') and says, among other things:  

 

Karmanyeva adhikaraste ma phaleshu kadachana
Ma karmaphalahetur bhurma te sangostvakarmani.


"Your attention must be directed toward the action alone, never with its fruits. Let not the fruits of action be your motive, neither should you be inclined toward inaction".

As we can see, even heroes can choke, but the truly great ones have a reliable 'corner man' like support system that helps them find a way to turn it around.

 

[update: fixed format]

A Working Multicultural Model: Necessary and Sufficient Conditions

Happy new-ish year. After five iterations, hopefully Analytics and OR folks are moving along a steep and positive gradient toward achieving their 2012 resolutions! If not, apply corrections to get back on track (taking into account the leap year factor).

A 2012 goal for this tab is to explore the human element in OR/Analytics practice. The OR and (applied) applied math workplace is an increasingly multicultural one. There is an increasing exchange of skilled people between countries due to globalization. Even today, many new immigrants and foreign workers continue to be flummoxed by the myriad of seemingly strange local customs, unwritten laws, etc. that confront them upon arriving at the host workplace. These differences result in a special kind of anxiety for the entrant, and to a certain extent, to his/her host, as the two parties seek a working equilibrium to get the job done on time.The challenge for people in such a workplace is to be conscious of and recognize the prevailing cultural differences (including those that we personally judge as 'unpleasant') in an impartial manner, while also embracing the mutually beneficial and useful commonality across cultures. Blindly resolving these differences in favor of either the host's belief system or the entrant's only increases this 'anxiety' and leads to increased stress in the workplace, which can then result in a drop in productivity and morale. Clearly, there has to be a better way to make this work for everybody (and not just a vocal majority).

What are some of the necessary and sufficient conditions that must be satisfied by a healthy, working multicultural model (MCM)? A key-phrase in the corporate and university workplace-playbook is 'zero-tolerance' for discrimination based on a variety of factors such as gender, race, etc. However, this only represents a bare minimum requirement. In the pan-math community, we find pure-math types who can barely tolerate applied math types, or the other way around. In the ORMS world, we will find a few academicians who tolerate what practitioners do, and vice-versa. In the tech work-place, we can spot some science PhDs tolerating engineers who in turn tolerate off-shore developers, and managers who are trying hard to tolerate these PhD scientists, and so on. Putting these people to work together on an high-profile project can be disastrous. 'Tolerance' is merely a necessary condition for a working MCM, but is nowhere close to being sufficient.

The ideas in this post are motivated by the writings of Rajiv Malhotra, a successful (now retired) Indian-American tech entrepreneur based in New Jersey, USA. A fundamental point raised by Rajiv (in the context of inter-faith dialog) is that mere tolerance is insufficient. A key component of the ‘sufficiency conditions’ is mutual respect. Let’s see how this works.

Mutual respect in the workplace already implies the necessary condition of zero-tolerance for discrimination. It then says something stronger: equality does not mean “being the same” or being “western” in thought, dress sense, and food habits. It is not a vector comparison. Two people can be equal and yet very different, like woman and man. If people behaved and responded in a homogenous fashion, there would be little need for revenue management or indeed, analytics. Anyone who believes that it is sufficient to tolerate a colleague who is 'different' should try saying it to that person and stick around for the reaction.

Mutual respect says: I don’t patronize you by tolerating you, I genuinely respect your right to your cultural and religious beliefs, some of which I clearly recognize as being very different from mine, and at the same time, I expect the same level of respect from you for my beliefs; you may well feel your way is “better for you”, and that’s cool with me as long as you don’t bug me to join your 'better' cause since I’m quite happy where I am. In OR lingo, a workplace characterized by mutual respect functions like a ‘KKT point’; expecting something more than mutual respect also creates conflict. Stress due to the invisible and unspoken 'peer pressure to conform' is sometimes an effect of working in an atmosphere (be it a high school classroom or office space) where mere tolerance prevails at the expense of mutual respect.

All this may seem obvious, but 'implementing mutual respect' is not always easy. In the original instance, Rajiv Malhotra tried to replace the much-venerated but ultimately trite phrase “religious tolerance” with "mutual respect for others religious beliefs" within the text of grand inter-faith declarations. The results were quite interesting. To merely tolerate our co-worker's religious beliefs, gender, race, and sexual orientation is to feed a hypocritical feeling of superiority that is likely to manifest itself in our professional relationship with that person at some point in time. A tolerance-based approach works well for finding practical solutions to numerical math problems, but for human relationships, mutual respect is vital. Nothing more, nothing less.



This first post of 2012 is humbly dedicated to Sri Rajiv Malhotra. Thanks, Rajiv ji.

Solver precision: a consumer perspective

This is a quick post motivated by a useful question posed in this nice blog on OR software that wondered about the need for so many decimal-points of precision in commercial solvers. As Prof. Paul Rubin touched upon in his brief response, there's always going to be a few numerically-unstable instances that may justify this level of precision. The question as well as the response was quite instructive and this post mostly adds context.

Speaking from the perspective of a consumer who deploys  such solvers, this quest for precision is not just an academic exercise. Ill-conditioned instances are inevitable in certain business situations and are not (yet) rare. A customer (e.g. a store manager using an algorithmic pricing software product) routinely stress tests their newly-purchased/updated decision-support system that has such a solver hidden inside it. Customers will sometimes specify extreme input values to gain a 'human feel' for the responsiveness of the product that their management asked them to use. In fact, even routine instances can occasionally defeat the best of data-driven scaling strategies, and the old nemesis, degeneracy, always lurks in ambush.

Such solvers also have to be robust enough to work 'off the box' for millions of varied instances (to the extent possible) across industries and changing business models within any given industry. Being 'optimally precise' may pay off in terms of reduced support and maintenance costs for the vendor who writes the solver code, as well as for the consumer who deploys it, and less headaches for the end-user, the customer.

With the information available in journals and the Internet, it is realistically possible for a DIY practitioner to assemble a reasonably fast and robust solver to handle their own company's LPs, but the task of building high-precision, enterprise-level MIP solvers is best left to the specialists.

OR models for discouraging criminal intent

Dr. Subramaniam Swamy, the brilliant lawyer who exposed the 2G scam in India is trying to raise awareness about this issue amongst the Indian public via a series of talks around the country. In one of his talks, he white-boards a simple but useful high-level model (shown below) to determine the level of financial penalty that should be imposed to deter future scams. This is especially important in the case of crooked politicians who tend to be thick-skinned and are willing to ride out their years in jail in order to enjoy their ill-gotten stash after 'serving out their term'. Conditioning on the chances of getting caught (p),

E[reward] = (1-p)R - p.D

where R = reward from the scam, and D = penalty to be paid if you are caught (primary decision variable). Swamy's point was that, in the Indian context, even though 'p' is relatively small in value for various reasons, all is not lost if 'D' can be made sufficiently large (proportional to 'R' times the odds of evasion) to ensure that the LHS value is unattractive enough.

Let's apply this model to the roads of India, where traffic violations are the norm. A given O-D (origin-destination) path is formed by several links, where link (i) is associated with a probability p(i), reward R(i), and penalty D(i). Crooks try to find the path of least resistance, e.g, smallest cumulative 'p' or max cumulative E[reward]. The police can counter this by a solving p-median type problem (this is a different 'p') where they can optimally position their scarce resource (traffic cops) to maximize an aggregate measure of expected penalty based on link traffic volumes. Given budget restrictions, these scarce resources have become even more scarce. However, it appears that in many other parts of the world, police departments have been smart enough to create a multiplier effect via an 'illusion of ubiquity' achieved via a 'ghost archetype' that periodically and randomly enforces the law in prominent locations in a particularly visible and pitiless manner. Recognizing the 'human element', in this case, the nonlinear 'customer response' to certain deployment scenarios can lead to a solution that increases the perceived probability p(i) for certain key links in the transportation network (beyond its actual statistical rate) without increasing actual capacity. Similarly, the presence of crooked 'bribe friendly' cops at busy intersections can lead to a nonlinear drop in public trust and perceived p(i), regardless of an increase in overall capacity.

To summarize, OR based decision support models can be effective in making a dent in corruption via analytically driven decisions that help maximize the perceived penalty for criminal/corrupt acts that in turn, leads to an actual incremental reduction in the relevant crime/scam rate, despite a scarcity of resources.

American Airlines Chapter 11: An OR Opportunity within a crisis

The news of American Airlines' Chapter11 may sadden some members of the OR community given their pioneering work in revenue management apart from their amazing impact on the overall ORMS practice in the airline industry. However, this crisis is also an opportunity for O.R. The company will be taking a close look at their business model as well as their more tactical operations and ring in a chain of meaningful improvements. Speaking from a similar 'chapter 11' experience during the last decade, this filing represents an opportunity for OR practitioners that must be grabbed. This situation highlights what this tab has talked about before: having a well trained ORMS team with domain expertise is invaluable and i'm sure AA has retained a lot of their experts.

Specific example
The renegotiation of the existing collective bargaining agreements (CBAs) with various unions is a great application example that can generate significant 'true dollar' returns. OR can be gainfully used to analyze rule changes that significantly improve efficiency while also improving the quality of work life of stakeholders to produce win-win deals. During 2003-2006, OR folks at a similar legacy US carrier were able to quantify and successfully redefine a set of highly complex work rules that ensured better utilization and compensation without sacrificing quality of work life. What's more, such feedback can help prevent CBA negotiations from stalling and win some trust from both sides of the table. In such situations, the management is likely to be more flexible in 'opening up' old rules, allowing the full use of powerful solvers and large-scale optimization models to determine the maximum level of improvement possible by replacing such legacy constraints with more sensible ones. Every  (deterministic) dollar saved during such stressful times is precious and is highly appreciated. In short, Chapter-11 is a time when OR folks on the ground can make their presence felt and directly contribute to the bottom-line. A friend in need is OR indeed.

update: some typos fixed

The best solver award in a decision support role goes to ..

Major ORMS conferences typically coincide with new releases of existing commercial optimization software products like CPLEX and Gurobi, as well as the introduction of new ones. In the last few days, we have seen the entry of an exciting new solver product, Sulum Optimization. Dr.Bixby's eagerly awaited updates on the state of the solver universe speak of truly breathtaking improvements. So how important are such off-the-shelf solvers in practice?

A complementary 'state of the union' question that is worth asking is 'How much progress has been achieved by humans as far as analyzing decision problem formulations in practice ?' While glancing through the journal papers in the last three decades and comparing the work with the approaches taken by researchers in the 1940s-1970s, I couldn't help but feel that there is a non-improvement, perhaps even a retrogression along this dimension. It's tough to quantify the answer, but we can try to describe reasonable boundary conditions.

1. A terrible formulation is one which cannot be readily analyzed to determine an acceptable solution to the original business problem. This is not the same as 'finding a feasible solution to the mathematical optimization model', although these questions are somewhat related. Yet, a whole lot more time and publicity is directed toward the latter question. Apparently quite a few MI-Hard (mission impossibly hard) problems have been discovered out there, especially in the last three decades. These instances are so mysterious that even an acceptable solution is elusive despite the obviously massive progress in solvers and hardware. What does this tell us? An acceptable solution is either already available or can be found using OR / business insight. I certainly haven't yet come across such a MI-Hard instance across multiple industries.

2. A viable formulation is one which you can analyze to find an excellent answer to the original problem by partial or complete enumeration, within a reasonable amount of time. In other words, you are doing your job as a practitioner well if your design simply avoids crappy solutions to the original problem, leaving you with the task of scanning just the few remaining good ones. This process is merely a refinement of the 'acceptability analysis' in (1) (Watson would ask what is 'constraint programming' ?). Not only is the process of being a 'human solver' quite enjoyable, it also goes a long way in convincing your employer and a customer that a competitor cannot simply buy their own solver and achieve parity. Plus it builds street-cred for you and OR. On the other hand, a few journals love to have MI-Hard problems subjected to 'shock and awe' within their pages.

Summary
There may be rare exploratory formulations that require the full power of such solvers to generate insight when very little is practically known about the original problem. In general, solvers are useful in practice like health insurance is useful in health care. Some feel that buying the best or most expensive health insurance will somehow translate into an equivalent improvement and stability in our health, forgetting that fundamental choices like exercise, lifestyle, and diet are far more important factors. In fact, if we find that we are using our health insurance a lot, it is all the more important to question those fundamental choices.

'Which is the best solver today' is a interesting question, but the best decision model that you build will be one that most certainly does not depend on the answer.

Long-distance convergence

The first picture tracks the achieved percentage reduction in a certain minimization objective function value (a shortest path distance) relative to it's initial value, over time.

Not monotone convergence, but still pretty good, and the relative gap finally goes close enough to zero (within a tolerance of 0.5%). Most would be happy to see this solution performance on any O.R decision problem instance in practice.

The next picture tracks the raw values corresponding to the first plot - the shortest path in miles, between the location of my ORMS job and that of my wife's (non ORMS job). The time scale is in years. This also happens to be the commute distance (logarithmic scale).

Average convergence rate = 581 miles/year
Total cost incurred = 27,500 mile-years (counting from year "-2")

Sometimes, superlinear convergence feels terribly slow, but in this era of labor restrictions, we'll chalk this down in the 'wins' column.

Jumbo decision models to protect the environment

As the population increase in India leads to scarce resources becoming scarcer, villagers in rural India increasingly encroach on jungle areas and vice-versa. In Orissa, the government has decided to take the help of elephants to manage this conflict.

This is a true story.


These magnificent, emotional multi-tuskers with a long trunk and an even longer memory, are much loved and venerated in India. Loved this particular song sequence as a kid.




Elephants require relatively larger habitats to survive, and in recent times, we increasingly hear of elephants and other wild animals in India going on the rampage among civilian populations located close to their territory.

To tackle this problem, the government of Orissa (a beautiful, culturally rich state in eastern India) came up with a novel control method based on self-governance: train 50 Col. Hathis and position them at vantage points. These smart jumbos serve dual purposes:

Online: actively discourage militant pachyderms from venturing too far out

Offline: speed up the learning curve for newbie wild elephants undergoing training.

An initial pilot has been successful.  Read this brief but amazing report for the real costs involved, benefits that can be realized, and the encouraging preliminary results.An interesting O.R. challenge is to maximize the effectiveness of this method without adding additional capital expenses. How should the forest officers position these limited number of smart elephants to maximize their effectiveness in controlling the herds? For example: given p 'Kunki' elephants, we can determine an optimal positioning of these elephants by solving the corresponding p-median like location-allocation problem to better control intrusions, cover more (convex?) territory, or utilize fewer Kunkis to effectively accomplish the same task.

Is this a first example of how OR and elephants can combine to help protect the environment?

Credits

A Jumbo-sized thanks to the brilliant and multi-talented Vijayendra Mohanty for inspiring this post.

This post is humbly dedicated to Shehla Masood (1973-2011).

How long is a game of snakes and ladders?

The detailed answer can be found here. You can stop right now or roll the dice and play on ...

The game originated in India more than 800 years ago and is still popular there. Other board games (Chaturangam or chess, and Pachisi or Ludo) also originated here, and a future post will explore the familiar stochastic OR topic of 'a gambler's ruin' in ancient India. Here's a picture of a native SNL board. The original Indian name of the SNL game translates to 'the path to salvation' and was supposed to be morally educational as well as enjoyable for kids. It's actually pretty profound.

From an Operations Research perspective, the game can be modeled as a Markov Chain. The moral lessons for kids in the Markovian property of SNL seems to be that no matter how terrible a path you took to get to a certain point, you retain the same possibility of salvation by consistently performing good deeds. Note the absence of any non-Markovian historical baggage of original sin. Similarly, a lifetime of virtuousness can be temporarily undone by a single big act of indiscretion that can literally bring you back to square one. As kids, we always felt nervous about the long snake lurking around the 99th square waiting to yank us down.

Per the paper (linked above) published in 1993, simulations indicated that the average number of moves for a 10X10 square game of SNL was around 39. More precisely, using the Markov Chain state transition equations, the authors (Althoen, King, and Schilling) calculate the exact expected number of moves in the "Milton Bradley version of Chutes and Ladders" to be equal to this impressive but twitter-unfriendly ratio:

225837582538403273407117496273279920181931269186581786048583
5757472998140039232950575874628786131130999406013041613400

or approximately 39.2. Other interesting results based on a sensitivity analysis of this value wrt adding or dropping snakes and/or ladders include:
- a six-sided die based game of SNL with no snakes or ladders lasts around 33 moves on average. A unit snake seemingly prolongs the game more than a ladder can speed it up. I felt that pretty acutely as a kid. Yet again, in true Steve Jobsian fashion (or maybe not), it turns out that the seemingly idle SNL time in Bangalore, India was a solid foundation for a career in O.R practice.

Anatomy of a scam

Once, even twice is a coincidence. But three is a pattern worthy of a second look.

Exhibit 1: The financial monoliths that rode the cash wave in an ocean of American tax payer money have pretty much gotten away scot-free. Their criminal greed has been marketed as a simple combination of market upredictability, non-robust math models, and corporate irresponsibility.

Exhibit 2: The response from the Pakistani government after the double-tap delivered to Osama Bin Laden a few hundred yards away from their West Point, was to admit 'gross incompetence' rather than confess to any willing participation in hiding a notorious fugitive. No punishment and continued pouring of billions of dollars down the drain. They happily take out a full page Ad in the Wall Street Journal on the 11th of this month to celebrate.

Exhibit 3: The government of India is for all practical purposes run by the Darth Vader-like Italian-born Sonia Maino, who has propped up an equally complicit 80+ year old mute puppet as the prime minister to take the heat. The current regime that has ruled India for 50 of its 60-odd post-independence years is neck deep in a series of corruption scandals and midnight arrests of peaceful anti-corruption activists. The most blatant of these is the so-called '2G scam', where billions of dollars (1.86 trillion ₹) worth of public money in form of lucrative bandwidth was all but given away to friends and family. Only the most junior ministers (belonging to the coalition-party :) are in jail. Their defense is rather innovative but inevitably based on this same theme - 'negligence' and 'uncertainty', rather than admitting to any criminal wrong-doing or fraud.

Case 3 is an interesting example. This tab has already touched upon it twice before and arguments outlined turned out to be in line with what the Harvard-affiliated anti-corruption lawyer Dr. Subramanyam Swami used in his own article to describe the reasons for the mess.

The defense in all three examples of colossal fraud essentially argue that they merely maintained the 'status quo', claiming ignorance of the true value of doing the (obviously) right thing. Their second line of attack is to plead down the severity of the charge all the way to a misdemeanor. In exhibit 3, this is being done along the following flimsy lines "since the true value of the resource can only be determined if an auction had actually taken place, the figures quoted are cooked up by vested interests". Two factors go against such an argument:

1. This figure was calculated by a government agency (!) - the Comptroller and Auditor General (CAG).

2. Unless the CAG has performed a rigorous math-based analysis and run simulations to determine the maximal revenue obtainable from selling a scarce resource in a gigantic market like India, the quoted figure that was based on an average or a reasonable auction scenario is more likely to be a lower bound on the true cost of the swindle.

How dependable are 'opportunity cost', and more generally such "if" based decision models? A paper that I co-authored as a student of civil engineering many years ago happens to be based on this idea and was used in highway resource planning in Virginia. Often times, business value of an analytics idea can only be viably demonstrated by calculating 'what would have happened to a set of past outcomes had this OR method been used instead". On the other hand, if a researcher were to build up a ladder that consists of several degrees of conditional dependence to arrive at a final value, then such chain-of-events driven claims have to closely scrutinized to ensure that we simply do not end up with 'noise'.