Inverse Rule of Project Timelines

Over the last decade and half, I've participated in a variety of internal and external commercial OR projects across multiple industries, many of which involved competitive bids. These projects somehow always ended up being one of two types - either long and routine, or interesting but cruelly short. Every time I came across that exciting project full of nice OR work, the deadlines were killing. The duration of the project/pilot/proof-of-concept appeared to be inversely proportional to the degree-of-sophistication. It seemed quite puzzling at first, but there are some plausible explanations for it, and perhaps this phenomenon shows up in other STEM-area projects too.

If the project isn't novel, and requires some reinventing of the wheel, it's considered low-risk and delegated to the Rodney Dangerfields in the trenches. If it turns out to be something new and shiny, senior pros are brought in to unleash their deadly math modeling dance moves on the client: a bewildering Bangra of reformulations and theorems, culminating in the East Coast Shuffle: the final formulation will always be solvable to optimality as a DP (thanks to a west coast friend for this discovery). A final spin through OR-FX chartware, and the gobsmacked customer is humbled into signing, provided the price is right, and of course, resistance to publication by any journal is futile. Problem is, the senior pro clock is relatively expensive. To keep the bid competitive, the total cost is treated like a knapsack constraint, which makes total time the casualty.

Result? like cricket matches that end in a draw after five days, lets just say that OR is the winner here.

(Written in jest, and any resemblance to real for-profit firms is not just coincidental but highly unlikely given the suboptimality of the inverse rule)

Industrial Applications of Analytics/OR at INFORMS 2013

I will be presenting three practice talks around the theme of 'industrial applications of analytics and OR' at the INFORMS annual conference, 2013. Each of them involve some type of optimization; each one is a different context - energy, fashion retail, e-commerce; each one a different setting (product, service, decision support tool) having varying client objectives and requirements.

3 - The core decision optimization problem turned out to be a discrete nonlinear formulation, and in each case, solved with the help of CPLEX after reformulations and/or decomposition.

2 - of the more challenging decision problems will be analyzed using results on real client data.

1 - of these solutions, apparently, was turned into a commercial product a while ago.

0 - number of theorems proved. Left to the journal paper and smarter co-authors.


Monday 8 - 9:30 am: Real-time personalized deals

New Directions in Pricing and Revenue Management)

Tuesday 8 - 9:30 am: Pre-pack optimization in Fashion Retail
Theory and Practice in Retail

Tuesday 11 - 12:30 pm: Dynamic pricing in a Smart-Grid
Topics in Dynamic Pricing and Mechanism Design

Gandhi and Operations Research

October 2nd is the birthday of Mahatma Gandhi, a major spiritual force behind the Indian freedom movement of the 20th century. Gandhi-ji also was a fundamental and direct inspiration for Martin Luther King Jr.'s civil rights movement of the 1960s, and Nelson Mandela's struggle against apartheid. In this post, we attempt to examine his idea of ahimsa from an optimization perspective.

Update (Oct 5): This Huffington Post article provides amazing insight into Gandhi's ideas.

What is ahimsa?
Indian textbooks mention that Gandhiji brought the colonial empire in India to its knees by using ahimsa and sathyagraha (both were 'spelling bee' words a couple of years ago). These words have no equivalent in English, and are often used to imply "passive resistance", "pacifism", or "non-violence". A mathematical optimization model provides a more useful translation.

The popular Sanskrit verses on himsa and ahimsa given below was popularized by Gandhiji:
ahimsa paramo dharmaha,
dharma himsa tathaiva cha
[Oct 2018 update: the second verse has been attributed to Swami Chinmayananda)

My translation:
Non-harming is the greatest virtue;
So too is righteous harm.

The second line suggests that allowing cruelty to go unchallenged is equivalent to willingly permitting harm, and therefore, must be resisted. The verses are a combination of the ideal (global optimality = zero harm), and a context-dependent violation of that ideal (soft rule = minimize harm). 'Local harming' is permissible in rare circumstances when it results in an overall reduction in global harm. The gangrenous foot has to be amputated to save the body, or a terrorist who attacks innocents in a mall or a school has to be taken down by security forces. In a recent talk, Narendra Modi tells us a story of how Gandhi would request his assistant at Sabarmati Ashram to pour back half a cup of water back into the river, because all he wanted was half a cup. Minimal harm!

