Wednesday, May 29, 2013

Jugaad Innovation: Stuck in a Local Optimum

Updated July 5, 2013:
CNN link on Jugaad Innovation.

The book cover blurb sounded exciting: Do more with less. An alternative to risky expenditure-driven, resource-hungry growth using a "bottom up approach to frugal and flexible innovation". Endorsement from a salesforce.com CEO. No doubt, Jugaad is a useful concept - it's a Hindi word that implies a improvised and clever work-around, but there is such a thing as stretching an idea too far. Jugaad arises from the Indian way of doing "more with less" - possibly a public response to artificial scarcity induced by genocidal British colonization since the late 18th century when a resource-rich India's share of world GDP plummeted from 25% to a negligible quantity in a short time to turn it into from a knowledge and manufacturing economy into an agrarian, impoverished nation. A scarcity-driven economy that has been nurtured by Nehruvian socialist politics over the last 60+ years. However, the word itself ties in nicely with ideas in Operations Research that deal with the optimal allocation and utilization of scarce resources, and hence this post.

The book has some heart-warming and splendid examples of Indian innovation, which are nice to read. The remarkably decentralized and entrepreneurial nature of the workforce, and their seeming comfort in operating effectively within what appears as "chaos" to the external observer is one of the salient features of the native Indian economy. A discussion of the Indian practice of the "missed call" (the closest that mankind has come to 'half a bit' of information) adds humor. The authors could have lent depth to the book by exploring the deep-rooted cultural origins of the decentralization, and entrepreneurial spirit that drives the Indian way of doing things. They do make some useful comparisons between the profligacy and rigidity of some Western CEOs with the adaptive nature of the "jugaad entrepreneur". However, celebrating every success from Bharti airtel to PepsiCo's direct seeding to Mitticool (now that is really cool) as a win for "Jugaad" dilutes the message. When the book hyped the crappy 'Aakash' tablet, the populist, Indian government's tax-payer subsidized tablet for the unwashed masses (a cheaper and cynically sub-optimal alternative to constructing and maintaining primary schools), it was time to cry halt. Celebrating artificial scarce resource allocation, however efficiently done, feels like a cop-out.

Operations Research practice is not just about optimizing within constraints and declaring victory. Value can be unlocked by using OR to expose the more expensive bottlenecks in the system. Constraints that turn out to be artifacts must be eliminated whenever possible. I'm all for (also) 'thinking small', but not at the expense of losing the context.

Monday, May 20, 2013

Solve TRP, Drive Tesla

So the awesome and hyped Tesla Model S is beating Mercedes, BMW, and Audi in sales despite the $70K price tag. One problem is the current lack of charging stations required to recharge over long trips. CNNMoney reports:
"CNNMoney took a Tesla Model S on a test drive from Washington D.C. to Boston. The all-electric car drove 450 miles with two stops to recharge at Tesla's Supercharger stations in Delaware and Connecticut"



A second problem is that unlike conventional gasoline cars that can be refueled very quickly, charging can take a relatively long time, and adds significantly to your total travel time. In the near future, as the number of Teslas increase, the number of charging stations is likely to go up too. However, it will remain a sparse resource for some time. A future Tesla trip from New York to California will require many recharging stops, reminiscent of the old stagecoach problem during the Gold Rush era, which is used to illustrate the principles of Dynamic Programming.

Update: May30, 2013
Popular Mechanics reports:
"...the California-based EV automaker plans to expand its fast-charging "supercharger" network across the continental U.S. During today's announcement, Musk said New York to Los Angeles trips would be viable as soon as this winter. 

"When you get in a car you have the ability to go almost anywhere," Musk said. "That's what the supercharger network will do." 

The rollout will begin as soon as this summer, with the number of stations tripling to 27 nationwide by the end of June. In addition to increasing supercharger density along the already-established California and Mid-Atlantic coasts, Tesla will debut chargers in a handful of new metropolitan areas within the next few weeks, including Austin/Houston, Portland/Seattle, Boulder/Denver, and Chicago/Milwaukee. By the end of the year, Musk expects to to have "a couple hundred" superchargers spread across the U.S. and southern Canada, with as little as 80 to 90 miles between stations along the Altantic and Pacific coasts..."

Tesla Routing Problem
Given a road network G having a limited number of charging stations located at specific nodes, the Tesla Routing Problem (TRP) will have to:
Find the shortest feasible time path from origin O to Destination D in network G.

Feasibility requires the car to visit enough charging stations in a timely manner. Optimality requires that the sequence of visits be carefully selected such that the total time spent is kept to a minimum.

Total travel time = driving time + recharge time

This involves two decisions:
D1. Which recharging stations to visit en-route?
D2. How long to recharge at every pit stop?

Assumptions:
A1. The longer you recharge, the longer your available range (to a limit).
A2. All recharging stations are similar, and infinite capacity (no queuing!)
A3. Range is deterministic

Update on A2: The Tesla can charge on any outlet, but the time to recharge can vary depending on the source.

Clearly, optimally solving TRP involves the finding a solution to a Traveling Salesman Problem even in the special case of instantaneous recharge (Y=0).

(Updated September 2013: As mentioned in the comments, the general case is not a TSP in the network of charging stations. Here, the assumption is that stations are sparsely located and we visit each one along the way. The title is changed to reflect this distinction).

This is no different from the (milder) challenge faced by conventional car drivers in unfamiliar areas where gas stations may be hard to come by (see this old post). Charge cannot be carried in Jerry-cans. The  shortage of charging stations does make every long Tesla trip a non-trivial problem to manage. Tesla owners have to deal with a NP-Hard Optimization Problem (Heh) on every such trip, but in practice, it should not be difficult to find good quality, feasible TRP solutions.

