Monday, December 30, 2013

Indian Intellectuals and the Fighter-Pilot Syndrome

Update: title changed

Legendary formula car racer Michael Schumacher suffered a serious injury in a skiing fall. As millions around the world pray for his safe recovery,  a troubling question was triggered by this sad news:

"How likely is it for a skiing enthusiast, who is known to have made a successful career in the superfast and dangerous world of Formula car racing, to meet with a skiing accident?"

Does this conditional probability increase or decrease? I am not aware that Schumi claimed he was a skiing expert or thought of himself as one. This is just a sample of one and could just be a tragic coincidence. The question remains open and the focus of this post is on a related topic.

Here's a wikipedia blurb on a US Air Force officer John Stapp:
"During his work at Holloman Air Force Base, Stapp became interested in the implications of his work for car safety. At the time, cars were generally not fitted with seatbelts, but Stapp had shown that a properly restrained human could survive far greater impacts than an unrestrained one. Many traffic-accident deaths were therefore avoidable but for the lack of seatbelts. Stapp became a strong advocate and publicist for this cause, frequently steering interviews onto the subject, organizing conferences, and staging demonstrations (including the first known use of automobile crash test dummies). At one point, the military objected to funding work they believed was outside their purview, but they were persuaded when Stapp gave them statistics showing that more Air Force pilots were killed in traffic accidents than in plane crashes. The culmination of his efforts came in 1966 when Stapp witnessed Lyndon B. Johnson sign the law making manufacture of cars with seatbelts (lapbelts at that time) compulsory..."




Controlling fast jets did not give those pilots additional skills that made them equally safe at driving cars at some speed. Is it possible that this 'fighter pilot effect' gave them a false sense of security while driving the much slower motor cars?  Similarly, safely driving ultra-fast cars shouldn't automatically make one an equally safe hi-speed skiing expert (update: initial reports indicate Schumacher was not going very fast). However, public belief in this 'fighter pilot syndrome' appears to exist at some level, and this is especially true in India. For example, if you win a Nobel Prize or for that matter, any prize in the west, then regardless of your field of expertise and your near-total ignorance about what makes India tick, you are given special powers that turn you into an expert on every topic under the sun (especially Indian culture and politics), overnight. Unlike Marxist economist Amartya Sen or India's egoistic movie stars, who don't need a second invitation, there are others who prefer not to make a fool of themselves in public. However, the Indian media does not spare them the embarrassment by demanding their "fighter pilot" advice on unrelated topics. This 'intellectual celebrity' feedback is then used to try and influence public opinion. A good example is the recent NDTV-25 debate panel on "secularism in India" compered by 2G-scam tainted journalist Barkha Dutt that included exactly one genuine expert, Arun Shourie, who knew what he was talking about, and bunch of other "experts".

All-weather experts and their Indian media co-pilots must be asked to wear their seat-belts and slow down before they take the Indian public for a ride.

Happy New Year. Drive Safe. Get well soon, Schumi.

Monday, December 9, 2013

Optimize Your In-store Holiday Shopping Route

Remember the last time you were not tired after holiday shopping in a busy mall, bulk shopping at a discount-club store, or weekend shopping at a crowded grocery store?

(source links: http://info.museumstoreassociation.orghttp://binaryapi.ap.org)

Hopefully, the simple and preliminary 'operations research (O.R)' analysis in this post can help make the experience a little less stressful and maybe even let us enjoy a bit of retail therapy that we can't get online.  The shopping optimization problem addressed here is simple one, albeit with a twist. This post was triggered by an observation made after recent shopping expeditions to a nearby Costco outlet.

We have a long shopping list of L line-items (i) of various quantities N(i) that we have to pick up in a store. How should we optimally reorder our shopping list to reflect the sequence in which we pick up these items?




Version 1
The simple version aims to minimize total shopping time. For example, we can formulate this as an instance of the so-called traveling salesman problem (TSP) that finds the shortest sequence that starts at the entrance, visits each of the L 'cities' once, then the checkout counter, and ends at the store exit (entrance). A google search shows this 2009 research paper by researchers at UPenn, which shares the technical details and interesting results for this version.

To simplify our problem, we assume that the topology of the store is prior knowledge, and we can roughly pre-assign items in the same aisle to the same 'city'. The resultant problem is to find the order of visits to the aisles of interest to us. If the aisles are neatly arranged as node intersections in a rectangular grid, then we simply have to find the shortest rectilinear "Manhattan" distance tour in this grid. Depending on the type of the store, the store-layout itself may be optimized by the retailer based on the observed foot-traffic and 'heat-map' data. For example, it may be designed to retain the customer in the system to increase chances of purchase (exploratory tour, store selling expensive luxury/fashion products), or quickly out of the system (routine tour, obligatory products like groceries), or based on some other goal. Store space and layout problems are known to be commercially useful optimization problems in the retail industry.

Picture linked from an iTunesApp (Concorde) page of Prof. Bill Cook that solves TSPs :)