(updated October 2)
Optimization Model of Ahimsa
From an optimization modeling perspective, these ahimsa verses represents an objective function of minimizing harm. In normal circumstances, the optimal value should be zero, but in all circumstances, it should be minimal. When some non-zero harm is inevitable, the goal is to limit the total harm to a minimum, i.e., the employed level of harm is optimal if and only if it is necessary and sufficient to restore dharma. The 'necessary' condition implies minimalism of the counteracting harm, while the 'sufficient' condition implies the safe neutralization of the source of the harm. It's a tough balancing act for humans even though nature itself effortlessly adheres to Newton's third law. A pure hard-constraint version of ahimsa would discourage self-defense and even celebrate cowardice, while a pure soft constraint version could open the doors to unnecessary use of force, and justifying cost versus benefit approaches. (The legal system dictum of "let a hundred guilty go unpunished, but a single innocent should not be wrongly convicted" is an interesting case study in this regard.) Hence, applying any one of these two lines is an incomplete specification and can lead to unpredictable results.

We argued a while ago that these verses are an improved 'fail-safe' choice for the 'zeroth law' of robotics. In the real world, when we build decision models to aid decision making, we can optimize decision variables to pick a pareto-optimal solution that also results in the least disruption to the system ("don't fix what isn't broken"). For example, if we are scheduling workers to maximize efficiency or minimizing cost, then an optimal solution that also minimally disrupts (and preferably, enhances) their quality-of-work-life is more likely to be sustainable over the long run.

Gandhiji's Swaraj
Many feel that Gandhiji was partial to the first line, and quotes attributed to him support this claim. On the other hand, Gandhi's 'Hind Swaraj' and his lesser known quotes on preferring violent self-defense to cowardly capitulation suggests that he was aware of both verses. His book 'Hind Swaraj' (Indian self-rule) implies that his primary objective was not merely an overthrow of colonizers, but to achieve the strategic and deeper goal of ending the cultural genocide of India (restoring its Sanskriti and dharma). Applying the ahimsa verses would yield a path to Swaraj that results in minimal incremental harm to India's Sanskriti and dharma. Such a path may not necessarily also be optimal in terms of being the shortest-time path, or the least painful, or one that maximizes regained territory.

Finding an Optimal Meeting Location

I encountered a neat version of this problem last week at work, while folks were trying to schedule a meeting with a client.

Decisions, Decisions. Location, Location, Location. Where do we meet?

Problem Statement

There are Wij project team members located at office O(i), i = 1, ..., M, that have skill sets j = 1, .., N. Each office location is staffed by a workers having different skill-sets and job responsibilities, such as research, software development, pre-sales, analytical services, etc. It is preferable that everybody attends, but to achieve a quorum and a productive meeting, at least Q(i) persons from O(i), and at least S(j) persons of skill-set j must be present. Assume that the unit travel expense T is roughly the cost of a round-trip air-ticket between O(i) to the airport nearest the meeting location, and that we incur a fixed, location-specific setup cost C. There are additional requirements that limit the number of feasible location choices: safety, conference-friendliness, etc.

Objective: optimally locate the meeting to minimize total cost.

Let A* be the airport associated with the optimal location.
Let x(ij) be the number of people of skill set j attending from O(i)

The problem formulation looks like this:
Minimize Sum(i, j) x(ij) T(O(i), A*) + C(A*)
sum(j) x(ij) ≥ Q(i), i = 1, ..., M
sum(i) x(ij) ≥ S(j), j = 1, ..., N
0 ≤ x(ij) ≤ Wij, x integer.
A* ∈ {commercial airports associated with feasible locations}

This resembles a capacitated location-allocation problem. If the x-variables are fixed, the formulation reduces to a pure A* location search. Similarly, if A* is fixed, the problem turns into a capacitated supply-demand problem.  If every location had exactly one skill set, then we can allocate no more than min(W, max(Q, S)) from each office, leaving us with a pure location problem. Let's assume this is indeed the case, and proceed.

