Wednesday, July 31, 2013

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.

Saturday, July 27, 2013

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'.

Thursday, July 25, 2013

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.

Monday, July 15, 2013

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 = S0(p/p0)-g
where Sis the (expected or observed) sales at price p0. 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.

Sunday, July 14, 2013

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!

Monday, July 1, 2013

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?