Version 2
Let us additionally assume that product attributes have an impact on our order. Suppose one or more items in our list is located in the frozen section at a grocery store, then we may prefer to get there at the end of our tour. Luckily, many stores appear to anticipate this (?), and locate this section towards the end of the store. Thus if 'maximum freshness' or 'minimum damage' is an additional consideration, this may alter the TSP route and the final ordering of items in our shopping list.

Version 3
This was the problem that was of immediate interest to me today. Costco sells stuff in bulk, so the items tend to be heavy, and considerable energy is expended moving the cart through the store. At the risk of mangling undergrad physics, let us proceed with our analysis...
Let μ be the (constant) coefficient of rolling friction between the wheels of the shopping cart and the store-floor. Then the work required to move mass m through distance d = force x displacement =μmgd, where g is the (constant) acceleration due to gravity. Thus a squeaky-wheeled cart will make us work extra hard. Speed of shopping is a consideration if we want to keep track of power (force x velocity). Covering the same tour length in half the time requires twice the power, i.e. the rate at which our body expends stored energy.

Carry versus Cart (reinventing the wheel)
If we had zero rolling friction, technically the only work involved is in lifting items and putting them in our cart. We can assume that this work is independent of our order of visit and is a fixed quantity. On the other hand, if we are not working with a wheeled-cart, but carry our stuff in a market-basket or shopping bags, then we have to raise the potential energy of the items to height 'h' (mgh) all the way until checkout, and also overcome the sliding friction between our shoes and the floor, which would probably be higher than the rolling friction, as illustrated below.

(link source http://static8.depositphotos.com)

Why is a shopping experience increasingly stressful over time?
As we add items to our cart, the work done per unit time (power) required increases. In the continuous case, this problem closely resembles our 'optimal snow shoveling problem' analyzed during a February snow storm. The accumulated objective function cost there increases as the square of the distance. Here, we look at the discrete situation. When we visit city 'i' to pick up N(i) items each having mass m(i), we instantaneously add mass N(i) * m(i) that we have to lug around until checkout. After picking up k-1 items, my total work done will approximately be:
μg * sum (i = 0,... k-1) W(i) * d(i, i+1), where i = 0, represents the store entrance, m(0) represents the mass of an empty shopping cart, and
W(i) = sum(j = 0, .., i) N(j) * m(j) = total mass carried from city i to i+1.

In other words, the 'cost' accrued while traversing any pair of cities also depends on the items we picked up earlier, i.e., it is no longer memory-less and varies depending on the cities visited earlier.

Result: our shopping gets increasingly more tiring over time

If one of the items in our shopping list involve a heavy item, then our optimal solution may no longer be the shortest time tour.  We now have to solve a minimum-effort TSP. Operations Researchers have also looked at methods for solving a path-dependent TSP in the past. A simple heuristic approach would be to break the trip into two tours. The earliest items stay with us the longest, so we first find the optimal sequence through the light items, followed by the shortest tour through the heavy items. We also have to organize the shopping cart carefully enough to ensure that our light items do not get squished by heavy products, and our ice-cream doesn't melt. I'm sure there are better algorithms than the one provided here.

Recommendation
If we want to burn calories while shopping then a good way to do that, based on our previous discussion is (a) carry our items, (b) pick up the heaviest items first, and (c) take the longest route to maximize energy expenditure (d) walk briskly. This health-and-fitness article provides ten tips for exercising that includes these ideas. For the rest of us who are looking to minimize effort, we simply do the opposite:

We sort our shopping list items in decreasing order of expected weight (frozen stuff goes to the bottom too), while also ensuring that the aisles of adjacent items in the list are close to each other, and we are not revisiting aisles or zig-zagging much.  Some swapping may be required to find improved sequences. Many of us have probably evolved into efficient shoppers over time, and naturally take these steps and more, but if there an opportunity for improvement that the 'science of better' can uncover for us to make our shopping less stressful, let's take it.

Happy Holidays!

Update 1: December 17, 2013
IBM Smarter Retail article says:
"..... Most recently, Lowe’s has offered the customer a product location functionality that is integrated with their wish list. According to Ronnie Damron, .....Whether customers are browsing the store for ideas or searching for a specific item in a hurry, we think the Product Locator feature will simplify the shopping process, creating a better experience that encourages customers to come back again and again.”

Monday, November 25, 2013

Optimizing Shubh Laabh: Harmonious Profitability

Sustainable machine-generated, data-driven decisions
The growing popularity of 'Big Data' coupled with 'machine learning' techniques coincides with an increasing use of automated, machine-computed solutions for a a variety of business problems that were once solved and optimized based (predominantly) on human inputs. Machine-generated solutions have been shown to be superior to these previous methods on the measured performance metrics in many instances, and companies all over the globe have deployed advanced analytics and business optimization models (e.g. built using Operations Research) to achieve incremental profitability, cost reductions, or improved system efficiency. However, all is not well. Some solutions are sustainable, and work well over time, while others begin to run into a seemingly endless stream of human or environmental issues, and fall by the wayside. 

What differentiates sustainable machine-generated optimizations from the unsustainable ones? The answer is not straightforward, and this post explores one aspect. For an example of what kinds of issues can crop up, see this BBC news article: "Amazon workers face increased risk of mental illness", as well as this older article on 'unhappy truckers'A portion of the BBC article highlighted below is color-coded to show where sustainable decision optimization could be potentially applied to improve upon the status-quo):

 "..... Amazon said the safety of its workers was its "number one priority."