If there are K feasible airports, we can compute the M travel costs, plus the setup-cost C per candidate to determine the total cost associated with a choice. After O(MK) computations in an exhaustive search, we can determine A*. But what if K is very large? We could look at this as a Weber problem and find the centroid, or, suppose we restrict our candidates to coincide with one of the office locations. This is not a terrible idea, since we can avoid paying for an external conference hall (C~0). This requires only O(M²) computations, and all team members at the optimal office location can attend.  Will the best choice from this restricted set of "extreme points" yield an optimal cost solution? In general, it is not guaranteed. If air fares to/from a particular airport (e.g. Las Vegas) is relatively low, then it may be optimal for the selected team members from every location to fly there, even if it is lies outside the convex hull of the office (airport) locations. However, if the traveling cost is a 'nice' function of distance traveled, then results from the literature can be employed to provide decision support:

Literature: Finding An Optimal Meeting Point on Road Networks
Stackoverflow discussion: "Shortest distance travel - common meeting point"

A wonderful reference book is the classic ol' textbook by R. L. Francis, et al., on Facility Layout and Location Analysis.

(pic link source: Amazon.com)

The 2013 Annual INFORMS conference is being held in Minneapolis, MN this year. Hypothermically Hypothetically, where would such a conference be located in order to minimize the total expected air travel + hotel cost of attendees (+ organization cost)? Any guesses?  If the optimal location remains static over time, a subset of attendees will end up paying a relatively higher cost, hence some rotation policy may be preferable.

Finding a location in a time-space network?

(pic link source and related blog: Planning an Annual Meeting? Location is Key!)

(A more concise version is published in the INFORMS conference blog).

Sine-Generator in the Aryabhatiya, 1500 years ago

Came across this post by Rajiv Malhotra on facebook, and am posting a screenshot.  More research and findings continue to trickle in about the discoveries and creations of ancient Indian mathematicians, and this sloka (verse) is not an isolated example. The focus of this brief post is on the design of the sloka from the data compression optimization aspect.

Brevity and conciseness was important to ancient Indian scientists and linguists for various reasons. Their success in optimally designing such slokas to be memorized by maximizing the density of information carried per unit syllable, while also (and this is important) ensuring that the sloka is logically sequenced and constructed, and relatively easy to memorize, is utterly remarkable. In particular, the affection for the minimal among those Sanskrit grammarians is legendary. There is an oft-repeated saying in ancient India that the joy experienced by a grammarian who manages to achieve a half-a-syllable reduction is only equaled by their joy upon the birth of their child. The choice of the objective function drives the design approach. In contrast with the previous example, we have the Vedic chants in Sanskrit, the world's oldest, unbroken surviving oral tradition, where redundancy was deliberately added to minimize error in oral transmission (an achievement that may have contributed toward India having the world's oldest, unbroken civilization). In this case, what was memorized and repeated was much, much longer than the original verses in order to optimize information and audio fidelity.


(Mysore is a city in Karnataka, India, whose state language is Kannada)

Update (Sept 5, 2013)
The English transcript of the sloka can be found here in the Nature Journal (thanks to Srikrishna ‏for sharing this link).

Update 1: December 15, 2013
A superb post at http://hindufocus.wordpress.com on a compressed Sanskrit verse for remembering the value of Pi to 32 decimal places.
"..... Here is an actual sutra of spiritual content, as well as secular mathematical significance.

gopi bhagya madhuvrata
srngiso dadhi sandhiga
khala jivita khatava
gala hala rasandara

..... The translation is as follows:

O Lord anointed with the yogurt of the milkmaids’ worship (Krishna), O savior of the fallen, O master of Shiva, please protect me."

Why the UPA will get re-elected in 2014: in 100 words or less

Stats indicate UPA to be the most corrupt government in Indian history, so it won't get reelected in the 2014 elections. Wrong. Here's proof.

1. Scam cash, embezzled dough, and black money is a sunk cost. Irrecoverable past. 

2. INC has turned India's voting mass into MYLOPs.

By definition, MYLOPs are Markovian; their vision of the future is independent of past events, given instant gratification. It follows from (1) and (2) that whoever supplies the biggest freebie to the voting mass now, wins. UPA just designed the free lunch, transcending the NFL theorem. 

No contest.

Notation

INC = Indian national congress, the dynastic party (ideology: Nehruvian socialism), which has wrecked India almost continuously since political independence (1947).

UPA = United Progressive Alliance = INC + clones, won the last two elections, seeks a hat-trick (= three-peat, in American).

MYLOPs = Myopic, Local Optimum seeking Pessimists. First introduced here. 

