Business Rule Conflict Resolution: Needles in a Haystack

This post uses the retail industry as a sketchpad to illustrate some simple but useful conflict resolution ideas employed within optimization methods in practice.

Least Infeasible Answers
Retailers have to address a myriad of business rules while optimizing merchandising, pricing, shelving, replenishing, and assortment planning decisions. Operations Researchers build mathematical models that translate these rules into a combination of soft constraints (goals, objectives, Key Performance Indicators (KPI)) that have to be maximally satisfied, and hard constraints that must be absolutely satisfied.
Conflicting hard rules can prevent the optimization application from returning a recommendation. The retailer would like to know which among their long list of rules is/are the root cause of this conflict so that they can address them appropriately and re-evaluate. Commercial solvers like CPLEX (and GUROBI, among others) can perform an infeasibility analysis to provide useful information pertaining to IIS (Irreducibly Inconsistent Sets), and based on optimizing a user-parameterized penalty function, can also find a minimally infeasible answer. These are non-trivial problems. (Try explaining to a senior pilot why a more junior pilot was assigned that plum schedule filled with all those long Hawaii layovers!) JW Chinneck has an entire book dealing with such issues.

User Experience
The liberal-arts degree armed retail store manager (RSM) has a business to operate and sales targets to achieve. Many a RSM care little for iterative conflict refinement and resolution and have even lesser patience to set up paramterized penalty functions. He/She often desires that the analytics software product automatically flag problematic rules and always return the "best possible" answer(s) and be done with it. 'Null' or 'Try, try again' is not an option. A positive user experience combined with the ability to "help me earn a bonus or you are toast" is correlated with continued patronage. In such situations, the decision analytics plumbing must be designed in such that it can, with little to no external guidance, produce practically useful diagnostics that pinpoints infeasibility and generate 'best fit' solutions that are readily business-comprehensible to the average user. After all, the business application interface and functionality is not primarily meant to be a analytics-tutorial warp drive thingy.

 (picture link source: anandtech.com)

Actions Express Priorities - Mohandas Gandhi
A store manager may have a high-level goal in mind such as: find a minimally business disruptive resolution of conflicting business rules. Toward this, several retailers employ prioritized business rules that result in a special haystack structure that invariably makes the conflict identification and resolution process more transparent and easy to manage. What would this decision problem structure look like? Borrowing computer-ware terminology (for example), it would be akin to an ordered collection of hard constraints, soft constraints, and firm constraints. Patented methods that gainfully exploit related ideas have been used to build retail optimization products that turned out to be successful in the global marketplace. On the other hand, the efficacy of such resolution methods can be context-specific and is not necessarily designed to yield universally scalable solutions. If your job is to solve only your company's or industry's specific problems and not that of all current and future corporations in the galaxy and beyond, such methods can be handy.

Analytics and Cricket - X : Reader's Response to DRS Debate

It's getting increasingly difficult to post on cricket given that the Indian cricket team is getting ripped to shreds by half-decent opposition despite home-ground advantage. Of course, as noted in an earlier post, home courts can significantly increase the chance of a choke, and this may well be happening. Mahendra Singh Dhoni (if by some chance, still remains the captain of the Indian team after the current cricket series) can win a few more tosses if he can exploit this idea. Desperate times call for analytical measures!

Meanwhile, an astute reader emailed a detailed response to the Bayes-theorem based analysis of the Decision Review System (DRS) used in cricket, which was posted on this blog a few months ago. He made some very pertinent points along with some brilliant comments on the game, which led to an informative exchange that will be carried in the next couple of cricket-related posts. Here is our the 2x2 color coded DRS matrix again for reference.

Raghavan notes:

".... I must question some of the steps in your analysis:

1. In your derivation you use  P(RED|OUT) = 0.95.  I think this is true only if all decisions are left to DRS.  You have considered only those decisions that are deemed not out by the umpire and referred.  The 95% number does not hold for these selected cases.  It would be lower.  Here's the rationale:
There is a high degree of correlation between DRS and umpires decisions; understandably so, since all those "plumb" decisions are easy for both, the umpire and DRS.  Bowlers would rarely review these decisions.  For the 10% or so cases when the umpire rules the batsman not out incorrectly, the DRS would very likely have a lower accuracy than its overall 95%.  

2. If you assume the "red zone" in the picture is sufficiently small compared to 10%, you would get the accuracy of DRS being about 50% for the cases when the umpire incorrectly rules not out.  Now, this needs a bit of explanation.  