Undercover reporter Adam Littler, 23, got an agency job at Amazon's Swansea warehouse. He took a hidden camera inside for BBC Panorama to record what happened on his shifts.
He was employed as a "picker", collecting orders from 800,000 sq ft of storage.
A handset told him what to collect and put on his trolley. It allotted him a set number of seconds to find each product and counted down. If he made a mistake the scanner beeped.
"We are machines, we are robots, we plug our scanner in, we're holding it, but we might as well be plugging it into ourselves", he said.
"We don't think for ourselves, maybe they don't trust us to think for ourselves as human beings, I don't know.
..... Prof Marmot, one of Britain's leading experts on stress at work, said the working conditions at the warehouse are "all the bad stuff at once".
He said: "The characteristics of this type of job, the evidence shows increased risk of mental illness and physical illness."
"There are always going to be menial jobs, but we can make them better or worse. And it seems to me the demands of efficiency at the cost of individual's health and wellbeing - it's got to be balanced."
I spent the early-mid 2000s redesigning, and improving airline crew scheduling optimization systems. This period also happened to be the industry's most tumultuous: 9-11, out-of-control fuel and labor costs exacerbated by the invasion of Iraq, repeated strikes by various worker unions followed by contentious negotiations that lead to multiple CBAs (collective bargaining agreements) being ripped up and rewritten, and companies lining up to file for Chapter-11 bankruptcy protection, etc. Endless problems. The office atmosphere got quite intense when the R&D team somehow managed to find itself in the middle of these events, and facing heat from all sides (management, unions, soaring passenger complaints) on the kinds of solutions that were generated by our decision support systems (The US airline industry pioneered the use of such techniques). The analytical lessons empirically learnt from such episodes are hard to replicate in classrooms. One such lesson was "pay a lot of attention to the impact of your model on the people and environment". The application of this lesson has been explored in this space in a variety of contexts earlier: here (Gandhi's methods), here (Smart-Grid), here (Airline Crew scheduling), and here (Conflict resolution). The issue is revisited here by borrowing an idea from traditional Indian business philosophy to see if new insight can be generated toward answering our question on sustainable business optimization.