Free lunch = FSB = A grossly underfunded food security bill, which provides a theoretical guarantee of free food for all poor people, but in reality is a food bank for UPA's vote bank.

Predicting Coconuts and Baby Chickens

The next few blogs cover observations from a recent visit to India and South-east Asia.

Earlier this month, I used to wake up at dawn every day to visit the farmer's market in my ancestral town in Tamil Nadu, India to purchase fresh vegetables for salad, curry, and sambhar.

The vegetables here are sold directly by farmers, and are simply delicious. The vegetables I purchase in US groceries may look better, but in terms of variety, flavor, and cost, are no match for what is on offer here in this village market.

I was introduced to a wise and elderly person selling coconuts in his stall.

My family buys coconuts exclusively from him. Coconuts, like the cow, have a special place in Hinduism. The Coconut is like the Kalpavriksha, the giving tree, while the cow is associated with the Kamadhenu, the wish fulfilling cow. The reason, as is usual with Hinduism, is both scientific and compassionate. The sanctity of a particular place, object, person, or living being is usually tied to net benefit of the entity with respect to the cosmos. The Indian cow and the coconut tree are incredibly giving in a variety of ways throughout their lifetime, demanding little in return. Worthy of emulation and praise.

Coconuts are often used in a Pooja (as a prayer offering) at temple. Often, Indians break a coconut prior to beginning an important task, or undertaking an tough journey, or launching a new project. When used for such a purpose, it is desirable that the coconut not be tender or rotten or dry, but perfectly fresh. Breaking a bad coconut at a temple is deemed to bring ill-luck (from a scientific perspective, this act aims to turn a complacent person/group into the more alert and focused type, pre-empting any mishap with positive action. Ill-luck is most certainly avoidable). However, there is no obvious, guaranteed way to tell from an external observation whether the inside of a coconut is spoilt or not. For example, roughly 50% of the coconuts I select at the local A&P grocery store turned out to be spoilt (The degree of spoil is actually a continuous variable, but for now, we simply treat it as a binary indicator). Thus, careful attention is paid to the selection of temple coconuts.

The white turbaned coconut vendor in the picture is an expert at picking out good coconuts. He has an excellent track record. I asked him about the various factors he takes into account prior to making his selection decision. Aside from a visual inspection, he conducts a quick 'sound test' to pick a coconut. If you let him know that this coconut is destined for a temple, he picks one that informally maximizes the probability of goodness. Also, spherical coconuts are preferred to the ellipsoidal ones, since they tend to shatter quite spectacularly like grenades, emphatically warding off ill-luck :) An empirical analytical model for predicting the probability of a good coconut can be constructed using a logit (logistical) model, for example:

log(odds of a good coconut) = A0 + A1 * thickness of the shell + A2 * latent quantity of coconut water inside + A3 * shape_factor +  A4 * sound_factor ... = U

By measuring the values of the explanatory variables in the RHS and recording the outcome after breaking the coconut, we can calibrate the coefficient vector (A) using historical data (maximum likelihood estimate, for example), giving us the following probability model that predicts the goodness of a coconut:

