In Basketball, fouls are allowed up to a limit, and results in automatic penalties that turn into potential baskets and/or getting fouled out, once the limit is breached. Therefore, hoops foul-rules represent a capacitated model that comes with a marginal cost (dual value) and players have to pay a shadow price per foul and have to smartly manage this dual cost along as the game reaches its climax. In soccer, however, the foul model is uncapacitated, with little penalty unless it is a hard foul that invites a yellow or red card. In fact, soccer appears provide a net incentive to commit cynical and tactical fouls. Consequently, you often end up with foul-a-minute matches like the Brazil-Colombia world cup clash, where the game stops every few minutes and kills the momentum.
It's just not cricket
Soccer, like cricket, leaves part of the how ethically the game is played to the players. Cricket does this even more, and I personally love this decentralized approach that requires every individual to take responsibility for their actions to protect the integrity of their sport and their character (since it represents a dharma-karma like way of dealing with ethics), but off late, we see in both sports that this 'spirit of the game' has been sacrificed precisely when the stakes are the highest. Therefore, some centralized penalty approach that the American way of life prefers may be brought in to restore balance, unless the teams can reform themselves. I personally prefer a capacitated foul model in soccer.
Saturday, July 5, 2014
Wednesday, May 21, 2014
Predicting the Indian Elections - A Win for Data Science
The exit polls for the recently concluded Indian elections threw up a spectrum of results. Several Cable-TV networks ran their own polls, most of their numbers falling within a seemingly reasonable range, barring a public research group called 'Todays Chanakya', whose numbers were literally off the charts, predicting a massive win for Narendra Modi. People began to take averages of these polls to come up with an 'expected result', and many of these 'poll of polls' excluded TC's result as an outlier, discarding it as unbelievable.
I spent quite a bit of time looking at the meager information provided in the todayschanakya.com (TC) website before the results were announced. Buzz-words aside, what caught my attention was the meticulous attention they paid toward obtaining a representative data sample in every single constituency. Their prior track record in predicting elections in India was simply stunning. In a recent state election too, their prediction was an outlier, and turned out to be accurate. This data sampling step is important, especially given the incredibly diverse nature of India's population. Translating projected vote-shares into actual seats won in India's 'first past the post' system is an incredibly daunting problem. If your sample is even slightly messed up, then your seat predictions can be way off, regardless of the sophistication of the predictive analytics you employ. Human judgment and domain expertise is critical.
As this useful blog points out, it's not about 'sampling error', but sampling bias. And once we see this, it is not difficult to see why the English TV networks of India, virtually every single one a willing and well-compensated participant in the witch hunt of Narendra Modi since 2002, miserably fail in their predictions, time and again. Their reporting has rarely been fact-driven, and is usually ratings-driven. Few, if any on their payroll, are trained in the rigorous scientific method. Reporters appear to be hired based on ideology, west-accented English-speaking ability, and political connections rather than merit or technical proficiency. So, when by force of habit, you look for a sample that you like, then you will only get the predictions you want viewers to see in your TV shows, which has little to do with reality. The media witch hunt against Modi, like their exit polls, as is now known, was never fact-driven from day one. It was doomed from the start. After this election, few will take their "predictions" seriously again unless they reform.
TC's predictions were quite accurate. Modi indeed won in a landslide as they predicted, with the incumbent Nehru dynasty (aka "UPA" coalition) whose corruption almost surely qualifies as a crime against humanity, getting deservedly annihilated. On election day, at around 1-2:00 AM EST, while following the election trends, UPA was leading in about a hundred of the 543 seats up for grabs, way higher the predicted range of 61-79 seats that TC predicted they would get. However, as the day progressed, it was amazing to see UPA's leads petering out one by one, as if an invisible rope was magically pulling it back into the predicted range. Statistical destiny. Only two people appeared to be convinced about the result before May 16. TC, who adopted a scientific approach to gathering and analyzing data, and Narendra Modi, who created the history in the first place. Both of them dared to be different and put their reputations on the line, and were worthy winners.
This election result and Modi becoming the Prime Minister of India has taught many of us a scientific lesson. Data science is about being guided by facts, not emotion, or prejudiced opinion, or preferred outcome. Carefully constructed fact-driven methods are less likely to fail. Gujarat's development, both rural and urban, spearheaded by Modi for 12 years, is real, and cannot be falsified. It happened, and it is there to be seen regardless of what the New York Times tells you. I blogged in 2012 that the heavy-lifting done in Gujarat may pay rich dividends in the future. The people there lived that development and they knew, and the thousands of migrants returned from Gujarat to other states to speak about their experience there. TC's data sample accurately reflected this reality. The media-heads sitting in Delhi, London, and New York were high on ideology-meth, low on fact. Few visited the state of Gujarat to make a factual assessment. Some of the open-minded critics who did, ended up becoming Modi's strongest supporters. Not surprisingly, his fact-driven campaign won him every single parliamentary seat there. The amazing number of Indians cutting across religious, class, language, age, gender, and geographical 'barriers', who voted for Modi, too cannot be brushed aside. Facts cannot be ignored until time-travel becomes practical.
And here's another prediction, an easy one. Modi will probably become India's best, and most unifying leader since Mahatma Gandhi, if he isn't already that. If, as the Nehru dynasty says, "power is poison", India has surely found their Shiva.
I spent quite a bit of time looking at the meager information provided in the todayschanakya.com (TC) website before the results were announced. Buzz-words aside, what caught my attention was the meticulous attention they paid toward obtaining a representative data sample in every single constituency. Their prior track record in predicting elections in India was simply stunning. In a recent state election too, their prediction was an outlier, and turned out to be accurate. This data sampling step is important, especially given the incredibly diverse nature of India's population. Translating projected vote-shares into actual seats won in India's 'first past the post' system is an incredibly daunting problem. If your sample is even slightly messed up, then your seat predictions can be way off, regardless of the sophistication of the predictive analytics you employ. Human judgment and domain expertise is critical.
As this useful blog points out, it's not about 'sampling error', but sampling bias. And once we see this, it is not difficult to see why the English TV networks of India, virtually every single one a willing and well-compensated participant in the witch hunt of Narendra Modi since 2002, miserably fail in their predictions, time and again. Their reporting has rarely been fact-driven, and is usually ratings-driven. Few, if any on their payroll, are trained in the rigorous scientific method. Reporters appear to be hired based on ideology, west-accented English-speaking ability, and political connections rather than merit or technical proficiency. So, when by force of habit, you look for a sample that you like, then you will only get the predictions you want viewers to see in your TV shows, which has little to do with reality. The media witch hunt against Modi, like their exit polls, as is now known, was never fact-driven from day one. It was doomed from the start. After this election, few will take their "predictions" seriously again unless they reform.
TC's predictions were quite accurate. Modi indeed won in a landslide as they predicted, with the incumbent Nehru dynasty (aka "UPA" coalition) whose corruption almost surely qualifies as a crime against humanity, getting deservedly annihilated. On election day, at around 1-2:00 AM EST, while following the election trends, UPA was leading in about a hundred of the 543 seats up for grabs, way higher the predicted range of 61-79 seats that TC predicted they would get. However, as the day progressed, it was amazing to see UPA's leads petering out one by one, as if an invisible rope was magically pulling it back into the predicted range. Statistical destiny. Only two people appeared to be convinced about the result before May 16. TC, who adopted a scientific approach to gathering and analyzing data, and Narendra Modi, who created the history in the first place. Both of them dared to be different and put their reputations on the line, and were worthy winners.
This election result and Modi becoming the Prime Minister of India has taught many of us a scientific lesson. Data science is about being guided by facts, not emotion, or prejudiced opinion, or preferred outcome. Carefully constructed fact-driven methods are less likely to fail. Gujarat's development, both rural and urban, spearheaded by Modi for 12 years, is real, and cannot be falsified. It happened, and it is there to be seen regardless of what the New York Times tells you. I blogged in 2012 that the heavy-lifting done in Gujarat may pay rich dividends in the future. The people there lived that development and they knew, and the thousands of migrants returned from Gujarat to other states to speak about their experience there. TC's data sample accurately reflected this reality. The media-heads sitting in Delhi, London, and New York were high on ideology-meth, low on fact. Few visited the state of Gujarat to make a factual assessment. Some of the open-minded critics who did, ended up becoming Modi's strongest supporters. Not surprisingly, his fact-driven campaign won him every single parliamentary seat there. The amazing number of Indians cutting across religious, class, language, age, gender, and geographical 'barriers', who voted for Modi, too cannot be brushed aside. Facts cannot be ignored until time-travel becomes practical.
And here's another prediction, an easy one. Modi will probably become India's best, and most unifying leader since Mahatma Gandhi, if he isn't already that. If, as the Nehru dynasty says, "power is poison", India has surely found their Shiva.
Wednesday, May 14, 2014
Indian elections 2014: Long words, short story
Can long, archaic words be used to maximize overall brevity (and levity)? Take the 2014 Indian general elections that recently concluded. Although the final results will come out on May 16 (the amazing Narendra Modi as Prime Minister), exit polls already give us this clear-enough picture:
India has understood that the phoney "Idea of India" brand of secularism is nothing but antidisestablishmentarianism in disguise, and we are witness to the historical floccinaucinihilipilification of the Nehru-dynasty by the Indian voter.
India has understood that the phoney "Idea of India" brand of secularism is nothing but antidisestablishmentarianism in disguise, and we are witness to the historical floccinaucinihilipilification of the Nehru-dynasty by the Indian voter.
Tuesday, March 4, 2014
Traveling Salesman Problem in a Portrait?
I'd planned to stop blogging until May this year to do my small bit in helping Narendra Modi become the next Prime Minister of India in the Indian general elections to be held very soon - one that will determine the future of my family there, as well as the destiny of 1.2 Billion Indians. India has suffered from a curse of culpable silence in the last ten years, but now it seems, that is changing, thanks to inspiring examples like these that asks people to come out and 'Vote for India' (thanks to @sarkar_swati, faculty at U-Penn, for sharing this video).
------------------------------------------------------------------------------
By sheer coincidence, this brief blog, like the previous one, is related to Asian (Japanese) art, and one i felt 'compelled' to do. Thanks to @SimoneCerbolini for sharing this beautiful portrait on twitter. What is interesting about this art is that it was done, as Simone tweets, using "a single thread wrapped around thousands of nails. Artwork "Mana" by Kumi Yamashita"
The artist, Kumi Yamashita, has a facebook page, and here is another picture from there.
The effect is stunning, and one marvels at the human 'cognitive shift' that convinces us that within this collection of thread and nails, is a lady. Here is a brilliant talk by neuroscientist V. S. Ramachandran (Director, Center for Brain and Cognition, UC, San Diego) on
From the operations research perspective, we gravitate toward the mathematical problem hidden in this portrait: determining the least length of thread to traverse through all these nails. A mathematical optimization model that can be used to answer this question is the celebrated 'Traveling Salesman Problem' (TSP), which is known to be difficult to solve, in theory. In practice, however, extremely large instances have been solved to provable optimality.
Here is another page that displays a collection of pictures from the artist's 'constellation series'. It also includes this ultra-close up that lets us see how the threading really progresses at the micro-level.
Each nail is traversed multiple times, and a greater density of thread is used to create a darker shade (e.g. the eye and the brow). Additionally, there appears to be a greater density of nails in that area. Can a thread-traversal path generated by a TSP solver (e.g. concorde) produce a similar effect to the eye and the brain? I'm not sure, although it may still produce 'a reasonable picture of a lady'. If the density of nails is increased in these areas, then perhaps the TSP-artwork may do a good job. Alternatively, it may be possible to modify the TSP network structure to induce such an effect.
------------------------------------------------------------------------------
By sheer coincidence, this brief blog, like the previous one, is related to Asian (Japanese) art, and one i felt 'compelled' to do. Thanks to @SimoneCerbolini for sharing this beautiful portrait on twitter. What is interesting about this art is that it was done, as Simone tweets, using "a single thread wrapped around thousands of nails. Artwork "Mana" by Kumi Yamashita"
The artist, Kumi Yamashita, has a facebook page, and here is another picture from there.
The effect is stunning, and one marvels at the human 'cognitive shift' that convinces us that within this collection of thread and nails, is a lady. Here is a brilliant talk by neuroscientist V. S. Ramachandran (Director, Center for Brain and Cognition, UC, San Diego) on
From the operations research perspective, we gravitate toward the mathematical problem hidden in this portrait: determining the least length of thread to traverse through all these nails. A mathematical optimization model that can be used to answer this question is the celebrated 'Traveling Salesman Problem' (TSP), which is known to be difficult to solve, in theory. In practice, however, extremely large instances have been solved to provable optimality.
Here is another page that displays a collection of pictures from the artist's 'constellation series'. It also includes this ultra-close up that lets us see how the threading really progresses at the micro-level.
Each nail is traversed multiple times, and a greater density of thread is used to create a darker shade (e.g. the eye and the brow). Additionally, there appears to be a greater density of nails in that area. Can a thread-traversal path generated by a TSP solver (e.g. concorde) produce a similar effect to the eye and the brain? I'm not sure, although it may still produce 'a reasonable picture of a lady'. If the density of nails is increased in these areas, then perhaps the TSP-artwork may do a good job. Alternatively, it may be possible to modify the TSP network structure to induce such an effect.
Saturday, January 25, 2014
Building the Unsolvable Maze
I came across a tweet via Simon Singh, famous writer of books based on math-topics. I've read a couple of them: 'Fermat's last theorem' and 'The code book'. His tweet points to a picture of an amazing maze hand-drawn over 30 years ago in Japan. Although it is supposed to be 'unsolvable', some comments there claim that it could be solved very quickly if it was made publicly available. Among the very first papers I read after coming to the U.S to study traffic engineering (to understand the reasons for India's chaotic, maze like traffic) was about Moore's algorithm entitled "shortest path through a maze". Mathematically, the shortest path problem formulation has a couple of properties of small interest in the context of this discussion. It has no duality gap, and is totally unimodular: It is sufficient to solve the continuous 'relaxation' to recover an integral optimal solution to the primal or dual formulation. Wikipedia has a page on maze-solving algorithms. Interesting as the optimization problem of finding an 'optimal route' to 'escape' this maze is, a more interesting question to me personally was: why would someone hand-build such an intricate maze over years; and then why not claim any credit for it? I have tried to interpret this based on my understanding of the Indian way.
(source link and main article at: http://imgur.com/gallery/4kyvVVb)
The intense concentration required for such a task is surely daunting: to at once elevate one's consciousness while also dissolving one's aham (ego) that hinders the mind from systematically growing a complex maze whose paths increase rapidly over time as more forks and merges are constructed. Paths that stop even as they begin, paths that ultimately lead nowhere, paths where you travel for a while, only to discover that you are back where you were before... and then after a lot of calm, refined, and introspective searching (not suffering), finding a path that leads one to satya (ultimate reality/truth) that transcends the maya of the maze that held us in its thrall. A path that dissolves the noisy duality between the world within the maze and without, uniting them harmoniously into a unified whole, even as the space enclosed within the maze maintains a provisional identity within this overall unity. And then perhaps a realization that there could be a pluralism of such (alternative optimal) transcendental paths to satya. A harmonious unity within multiplicity that celebrates its diversity, rather than a synthesized unity derived by optimizing the goal of orderly sameness. The latter produces an efficient monoculture, but one that invariably regards pluralism as a seed of chaos. The former, integral unity best represents the nature of the underlying philosophical unity of India that has continually preserved and refined its dharma civilization over several thousand years. This forms the dharmic basis for any reasonable 'idea of India'. I look forward to reading Rajiv Malhotra's new book on this subject.
Journeys that traverse such a path have led to amazing discoveries that enlightened the world, and will continue to do so. Perhaps it produced this captivating art that simultaneously appeals to the casual observer, the artist, the seeker, and the analyst alike; yet each of us seeing only a partial facet of its underlying truth. A work of art to which its 'creator' deliberately did not append a signature to, and claim ownership of, perhaps unwilling to disturb it's harmony. That is the way of the Yogi.
Dedicated to Rajiv Malhotra on the occasion of India's 65th republic day.Thank you.
(source link and main article at: http://imgur.com/gallery/4kyvVVb)
The intense concentration required for such a task is surely daunting: to at once elevate one's consciousness while also dissolving one's aham (ego) that hinders the mind from systematically growing a complex maze whose paths increase rapidly over time as more forks and merges are constructed. Paths that stop even as they begin, paths that ultimately lead nowhere, paths where you travel for a while, only to discover that you are back where you were before... and then after a lot of calm, refined, and introspective searching (not suffering), finding a path that leads one to satya (ultimate reality/truth) that transcends the maya of the maze that held us in its thrall. A path that dissolves the noisy duality between the world within the maze and without, uniting them harmoniously into a unified whole, even as the space enclosed within the maze maintains a provisional identity within this overall unity. And then perhaps a realization that there could be a pluralism of such (alternative optimal) transcendental paths to satya. A harmonious unity within multiplicity that celebrates its diversity, rather than a synthesized unity derived by optimizing the goal of orderly sameness. The latter produces an efficient monoculture, but one that invariably regards pluralism as a seed of chaos. The former, integral unity best represents the nature of the underlying philosophical unity of India that has continually preserved and refined its dharma civilization over several thousand years. This forms the dharmic basis for any reasonable 'idea of India'. I look forward to reading Rajiv Malhotra's new book on this subject.
Journeys that traverse such a path have led to amazing discoveries that enlightened the world, and will continue to do so. Perhaps it produced this captivating art that simultaneously appeals to the casual observer, the artist, the seeker, and the analyst alike; yet each of us seeing only a partial facet of its underlying truth. A work of art to which its 'creator' deliberately did not append a signature to, and claim ownership of, perhaps unwilling to disturb it's harmony. That is the way of the Yogi.
Dedicated to Rajiv Malhotra on the occasion of India's 65th republic day.Thank you.
Sunday, January 19, 2014
The King and the Vampire - 3: The Flaw of Optimizing-On-Average
This is the third episode of the 'King Vikram and the Vetaal' series.
(link: juneesh.files.wordpress.com)
Dark was the night and weird the atmosphere. It rained from time to time. Eerie laughter of ghosts rose above the moaning of jackals. Flashes of lightning revealed fearful faces. But King Vikram did not swerve. He climbed the ancient tree once again and brought the corpse down. With the corpse lying astride on his shoulder, he began crossing the desolate cremation ground. "O wise King, it seems to me that your ministers are sometimes too quick in taking policy decisions based on an average scenario, ignoring the distribution. But it is better for you to know that such decisions invariably results in complaints. Let me cite an instance. Pay your attention to my narration. That might bring you some relief as you trudge along," said the Betaal, which possessed the corpse.
The retailing vampire went on:
Once there lived a retailer who always optimized his scarce resource constrained planning problems based on an average planning week. It was a quick and easy heuristic, and he claimed that it worked just fine. One day, an OR practitioner challenged this assumption, quoting points from the well-known 'flaw of averages' book, and said that with a bit more effort, and without increasing the problem size much, one can generate true optimal merchandising decisions by including all scenarios, using CPLEX. This would also be relatively more robust in reality compared to optimizing to the average. The retailer replied that while this issue was of theoretical importance, it did not matter much in practice, unless he saw some hard evidence. The practitioner decided to make an empirical point and proceeded to evaluate a number of historical instances by evaluating the recommendations generated by these two approaches over all the scenarios. In 75% of the instances, the practitioner's method yielded relatively better metrics, while in 25% of the cases, the retailer's average method did better. The retailer took one look at the results and said that the experimental setup was erroneous, inconclusive, and remained unconvinced.
(pic source link: omshivam.files.wordpress.com)
Dark was the night and weird the atmosphere. It rained from time to time. Eerie laughter of ghosts rose above the moaning of jackals. Flashes of lightning revealed fearful faces. But King Vikram did not swerve. He climbed the ancient tree once again and brought the corpse down. With the corpse lying astride on his shoulder, he began crossing the desolate cremation ground. "O wise King, it seems to me that your ministers are sometimes too quick in taking policy decisions based on an average scenario, ignoring the distribution. But it is better for you to know that such decisions invariably results in complaints. Let me cite an instance. Pay your attention to my narration. That might bring you some relief as you trudge along," said the Betaal, which possessed the corpse.
(pic source link: pryas.wordpress.com)
The retailing vampire went on:
Once there lived a retailer who always optimized his scarce resource constrained planning problems based on an average planning week. It was a quick and easy heuristic, and he claimed that it worked just fine. One day, an OR practitioner challenged this assumption, quoting points from the well-known 'flaw of averages' book, and said that with a bit more effort, and without increasing the problem size much, one can generate true optimal merchandising decisions by including all scenarios, using CPLEX. This would also be relatively more robust in reality compared to optimizing to the average. The retailer replied that while this issue was of theoretical importance, it did not matter much in practice, unless he saw some hard evidence. The practitioner decided to make an empirical point and proceeded to evaluate a number of historical instances by evaluating the recommendations generated by these two approaches over all the scenarios. In 75% of the instances, the practitioner's method yielded relatively better metrics, while in 25% of the cases, the retailer's average method did better. The retailer took one look at the results and said that the experimental setup was erroneous, inconclusive, and remained unconvinced.
So tell me King Vikram, Why did the retailer conclude the test setup was faulty? Was he correct in this assessment? Which method is better in the retailer's context? Answer me if you can. Should you keep mum though you may know the answers, your head would roll off your shoulders!"
King Vikram was silent, then closed his eyes, as if going into a Yogic trance in a moment of intense meditation. He reopened his eyes soon enough along with a smile, and then spoke: "Vetaal, unlike the last time, this one is pretty easy, so let's take the first question first.
1. The retailer felt the experimental setup was flawed because, if the practitioner's method truly yielded optimal solutions as claimed, then it should have done just as well or better in 100% of the instances.
2. However, the retailer was wrong because his old method optimized against constraints based on an average scenario. There is no guarantee that his decisions will be feasible to the original problem, over all scenarios. Therefore, in the instances where the old method did better, the recommendations had to be infeasible, since we cannot, of course, find a feasible solution better than an optimal one.
3. So we now know that the old method generated infeasible solutions at least 25% of the time. If we ignore these cases where we know it was surely infeasible, and look at the remaining 75% of the cases where it may have been feasible, it did worse 100% of the time due to a combination of suboptimality and overly-constrained instances.
In every case, the old method was either infeasible or suboptimal. The average-based heuristic must be discarded.
King Vikram was silent, then closed his eyes, as if going into a Yogic trance in a moment of intense meditation. He reopened his eyes soon enough along with a smile, and then spoke: "Vetaal, unlike the last time, this one is pretty easy, so let's take the first question first.
1. The retailer felt the experimental setup was flawed because, if the practitioner's method truly yielded optimal solutions as claimed, then it should have done just as well or better in 100% of the instances.
2. However, the retailer was wrong because his old method optimized against constraints based on an average scenario. There is no guarantee that his decisions will be feasible to the original problem, over all scenarios. Therefore, in the instances where the old method did better, the recommendations had to be infeasible, since we cannot, of course, find a feasible solution better than an optimal one.
3. So we now know that the old method generated infeasible solutions at least 25% of the time. If we ignore these cases where we know it was surely infeasible, and look at the remaining 75% of the cases where it may have been feasible, it did worse 100% of the time due to a combination of suboptimality and overly-constrained instances.
In every case, the old method was either infeasible or suboptimal. The average-based heuristic must be discarded.
No sooner had King Vikram concluded his answer than the vampire, along with the corpse, gave him the slip.
(pic source link: omshivam.files.wordpress.com)
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.
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.org, http://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.”
(source links: http://info.museumstoreassociation.org, http://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.
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):
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:
(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.
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.
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.
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.
Kindle book 2 (Advanced forecast-modeling textbook)
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.
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 |
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 |
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)
l ≤ 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.
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.
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.
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.
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.
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.
Subscribe to:
Posts (Atom)