Let's assume that whenever the umpire rules out correctly, the DRS also rules correctly (well, at least close to 100% of the time).  Note that this does not include just the referrals, but also all the "easy and obvious" decisions that are not referred.  Since the overall accuracy of DRS is 95%, of the 10% that the umpire incorrectly rules not out, DRS also gets it wrong for half of those 10% cases giving an overall 95% accuracy.  In case the "red zone" corresponding to incorrect OUT decisions of the DRS is not close to zero, but say 2% (which is large in my opinion), the DRS accuracy in the bowler referred cases we are talking of would by 70% rather than 50%.  Still way lower than the 95% overall accuracy. [I have made some approximations here, but the overall logic hold]


3. Now, if you plug 70% instead of 95% in your next steps, you get P(OUT|RED) = 88.6%.  Nothing wrong with this number, except when you compare it with the 90% accuracy of umpires.  It's not apples to apples.  P(OUT|Umpire says OUT) is not 90% if you only considered referred cases.  It's actually a conditional probability:
P(OUT|Umpire says OUT, BOWLER REFERS).  I don't have enough information to estimate this, but I'm sure you'll agree it's lower than 90% since bowlers don't refer randomly.

4. I think the right comparison is between the what the final decision would be with and without DRS. There is no doubt that umpire + DRS referrals improve overall accuracy of decisions.  I admit that false positives would increase marginally, which affects batsmen more than bowlers because of the nature of the game (a batsman has no chance of a comeback after a bad decision, while a bowler does).  But I think it is because of the way Hawk-eye is used today.

5. In my opinion, the main problem with DRS is that its decision are made to be black and white.  There should be a reliability measure used.  A very rudimentary form of this currently used in LBW decisions.  For example, if the umpire has ruled out, to be ruled not out by DRS the predicted ball path has to completely miss the stumps.  But if the umpire has ruled not out, the predicted path should show that at least half the ball is within the stumps for the decision to be over-turned.  Eventually, I feel Hawk eye would be able to estimate the accuracy of it's decision.  I'm sure Hawk eye has statistics on it's estimates.  The standard deviation of the estimate would depend on several factors - (1) how far in from of the stumps has the ball struck the pads (2) How close to the pads has the ball pitched (hawk-eye needs at least a couple of feet after the bounce to track the changed trajectory), (3) Amount of turn, swing or seam movement observed.

If a standard deviation (sigma) can be estimated, then a window of say +/- 3*sigma could be used as the "region of uncertainty". If the ball is predicted to hit the stumps within this region of uncertainty then the decision should be out. Of course the more complicated it gets to explain to the viewer, the more resistance there would be to be accepted.  But if it is the right way, it will eventually get accepted.  Take DL method for example.  A vast majority of viewers don't understand it fully, but most of them know that it is fair.

6. There's another aspect that needs to be investigated.  It's about how the decision of the on-field umpire is affected by the knowledge that DRS is available. "




Followups will be carried in a subsequent post. Blog-related emails can be sent to: dual[no space or dot here]noise AT gmail dot com, or simply send a tweet.

The Rose and The Chrysanthemum

An extended tweet triggered by recalling an old joke.

(pic: Wikipedia)

Girl: look! a rose!

Boy: No, that's a Chrysanthemum.

Girl: Ok, then spell it

Boy: Kri--, no. Ch-ri-san... you're right, that's a rose.

This is an example of user-optimality.

Optimal Location of Speed Limit Signs

One of the nice things about the relatively more recent automobile GPS products is that they are able to inform us of the current speed limit. Sometimes, when we take our eyes of the road for a second to grab a soda, we may have driven past a speed limit sign and be unaware of the new speed limit. Of course, there are times when the GPS unit itself does not display the speed limit for certain areas, and at other times, it is off by 10 mph, perhaps due to recent road updates. Like any decision support system, the GPS unit cannot be a fail-safe backup for user negligence.

The problem of optimally locating speed limit signs on a network must have been studied and solved a long time ago especially since the analysis of traffic and transportation networks has long been popular research area among ORMS folks. Perhaps there exists a practical combinatorial optimization problem in terms of determining minimal/safest/least ambiguous ways of locating speed signs in the presence of scarce resources and budget limits. A partial list of assumptions and constraints include:
- Speed limits change in discrete quantities of 5mph or 10 mph
- Every driver will treat the last speed limit sign (or update) they saw on the network as the prevailing speed limit
- Every driver at every point in the road network must be in unanimous agreement on what the speed limit is. This is the ideal situation.
- In practice, perhaps the above requirement can be relaxed to stipulate that any non-trivial ambiguity must be resolved with a certain time or distance threshold whose value is location-specific
- Different types of speed limit signs are possible - they may be time-dependent (day/night) as well as location-dependent (school, bridge, tunnel) - Speed limit values can be fixed or variable ("smart roads"). This requirement can potentially inject a dynamic optimization aspect into the problem.