(pic link source: http://www.indiabazaar.co.uk)

(Updated: November 30, 2013 Finally found the link to article that inspired this post)
It is interesting to note that for centuries, traditional business communities in India had adopted the policy of Shubh Laabh (written in Hindi in the picture), which roughly translates into 'auspicious/harmonious profit' (Aravindan Neelakandan, co-author of 'Breaking India' in the linked article notes: "Lakshmi symbolizes the wealth that is holistic: it is wealth that puts welfare (Shub) before profit (Laabh)." The pursuit of wealth and profitability was never frowned upon in Hindu society, while unconstrained profit maximization was recognized as a socially destabilizing and ecologically unsustainable objective.  'Shubh Laabh' recognizes and respects the presence of long-lasting and latent side-effects that arise from business decisions (that can bring you 'bad luck') and attempts to balance them equitably with the more immediate goal of profitability (Laabh). These traditional businesses employed some operational form of Ahimsa (the principle of minimal harm) to optimize Shubh Laabh:
Rule a) limit harm (hard-constraint version)
Rule b) minimize harm (soft-constraint version)
Let us see how this idea can be incorporated within modern decision optimization systems. Amazon appears to have satisfied all legal requirements via (a) by making safety a top priority. It has probably ensured that the statistical rate of accidents is below some stringent threshold. In the airline world, (a) is achieved by ensuring total compliance with respect to all FAA- and CBA-mandated safety rules. However, this represents a necessary condition that tolerates a certain level of error as 'legally acceptable collateral damage'. The resultant formulation is: maximize profitability subject to safety regulations. However, this in itself is an insufficient specification if we want our algorithms to minimize harmful side-effects. An Ahimsa-based model would additionally consider (b) and eschew profit achieved at the cost of a reduced employee quality-of-work-life (QWL) or environmental degradation, as unsustainable and counterproductive in the long run. 

For large-scale systems such as a retail supply-chain or airline crew schedules, a reasonably skilled analytics professional should be able to incorporate requirements (a)-(b) within their decision support algorithm which, among alternative near-optimal solutions (and there are often many of these), selects one that also maximizes worker QWL, and/or minimizes harm (e.g. reduces carbon footprint). This requires the human-and-environment-variables in the system be treated positively as an active and equal partner based on mutual respect, by explicitly including their requirements as part of the primary goal (objective function), going beyond a legalistic/adversarial approach of treating these variables as a 'loss-making noise that has to be managed' by specifying a minimum tolerance constraint.

To summarize
It is possible to achieve sustainable profitable solutions via automated decision support systems that are also harmonious and sustainable, by paying due respect to all the stakeholders (including Ms. Nature), right from the design phase.


An old blog discussed Rajiv Malhotra's use of 'mutual respect' (as opposed to mere tolerance) as a simple but powerful basis for two heterogeneous groups of people, or people subscribing to conflicting thought systems, to achieve a fair and sustainable equilibrium in their interactions. It appears that such a mutual respect:

a) is implicitly present in the idea of Shubh Laabh, which in turn

b) can be employed as a key guiding principle of 'sustainable design' when building decision support algorithms for managing complex business problems, where multiple, and potentially conflicting, goals have to be delicately balanced.


The opinions expressed in this article are personal.

Wednesday, November 20, 2013

Optimizing a Kid's Birthday Party

The previous post was about virtual books. This brief post is about children's books, and the nice idea of requesting kids to bring their used books to a birthday party. Suppose there are N kids, with kid(i) bringing book-set B(i). The optimization problem is fairly simple to state. Get the kids to exchange their books in such way that total satisfaction is maximized after the exchange.

A distributed optimization approach could, for example, let kids do their own thing and perform two-opt book swaps until every kid achieves their user-optimal solution, or no candidate is available for swapping.

A centralized optimization scheme may require a parent to create a library of sum(i)|B(i)| books, acquire book-attribute preferences from kids, the attribute vector for each book, and using this information to (informally) solve a partitioning problem that assigns |B(i)| books to kid(i) such that it maximizes the preference sum.

A Karmic optimization approach, which I personally prefer, could let the kids enjoy the cake and ice-cream, while a parent mixes the books up and organizes a fun lottery where the books pick the kids.

Regardless of how the books are assigned, if we do this over a sufficient number of birthday parties, the kids would eventually get to read a variety of books at no extra cost.


Friday, November 8, 2013

Optimizing Kindle Book Rentals