prob (good coconut) = exp(U) / (1 + exp(U).

When we pick coconuts, our mental decision model informally estimates the RHS for a given set of coconuts and picks the one that appears to maximize the odds. During the last few years, our vendor has picked just one bad coconut. It seems he was quite distraught, and replaced the coconut free of cost.

A related, traditional prediction problem that requires specialized skills and experience, is determining the gender of a baby chicken. Multiple techniques have been employed to make this prediction. Unlike coconuts, experts here can  make a conclusive determination (probability ~ 1.0). As the book "Moonwalking with Einstein" notes: "A good chicken sexer can identify the gender of approximately 1,000 chickens an hour and much of this has to do with their expert memory of chicken private parts".

86400X speedup?

I once read a research paper that stated that their customized nonlinear solver reduced computational time for a particular problem class from days to seconds, i.e., something like an 86400X speedup. 

(pic source link: espn.go.com)

Digging a little deeper, it seems the authors did not notice prior work that solved similar sized instances of a more difficult discrete nonlinear case, using an analogous CPLEX-based approach, in a few seconds to a few hours in the worst case. Even a conservative 'from several minutes to a few seconds' mean-improvement is impressive (~100X faster). After deleting complicating side-constraints and relaxing integrality restrictions, the resulting continuous relaxation can indeed be solved really quickly compared to the original problem.

Amartya Sen recently confessed to pulling numbers out of thin air to grab people's attention, lending credence to the claims of his detractors. I hope O(claims) does not turn into a total marketing game in the future.

Exhaustive Search for #orms books in South India

Blog#2 from India.

A bookstore I've regularly visited over the last couple of decades is the 150+ year old Higginbothams on Mount Road, Madras (Chennai).

(pic source link: wikipedia)

My first ORMS textbook: 'Linear Programming and Network Flows' by Bazaraa, Jarvis, and Sherali was purchased here. In recent years, finding the latest ORMS books here has become tedious. The Chennai Metro rail construction has adversely impacted the parking area in front. Yesterday's search spanned the entire second floor, and ORMS/Business Analytics books were found in the following sections: Management (Management Science books), Operational Management (OM, Supply Chain), Statistics (a slew of Intro2ORMS books, probability models, queuing theory), Linear Algebra (Linear Programming), Computer Science (computational complexity, graph theory, combinatorics), ... Perhaps this situation is a reflection of the field of ORMS itself. It's been a multidisciplinary area since the beginning.

Sapna book house in Bangalore has a good collection of computer science oriented material.

(pic source link: images.touristlink.com)

SBH once boasted of a huge collection of technical books, and it's still a pretty decent place to look for books relating to business analytics, data mining, and machine learning.

Gangarams is another well-known book store in Bangalore.

(pic source link: dnaindia.com)

I've found very few ORMS books here in the past, and I plan to skip it this time around.

Off late, flipkart.com, the Amazon-like online bookstore offers a massive assortment of books, including ORMS titles. It ships only to Indian addresses currently, accepts credit cards, and offers free home delivery within 2-7 business days. Despite these benefits, online shopping denies one the simple joy of a leisurely enumeration search in the afternoon, wading thru stacks of old, dusty tomes in search of that one hidden gem. In a totally random location at Higginbothams was a copy of 'Optimization for Machine Learning'.

Optimizing Schedules: QWL Considerations

A first blog post from India.
Impact of Decision Variables on Humans
This practice related comment was triggered by yet another useful 'Punk Rock OR' post  - on 'optimization and unhappy truckers', which briefly reviews a Tom Vanderbilt article that noted that mathematical optimization may having contributed to the incremental unhappiness of employees who were affected by the decisions prescribed by the model. TV's article also talks about the optimization of airline crew schedules, which is a useful example to analyze some of the side-effects of optimization.

Scheduling Objectives

The rules that govern the safe scheduling of airline crews are incredibly complex, and used to appear in a bound book form (every single one must be programmed into the optimization system, scarring an Operations Researcher for life). Additionally, there are hundreds of different 'cost' components that typically go into an airline crew scheduling system that is so neatly abstracted to "Min cx. Ax=1, x binary" in OR textbooks. Some of the objectives are listed below:

1. cost, utilization, efficiency

2. quality of work life (QWL)

3. schedule regularity

4. operational resilience

5. Downstream system compatibility

.. and many more..

Among these, a component that is most relevant to the discussion here is QWL, a non-negotiable component of "soft rules" that go beyond what the FAA prescribes and diligently adheres to the letter and spirit of a collective bargaining agreement (CBA) between the management and representatives of the crews. QWL metrics are audited and checked before schedules are published, and tracked over time. A drop in QWL metrics can result in followup phone calls from crew representatives, and keeping the call volume (and decibel) to a minimum is a clear and track-able goal.

Anonymous Schedules, Personal Impacts

While traveling on company flights, I initially used to strike up a conversation with flight-attendants (FAs) to get their opinions on their schedules, and any particular issues they had. There were some harsh complaints, but also the occasional compliment based on their feedback that compared their QWL to FAs in other carriers.  Nevertheless, schedules are initially anonymous, and thus indifferent to personal needs, while also being free of privacy concerns. It is safe to say that unless schedules are personalized, there's bound to be unhappy crews. Personalization is at odds with automation, and the task of optimally synchronizing and scheduling 30, 000 FAs and pilots, and hundreds of expensive aircraft that operate thousands of flights per day, while trying to keep costs down, reliability high, and crews happy is non-trivial. Luckily, the space of feasible schedules contains many trillions of possibilities, and is diverse enough to accommodate many, many management and crew objectives to produce tons of alternative near-optimal solutions. In fact, this feature plays a vital part in designing new and improved crew safety rules during CBA negotiations. To summarize, modern, large-scale industrial optimization systems are sophisticated, robust, and flexible enough to accommodate a myriad of human-impact objectives without breaking a sweat. Who knows, truly personalized schedules that sync with personal calendars, while also keeping utilization high, may well be technically feasible now. Preferential bidding systems (PBS) have already been in place for more than a decade now.

Actions Reflect Priorities

Some of my purely personal observations based on the data I have seen: the QWL metrics for a schedule is correlated to the negotiating clout of the organization for whom the scheduling is done, and the importance given by management to maintaining harmonious relations with them. Higher up the food chain, the better the QWL. Not surprisingly, some employee organizations may have their own optimization systems that enable them to evaluate their schedules (and also 'game' the system). 

In between the scheduler and the 'schedulee' is the OR layer, the secret sauce. I'd like to believe that OR'ers can make and have made a positive difference by paying attention to the net human impact of a binary variable changing from a 0 to 1 to find win-win stakeholder-friendly alternative optima. I've seen analysts devote many days trying to figure out how to make excruciatingly complex experimental QWL constraints work cost-effectively in the optimization system to break an ongoing CBA negotiation deadlock: for example, how to limit the flying done by west-coast based pilots when it is dawn, Eastern Standard Time (EST). Putting the plane on autopilot and going to sleep is not an option. I have even seen prototypes that used "crew happiness variables" :)

It is interesting to look at the optimized crew-aircraft schedules for fractional jets that ferry well-heeled folks and time-starved execs on Gulfstream-Vs to various parts of the world between tiny airports. Needless to say, non-bottomline 'costs' and degree of personalization play a prominent role in the objective function. The customer is both king and queen. In the end, a well-designed optimization system's objectives can accommodate the considerations of all the stakeholders to consistently (and merely) reflect their relative importance from a human decision-maker's perspective. Nothing more, nothing less. As Gandhi ji said, actions reflect priorities.

The Rowling Elasticity

Elasticity is a very useful measure in structural engineering and helps us figure out the strength of materials (e.g. the 'strain' that is used along with Young's modulus). It is also an important idea in economics and price optimization. The price elasticity of demand quantifies the impact of a price change on the demand for an product. The thermal elasticity of electricity load in summer = percentage increase in residential cooling power consumption when outdoor temperature increases by 1%.  Elasticity is a dimensionless quantity = the % change in dependent variable / % change in causal.

Estimating Elasticity
Price elastic items like restaurant meals and airline tickets typically have an elasticity value less than -1.0 so that a 1% reduction in price yields a sales increase of more than 1%. Groceries typically are weakly price elastic in the range (-1, 0). Addictive items are relatively inelastic, while certain brand-image driven high-end luxury products may even have a positive price elasticity. The assumption of constant elasticity (-g) allows us to derive the following sales-lift model:
S = S₀(p/p₀)^-g
where S₀ is the (expected or observed) sales at price p₀. This is a simple and convenient representation that works well for small price changes. It is popular among retail analysts because you get a constant elasticity term (g) that is easy to communicate, which can also be easily estimated using linear regression on historical sales data by taking the logarithm on both sides.

Elasticity of Discrete Causals
Elasticity estimates can be used to gauge customer response and public sensitivity. Price is a continuous variable, but we can also associate elasticity with boolean indicator variables even though we cannot really calculate it's % change. For example, a promotional ad prominently placed in the front-page as opposed to the mid-pages of a weekly store circular may elicit a taller spike in sales. Some Hollywood movies that fly under radar experience huge sales lifts upon being named as an Oscar contender. BoxofficeQuant has an interesting analysis of the sales 'elasticity' of Oscar nominated movies. Statements by influential leaders tend to be relatively more elastic and elicit an heightened public response (e.g. Alan Greenspan in the US, or Narendra Modi in India). Perhaps there's a Matthew effect at work as well - the exact same product that is sold under a different name can be more elastic even though the benefit to the customer is the same. Recently, JK Rowling published a book under the pseudonym Robert Galbraith. Upon the discovery of this name change, Amazon sales of the book rose spectacularly: The magnitude of the short-term sales 'elasticity' of her famous name at Amazon.com was estimated at more than half a million.

Analytics and Cricket - XI: Using DRS Optimally

The Ashes
The first Ashes cricket test that concluded earlier today ago in England triggered this post.

(pic source link: guardian.co.uk)

This post is again related to the Decision Review System (DRS) that combines machine and human intelligence to support evidence-driven out/not-out decisions in cricket. The previous cricket-related post can be found here where a reader critiqued an earlier post on the false positives issue of DRS (that saw a lot of visits last week during this cricket match).  It's now apparent that England won the match thanks in part to their superior use of DRS compared to Australia.

DRS
The DRS consists of 3 components:
1. The human (a team of umpires, camera manners, and hardware operators)

2. The hardware (hot-spot, slow-mo cameras, snick-o-meters, etc). These are the data gathering devices.

3. The Analytics and Software (ball-tracking and optimal trajectory prediction, aka 'Hawkeye' based system)

This gives us three separate (but possibly correlated) sources of error:
a. Operator error

b. Hardware error: Technology limitations - resolution, video frame rates, hardware sensitivity, etc. may be inadequate at times for sporting action that occurs as fast as 100 mph or spin at 2000 rpm ...

c. Prediction algorithm error: Given such variations in sporting action, a forecast of the future trajectory of the ball is also subject to uncertainty.

(pic source link: dailymail.co.uk)

A smart user, after sufficient experience with the system, will be able to grasp the strengths and limitations of the system. In test cricket, a team is allowed no more than two unsuccessful DRS reviews per inning. Thus it is a scarce resource that must be cleverly used to maximize benefit.  In fact, the DRS is an example of a situation where the use of a decision support system (DSS) itself involves decision-making under uncertainty using a meta optimization model.

Optimal Usage of DRS
There are several factors that dictate when the trigger must be pulled by a cricket captain to invoke DRS to try and overturn an on-field umpiring decision.
i. The probability of success (p)
ii. The incremental reward, given a successful review (R)
iii. The cost of an unsuccessful review = cost of status quo (set to 0, normalized)
iv. The expected future value of having no more than k reviews still available in the inventory (concave, decreasing f(k), with f(0) = 0).

Reviewing only based on (ii) is a like a "Hail Mary" and banks on hope. On the other hand, paying exclusive attention to (i) may not be the best approach either, since it can result in a captain using up the reviews quickly, reducing the chances of taking advantage of the DRS later when "you need it the most". A person who doesn't use DRS at all (or too late to have an impact) leaves unclaimed reward on the table.

Probability Model
We'll start with a simple model. It's not perfect, or the best, but merely a good starting point for further negotiations.

The value of do-nothing  = f(k).

The value of a DRS review = p[R + f(k)] + (1-p)[f(k-1)] = pR + pf(k) + (1-p)f(k-1).

It is beneficial to go for a review when:
pR > (1-p)[f(k) - f(k-1)] or

p/(1-p) > [f(k) - f(k-1)]/R

i.e., odds must be greater than marginal value of a review / marginal reward

In other words:
it is good to review when the odds of overturning the on-field decision exceeds the ratio of the expected cost of losing a DRS review, to the expected incremental reward.

Use Case: for fifty-fifty calls (p = 0.5) with a single DRS review in the inventory, you would want to review only if you are convinced that the present reward is likely to exceed the value of not having DRS for the remainder of the innings. For a fixed reward, the RHS increases steeply after the first unsuccessful review due to the concave f. To be really safe, you want to risk a second and final unsuccessful review only when you can trigger a truly game-changing decision that greatly increases the chances of winning the match.  In general, R may neither be a strictly increasing nor a decreasing function of time. This is especially true in limited-overs cricket where a game-changing event can occur very early in the game. However in soccer, baseball, or basketball, R can be reasonably approximated as an increasing function over time. In general, it makes sense to save the review for the end-game. In any sporting event, including cricket, which is heading for a close finish, it may be beneficial to delay the use of a review.

In the Ashes test, Michael Clarke, the Australian captain appeared to pay more attention to 'R' and less attention to 'f', and was left without recourse at a crucial stage, and this hurt his team. On the other hand, the England skipper Alastair Cook delayed the use of DRS: The last wicket of a closely contested match fell when the game had reached a climax (R = R_max), and was DRS-induced. Thus, optimally delaying DRS involves the constant assessing and updating of risk versus reward and pulling the trigger when the odds are in your favor.

Analytical Decision Support Systems
A smart organization will aware of the strengths, weakness, and value of DSS based decisions. In some industries that are characterized by shrinking margins, even small incremental gains in market-share or profitability using DSS can alter the competitive landscape of the market. This motivates an interesting question: If two firms employ the same decision analytics suite provided by the same vendor, does it necessarily cancel out? or like in cricket, can one firm do a better job of maximizing value from the DSS to gain a competitive advantage?

Updated July 17, 2013:
It turns out, that wicketkeeper Matt Prior was instrumental in ensuring England's good DRS strategy. As we all know, a good prior saves your posterior during crunch time!

Are Operations Researchers Eulerian Decision Makers?

It is interesting to read Venkatesh Rao's book 'Tempo' (and the blog) from an Operations Research (OR) perspective and explore its ideas on human decision making. To better comprehend the themes in the book, I've been trying to map the examples in the book to familiar OR-type problems. For example, timing the purchase of consumer products at Amazon.com over a period of time while also managing to satisfy the free-shipping threshold to the extent possible feels like playing a game of tetris where we try to optimally delay the inevitable ("entropic optimization").

A recent tempo blog post compares Lagrangian versus Eulerian decision makers (let's call them LDMs and EDMs). These two approaches appear to have their origin as choices of frames of reference for studying fluid flow. An LDM tracks a single 'parcel' of flow though its entire journey while the EDM examines many parcels that flow through a particular location. Let's apply this to an airline OR (crew scheduling) scenario:

an LDM follows a particular crew operating a sequence of flights through a network before returning to her/his base, while the EDM looks at many crews arriving and departing through a particular airport. LDMs track flow-paths, while EDMS zoom in on activities within a specific node in the network. Another example from airline network revenue optimization: an LDM may focus on a passenger flowing and the accumulated revenue through an itinerary consisting of multiple flights, whereas the EDM zooms in on the variable price and fixed cost associated with a seat on a specific flight that is a part of many passenger itineraries.

Intuitively, it feels as if the LDMs focus on the clearly visible primal decision variables, whereas the EDM focuses on the latent, underlying dual problem. Column generation as an iterative optimization approach works well when the EDMs compute and transmit useful 'dual' signals from specific locations to LDMs (e.g., the rate of pilots arrive and depart at their node) who in turn, collect and apply this updated information to stitch together new and improved flow-paths across the network (i.e., columns), which in turn ensures more balanced and smoother flows across the nodes (i.e., rows). For some problem classes, if we solve the dual problem, our primal decisions are also at hand, and if the dual is unsolvable, the primal is likely to be problematic as well. Conjecture: Lagrangian and Eulerian decision makers build mental models that represent (informal) primal and dual formulations of the same problem. Depending on the context, one or the other approach may be more convenient or effective. 

The ability to extract information from noisy dual signals is useful in solving complex or large-scale industrial optimization problems. For example, in the airline revenue optimization example, it is known to be more convenient and reliable for airline revenue/scheduling planners to take decisions based on the shadow prices of flights, rather than rely on the optimized prices of the millions of possible itineraries. Dual methods are insightful and can help solve a decision problem where a frontal assault fails. To the best of my knowledge, the default out-of-box method invoked by the leading mathematical optimization software packages today for solving linear programs is their dual algorithm.

In general, Eulerian decision making or as this post sees it, 'dual-driven decision making' may be the more attractive first-choice approach for human decision making. The tempo blog notes:
"... When flow gets turbulent, the fluid mixes a lot. To properly follow a “parcel”, you have to let it expand as flow lines diverge and churn. This means there is more fluid in your parcel than you started with, more “noise.” Eventually you are trying to analyze world hunger — the entire body of fluid.
But the Eulerian static parcel stays the same size. It just bleeds causal structure and gets more entropic. The action gets a lot more random and choppy, but still tractable in size. It is also easier to shrink what you’re paying attention to when things get complex — it’s called focusing – than it is to reduce the ambition of a model you’re tracking (generally called pruning)..."

Are Operations Researchers Eulerian Decision Makers?