Perhaps a greedy method may be sufficient to generate a good answer to the (fixed value) speed-limit signpost location problem. There are of course, numerous other related location optimization problems on road networks:
locating advertisement hoardings, direction/information signs, emergency vehicles, detours, etc. All these models appear to be well studied in the literature. The proliferation of smart-phones can also have an impact on future 'smart road network' design in general. All in all, location, location, location science continues to be a very interesting sub-area of Operations Research.

House Hunting Efficiently

One of the consequences of the kind of convergence shown in this graph was that it created the need to buy a house. It's become a ritual to spend weekdays creating a list of houses that are feasible with respect to hard constraints (big kitchen, level lot, ..), and then converting that into a prioritized list based on how they score on soft constraints (pre-wired for Bose speakers, for example) that in turn motivates a preferred way of visiting these houses during weekends. I noticed that I rarely see each house in isolation and my view of a house tends to be colored by what I saw earlier. However, of late, the time to view these houses has become a scarce resource, so I created an O.R driven prioritized list that maximizes and optimally allocates viewing time, keeping the total duration equal to the limited time available. I used my automobile GPS unit as the solver.

This GPS unit "solves" the Traveling Salesman Problem (TSP) to figure out the optimal (?) order of visitation that minimizes total drive time, which automatically maximizes aggregate viewing time. (In particular, if houses are located on either side of a busy highway or Main Street, a good heuristic would be ensure that the optimal path intersects such a link infrequently.) I can then allocate the optimal expected viewing time to the houses based on personal preferences. The total viewing time also informs me if I have spread myself too thin, in which case, I can start deleting houses with the lowest scores from the list and re-optimize until the solution looks reasonable. 

If viewing order is important from a 'relative comparison' perspective, the resultant constrained TSP problem becomes a bit more harder to solve using a GPS unit. A simple heuristic rule could be to fix the second node ("first house to first") and/or the second-last node ("house to visit last") of the tour and let the others be visited based on time-optimality. If your realtor drives you around, her/his office is the start and end node of the Hamiltonian circuit.

One issue I encountered while using the GPS unit to merely drive-by a house as part of a local neighborhood search (pun unintended) is that I had to get close enough to the house and maybe pause a bit to inform the GPS that this house has been reached. Otherwise, the GPS unit would continually re-route me back to the house, resulting in considerable confusion.

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.

The iPod and the O.R. Designer

The web is full of business articles that extol the benefits of a great, overall user experience that has come to define the iPod product. These articles roughly state that we knowingly accepted a discrete approximation of continuous music and enjoyed the experience because it was delivered in a really convenient manner. Business commentators even go so far as to say that features don't matter any more. Not surprisingly, there are huge lessons to be learned for those us who make a living by building apps with 'O.R. inside' for business end-users.

If your OR program in school was part of the Industrial and Systems Engineering (ISE) department, then we would recognize that these are not novel ideas. We have seen this before in our ISE labs and it resembles 'Human Factors' engineering. It was always exciting to know what the HFE guys were up to - they were generally designing all this ergonomic stuff - keyboards, wheelchairs, etc. We O.R. grads were optimizing big-deal industrial problems with sophisticated math and did not pay enough attention to such "low-tech and qualitative" HFE ideas. Designing for an optimal business-user experience can be thought of as an area that combines OR with HFE. First a look at a partial checklist of design questions that we can relate to.

Does your O.R. app:
- require the user to have an O.R. PhD to operate?
- feel paranoid about the sophistication of the O.R. technology inside?
- obsess about run time with little regard for quality?
- have bewildering layers of menus filled with dials for 'costs', 'penalties', etc.?
- change answers wildly with small changes in input?
- come back with a blank stare if it encounters infeasibility somewhere inside?
...

You get the idea. An O.R. practitioner not only has to worry about the stuff that is inside - traditionally, we've been good analysts and trained for that, but it's about time we become equally good designers - few, if any, O.R. graduate programs teach that. Perhaps we should be teaming up with our next door HFE neighbors on this. As we continue to explore this theme, we will notice interesting connections between what's inside and outside the app.