When to buy at Amazon
Amazon just raised their 'free shipping' threshold to 35$, a few weeks before the holiday shopping season. This simple 'entropic optimization' approach, which utilizes Amazon's wish list to time-prioritize purchases remains valid, but requires an increased level of procrastination. What also caught my attention is Amazon's Kindle rental models. Beyond the initial sunk costs, virtual products are high margin, with negligible holding cost, besides an infinite, instantaneously replenish-able inventory. They are also scratch/damage proof. The only long-term downside to providing a renting option appears to be faulty pricing. If we price too low, we may turn many potential buyers into renters, and a high price may discourage potential renters. Let's look at a couple of (real) Kindle rentals for which I laboriously pulled data while watching Sachin Tendulkar's 199th cricket test match.

Kindle Book 1 (Undergrad Math textbook)
The minimum rental period is 60 days (50$), and the maximum (apparently) is around 360 days (140$), with the marginal price held approximately constant. We pay 30 cents for every extra rental day beyond the minimum period.

Kindle Book 1: Price Versus Rental Days

The cost (snapshot at the point of observation) of purchasing a permanent copy was 200$. If we plot the percentage price discount versus the rental period expressed as percentage of a year, we can see that the discount varies between 25% and 70% of the full cost. Approximately linear model employed for this book. Here, we can rent the book for an entire year without paying the full price.

Price Discount Percentage versus Rental Percentage-of-Year


Kindle book 2 (Advanced forecast-modeling textbook)
The second example is a bit more interesting. The content is technically far more sophisticated compared to Book 1, but the target market is different, and the number of (paper) pages is far lower, and so is the price. In both instances, the cheapest rental can be purchased at less than half the full price. There are roughly three different marginal prices employed within a rental period that varies between a minimum of 30 days (~$15) and a maximum of 365 days (~$35, also the full Kindle price). The corresponding breakpoints occur (roughly) near the 90-day, and 180-day rentals, respectively. If we restrict our attention to this rental time period, the price is concave, with the marginal prices decreasing as the rental period increases. It is preferable to simply buy the book rather than rent it for close to a year.

Kindle Book 2: Piece-wise linear rental pricing
A percentage based plot is show below, along with an empirical power-law pricing model (using Open Office) that looks like a near-perfect fit for this particular book rental. A log(x) model also works well in this instance.



Optimization Models
Seller: How would optimization scientists go about determining these marginal rental prices? Suggestions welcome. Perhaps ideas from analytical rental models for other products (cars, houses, equipment ...) can be used as a starting point to figure out this "information rental" model. Perhaps the pricing model can be initialized using historical rental data gathered for similar books. This being an online retail sales model, we can dynamically and frequently update these models or their parameters to maximize performance metrics. 

Buyer: From a user-perspective, if we can assign a value for owning a permanent copy, and have an informal mental model of the temporal utility of a rental as T(x), then (for example), we could solve some variation of this single-decision problem in 'x':
Maximize Value V = T(x)/f(x) ( Maximize log T - log f, optionally)
 x  u
to determine an optimal 'rent versus buy versus walk-away' decision based on our willingness-to-pay. Assuming a 1:1 mapping between 'f' and 'x', so we could transform any price range limit into an equivalent (l, u) bound on 'x'.
A simple way to solve this problem is to enumerate the values of V for all rental days using a spreadsheet.

Renting digital textbooks over a semester
Like thousands of Indian immigrants in the U.S, I came on an assistantship, carrying a couple of hundred bucks in my pocket that represented a big chunk of my parent's savings. I actually felt rich when I discovered that the take-home monthly income from my research assistant-ship after tuition fees turned out to be more than what my engineer dad was earning after decades of dedicated service in Nehruvian India. Until I saw the prescribed textbook prices, that is. Buying overpriced books was simply out of the question when the few copies in the library were already taken. There was no Amazon then, and it would've been amazing to have a rental option like this, especially when continued funding is dependent on maintaining good grades.

For example, if we only cared about a textbook for portions of a semester (our total planning horizon), and our total price budget is 'pmax', then we can informally solve a multiple-period version of the above optimization model to come up with a best waiting strategy and rent for one or more time periods ("quiz time") which maximizes our total T(x) and also keeps us within our "knapsack" like price budget for the semester. This policy of "rent as needed" may work well with book rentals having a constant marginal price. On the other hand it may be worthwhile renting fewer times for an optimally longer duration if the price is concave in the length of the rental, as it is in our second instance. 

Monday, November 4, 2013

Operations Research for the SmartGrid - 2: Optimization Problems

