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:

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