The recharge time makes the TRP a bit more interesting. If two stations are close to each other, we don't have to recharge fully, and just need the minimum to reach the next stop - or perhaps we recharge fully, which allows us to reach a station that is further away but turns out to be more time-effective, overall. Clearly, these two decisions appear to be interlinked and may need to be jointly optimized. D1 is a binary decision variable X(i) - we either visit or don't visit a station at node X(i), whereas D2 is a semi-continuous variable Y(i) conditional on D1:

Y(i)  U.X(i)
where U = maximum recharge time.

Another interesting and maybe even useful problem for Tesla-makers to solve is where to add new charging stations on the network G over time. What is the minimum number and location of stations required to guarantee feasible solutions to any TRP in the 48 states of continental US? How will stations deal with congestion in the future? and so on ...

I haven't driven a Tesla yet but I wouldn't mind relocating my office to inside one and telecommute.

Monday, May 6, 2013

Guesstimation in Optimization and Analytics

Guesstimation
Browsing through the various examples examined in the 2008 book 'Guesstimation', it is apparent that the basic ideas behind this approach of "solving the world's problems on the back of a paper napkin" are useful for analyzing real-life optimization and analytics instances. Whether we are looking at (i) Smart-grid optimization ("how many hours does it take to charge an electric car"), or (ii) Hazmat routing ("what is the risk of dying per unit mile of road") or (iii) environmental problems ("how much farmland will it take to convert all gasoline cars to ethanol"), guesstimating values can be critical to effective model formulation in the absence of precise information. Guesstimation is a 'small data' method that can improve the effectiveness and performance of our 'big data' analytics.

Optimization
Let's look at an 'elastic' linear programming formulation:
LP: Minimize c.x + P.s
A.x - s <= b
l <= x <= u, s >= 0
where we've added artificial variables 's' to ensure feasibility of LP for any bound feasible 'x'. Often times, exact values for b, c, l, u, or portions of A are not available. Furthermore, we allow artificial variables to be active at some high but as yet unknown penalty rate of 'P'. We often end up guesstimating these values in industrial applications since many of these values are not known accurately.

Example (i) in the previous paragraph gives us a charge rate per car (a component of 'A' matrix). if 'x' is the number of cars to be charged, and 'b' is an upper bound on the time available and 'c' the cost of electricity for that duration, we can predict the 'ballpark' cost incurred and the charge stored. Similarly, example (ii) gives us the average risk per unit mile as a cost coefficient 'c'. By extending this calculation to denote high and low risk arcs in a network, we have an initial minimum risk network path optimization formulation at hand. Finally, example (iii) gives us an unconstrained resource requirement. This value allows us to quickly assess the impact of adding a resource constraint.

Thou shalt always Guesstimate!
Direct uses of guesstimation in practical optimization include the calculation of tighter bounds (l, u) for decision variables, and the smallest valid values for the big-M numbers that riddle integer programming formulations. If we think of (u - l) as a measure of our ignorance about the as yet unknown optimal 'x', guesstimating tight bounds is akin to maximally reducing its "prior variance". While guesstimation in the book is done using feasibility calculations, we can and should incorporate optimality considerations to obtain sharper bounds for such unknown variables. Using solver default (0, infinity) values is lazy and bad practice. Also, spending some time to improve bounds often gives us insight into the nature of the optimal solution, and which constraints are likely to be more restrictive, and helps catch modeling bugs earlier.

Example 1: what is the cost of not scheduling a crew for an airline flight?
In airline crew scheduling, the flights in a schedule are partitioned among crew pairings (see this post for a problem description). Every flight must be covered by exactly one pairing. This is a hard constraint, but in practice, we have to temporarily employ its elastic form of the type described above, and penalize violations via 'P'. How do we determine an appropriate penalty value? This would be the cost of leaving a flight uncovered. Such flights have to be covered by a reserve crew, which comes at a certain cost that can be calculated and is typically smaller than some default value we may have otherwise chosen. The dual variable value associated with an uncovered flight in an optimal LP solution attains a value close to 'P'. Any new column (x(j)) generated that covers this flight will subsequently will have a reduced cost of order (c(j)-P), and so on. Good guesstimation of P helps in producing manageable reduced costs, and accelerates algorithm convergence.

Example 2: what is the price elasticity of point-and-shoot digital cameras?
Price elasticity is a dimensionless (negative) quantity that gives us the expected percentage change in sales for a percentage change in price. We can expect that this value will be more than that for electricity, grocery, and dairy items, which are essential items that people are less willing to give up when price is hiked, and are likely to be inelastic (less than a percent drop in sales for a percent increase in price, say -0.5). The value will be lower than that of highly discretionary purchases like fashion apparel or leisure airline tickets (which have an elasticity of -4 to -2). The geometric and arithmetic mean of 3.0 and 0.5 gives us a range (-1.8, -1.2). A data-driven estimation of this value should be compared against this guesstimate as a sanity check. For example, if regression models on a data sample estimates an 'optimized' elasticity parameter value of -5 or -0.1, we may want to double check our modeling, or run the risk of producing wild predictions.

Another use of guesstimation is in generating plausible random optimization instances to demonstrate the effectiveness of new NP-Hard algorithms for a certain problem class if only limited real-life data is available. It can help weed out weird and contrived instances that skew the degree of difficulty of the problem and make it seem much harder than it actually is in reality.