In this sequel to part-1,  an overview of a few, specific optimization models employed within three different Smart-Grid areas is provided. I found these samples to be interesting from a practitioner's perspective. INFORMS publishes a lot of good papers in these areas, and is an excellent source of references.

Managing Electric-Vehicle (EV) Charging within a Smart-Grid
EV System Perspective: 
EV problems are fun. Researchers in Hong Kong have investigated efficient online charging algorithms for EVs without future information, where EV charging is coordinated to minimize total energy cost. EVs arrive at the charging station randomly, with random charging demands that must be fulfilled before their departure time. Suppose that N EVs arrive during a time period T, indexed from 1 to N according to their arrival order.  The optimal charging scheduling problem minimizes a total (convex) generation cost over time T, by determining the best charging rate for EV i at time t, x(i, t), subject to various constraints.

The difficulty of an efficient charging control mainly comes from the uncertainty of each EV’s charging profile. Prior approaches assume that the arrival time and charging demand of an EV is assumed to be known to the charging station prior to its arrival. However, the HK team have come up with an optimal online charging algorithm that schedules EV charging based only on the information of EVs that have already arrived at the charging station. They show that their approach results in less than 14% extra cost more an optimal offline algorithm,   which can be potentially reduced even further.

EV User Perspective
Cool routing algorithms can also be developed from a user-perspective. One interesting work I came across takes a more holistic and rigorous view of the simple Tesla routing problem that I blogged out a while ago. Researchers in Europe look at a routing subproblem within the more general context of managing congestion at EV charging stations and minimizing the impact of EVs on grid performance. They employ an algorithm to compute the best charging points to visit to based on the estimated travel time (shortest-path, and reachability based on available battery power) to all charging points, and the point-specific charging cost. Input: O-D locations, initial battery level, desired charging level for the EV user, and the preferred time of departure. The optimal route, the subset of intermediate charging points, and the slot that the EV is going to charge at, are returned as output.

Demand Response and Pricing
Revenue Management and supply chain analytics folks will be pretty familiar with this area. Smart-devices can be programmed to automatically (with human overrides) respond to price changes by reducing or rescheduling electricity usage. Couple of differences here from standard RM/SCM problems : i) unlike supply chains that process manufactured widgets through warehouses and distribution centers, it is quite difficult to efficiently store and "ship" electricity using batteries, although the technologies are getting better each day. Thus, the electricity we use is probably produced less than a second ago, and marginal costs can spike during peak periods ii) electricity tends to be incredibly inelastic, making it stubbornly resistant to pricing changes, unlike say, smart-phones.

We noticed that prior approaches that apply peak-hour "congestion" pricing tended to 'migrate' rather than mitigate peaks. By carefully combining peak and off-peak pricing with accurate short-term load forecasting, and jointly optimizing the entire price profile, it is possible to proactively flatten the overall predicted load profile by inducing customers to make small shifts in their usage. Even a small peak shift-reduction during high-load days can result in a lot of savings. In fact, our experiment using actual Smart-Grid data showed that even a half a percentage point peak reduction using optimization could potentially lead to more than a 25% reduction in cost, which can benefit both the customers, as well as the utility companies.

Smart-Grid Control
Among the variety of problems solved here, researchers are also looking at the security-constrained optimal power flow that aims to minimize the total cost of system operation while satisfying certain contingency constraints.This smart-grid formulation extends the standard optimal power flow (OPF) problem, which determines a cost-minimal generation schedule cost while satisfying hourly demands, as well as energy and environmental limits, and meeting network security goals. Optimization methods used here include Benders decomposition, as well as Lagrangian multiplier techniques. Some of the newer variations employ distributed algorithms that are designed to work on a massive scale.

These are just a few samples that caught my attention. There are a variety of other problem areas being addressed (e.g. batteries, renewable energy sources, micro-grids), all of which perform some type of an optimization.

Saturday, October 26, 2013

Operations Research for the SmartGrid - 1

A popular joke in my undergrad campus at IIT-Madras used to be "why is the large water tank in our campus not used? Answer: the design engineers did not take the weight of water into account". The legend may be as real as the croc in the campus lake, but newspaper reports a few days ago quoted a US government spokesperson saying that the 'heath insurance website worked correctly, but just did not take the volume into account'. I'm sure a lot more attention was paid to the voters within the sophisticated analytical models used during the 2012 elections. Volume was not a problem then, somehow. Actions reflect priorities, as Gandhi said. So what are the priority areas in Smart-Grid research?

