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

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.