I recently attended the IEEE SmartGridComm 2013 international conference in the beautiful city of Vancouver, Canada. (A very brief historical tangent: From my Indian-American immigrant perspective, Vancouver is also a somber reminder of the discrimination that was once practiced by the US and Canadian governments, exemplified by the Komagata Maru incident). The paper presentations were refereed entries, uniformly of high quality, and largely focused on the dizzying science and technology associated with the various elements of the smart-grid (electric vehicles, batteries, wind, solar, communications, security, ...). Marry this with 'Big Data' and you get the convoluted buzz of two 'hyperbolic' distributions. Personally speaking, the glaring problem was this: the tech part felt overcooked, and the human part, somewhat overlooked, save for this five-minute talk, and the excellent keynote talks, which emphasized the latter (a favorite keynote comment described the important and immediate practical problem of 'transmission optimization' as the drunken uncle of the smart grid - largely ignored, but full of smart ideas). I found that several others at the conference too shared an opinion: the single most important component of the Smart-Grid remains the people for whom it is being built in the first place. If anything, understanding their behavior and impact is more important than ever before.

The world of electrical system modeling is full of elegant math that manage electrons that flow through circuits obediently as dictated by the equations. These models match up relatively well with reality (even imaginary numbers work here). In contrast, real world ORMS projects usually begin with people's real and changing requirements, and culminates in finding lasting solutions for real people, using noisy and incomplete SmallData. Unlike widgets, packets, and electrons, the goal of accurately modeling human response largely remains an open challenge, and the temptation to simply ignore this component of the SmartGrid is strong. However, the empirical, perhaps paradoxical, lesson I've learned the hard way is that the more effectively we want to mechanize, automate, and optimize systems by reducing or eliminating manual intervention (i.e. save humans from humans, a la Asimov's robots), the more practically important it becomes for our optimization models to take into account the behavior of, and the implications for all the human stakeholders, upfront. Be it workforce scheduling, Big data analytics, or the SmartGrid, an ahimsa-based multi-objective approach that also minimizes harm or maximizes benefit to the human element and blends harmoniously with the environment is likely to be more sustainable. Which is another way of saying: SmartGrid is one heck of an OR opportunity and I'm glad to be a small part of this journey.

The next part of this series will review some interesting SmartGrid optimization problems.

Wednesday, October 23, 2013

Time-constrained Technical Talks

Just jotting down some thoughts while attending the IEEE SmartGridComm conference in Vancouver, Canada. The talk duration here is roughly the same as that at INFORMS, about 20 minutes. There were plenty of talks on EVs (electric vehicles) in terms of their impact on the grid, locating charging stations, charging strategies, etc. I blogged about the Tesla routing problem - a very simple treatment purely out of curiosity - Smart-grid researchers have taken a variety of such EV related optimization problems to much more sophisticated levels. The most interesting feature of this SGComm edition was the introduction of 'Lightning Talks' of five minutes duration at lunch time, buzzer controlled. Given my extremely limited background in power systems and electrical engineering, I attended these five-minute talks for the novelty factor, and betting that nobody would present anything too complicated in five minutes. Of the 8 talks, 2 finished 1-2 minutes ahead of time, 2 were buzzer-beaters (nice!), and 4 violated the time-limit.So 50% of the time, the knapsack constraint was satisfied (half of that, tightly).

INFORMS may consider adding this feature in their next edition. After all, 'the elevator pitch' is an important part of OR soft skills. The talks were quite informative and the talkers cut to the chase and spend their scarce resource (time) trying to convey the one or two key ideas rather than to walk through excruciating technical details. The best talk was by Naeem, a researcher originally from Tanzania (where 97% of the villages have no electricity), who, in five-ish minutes, talked about how he came up with a micro-grid solution for villages that used diesel generators to provide electricity for lighting, some Jugaad-type ideas, and using Sim-card based methods for managing payments. Quite brilliant. Here's a link, and be sure to google his work. My fifteen minutes is up.

Tuesday, October 15, 2013

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)

Friday, October 4, 2013

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

Tuesday, October 1, 2013

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.

Friday, September 20, 2013

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
 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(M2) 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).

Wednesday, September 4, 2013

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

Sunday, September 1, 2013

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.

Sunday, August 25, 2013

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

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.