First the original story today doing the rounds on the Internet on bees solving a TSP while traversing a sequence of flowers for nectar. Their approach resembles the ant-colony / swarm-optimization approach, and while this 'bee story' is truly astounding, the author further states the computers have to explore every possible path to select the best and that takes days. Obviously, they did not hear about Operations Research, and the fantastic work done on inventing efficient algorithms for solving gigantic and difficult TSP problems to provable (near-) global optimality in quick time. The fantastic book on TSP by Dr. Applegate, Dr. Bixby, et al. gives us a fascinating blow-by-blow account of the work on this topic from the TSP past to the present. You can even try out their Concorde solver. The state-of-the-art is truly amazing and based on decades of breakthrough ideas.
Yet, article after article that seem to come out every couple of years assumes that if a problem is NP-Hard, then it is almost "impossible to solve efficiently in practice" and enumeration is the only way. Nope. A pure application of software programming and hardware strategies certainly does not work or scale. OR leads the way.
An incredible amount of success in OR practice has come via successfully tackling precisely such large-scale and ultra-complex NP-Hard problems. Large-scale TSP-structured problems have been routinely solved in Supply-chain planning, vehicle routing, aircraft routing, etc. Not only are problems solved well and quickly, but we also know how well and how much improvement is still possible. These small optimality gaps matter. A TSP solution that is 1% closer to optimality may save a company another million dollars.
Heuristics of unknown quality based on bees and ants are nice, but they don't really tell you if there is another solution that could your save your company another 10%. And if you were to change your input parameters, it may return an entirely different solution that makes such approaches largely unpractical for use within products. And adding a constraint the prohibits certain paths may well make such approaches useless. This Tab has discussed the practical problems with using such heuristics in previous posts here, and you will find more in Dr. Trick's OR Blog when TSP was "solved" last year by creatures with even smaller brains, i.e. bacteria :-)
There's even TSP art. Check this out as well. Let's give O.R. and humans some credit please!
Monday, October 25, 2010
Saturday, October 23, 2010
Maximizing Dignity: The Traveling Angel Problem
Can one person feed 400 hungry mouths in the temple city of Madurai in South India, every day of the year?
Mr. Krishnan is a good human being. In today's world, we have to start looking for those first before we start looking for heroes. I was happy to see that he was nominated for the "CNN hero of the year" award for this work. Hopefully this publicity will translate into more help for his operation. The talented Mr. K, at the age of 22, was all set to be a five-star chef in Switzerland seven years ago, but chucked all that when he saw an hungry old man in his home town doing the unthinkable. Since then, without taking a single day off, he is up at 4am to cook tasty and fresh vegetarian food. He then drives around the town of Madurai (most famous for it's amazing Meenakshi Amman Kovil - the temple of a 1000 pillars) feeding the destitute and the hungry. He often hand-feeds them and gives them haircuts along with a meal. His focus is on restoring the dignity of a human being. Is that not fundamental? Simply put, in this temple city, Krishnan is the Goddess Annapoorani to these castaway people. Contribute generously to the Sakthi foundation's Askhaya trust if you can (paypal accepted too. cool). Even a small amount goes a long way.
O.R. is the far less important part here, but one wonders how this amazing person chooses his 125 mile driving route? He has a limited quantity of freshly prepared food stocked in his van that has to reach 400 desperately hungry mouths all over his city as effectively and efficiently as possible. OR should be helping in such practical situations. We can't always be for and about profit-maximization models for corporations, weapons and target acquisition for the military, or abstract academic problems. The logistics of Mr. K's 'meals on wheels' operation contains a classical vehicle routing / traveling salesman problem element. A more efficient operation and utilization of scarce resources means that more people can be fed and more shattered lives can rebuilt and dignity restored. The google map of the city of Madurai is shown below.
View Larger Map
Who will optimize Krishnan's supply chain?
Mr. Krishnan is a good human being. In today's world, we have to start looking for those first before we start looking for heroes. I was happy to see that he was nominated for the "CNN hero of the year" award for this work. Hopefully this publicity will translate into more help for his operation. The talented Mr. K, at the age of 22, was all set to be a five-star chef in Switzerland seven years ago, but chucked all that when he saw an hungry old man in his home town doing the unthinkable. Since then, without taking a single day off, he is up at 4am to cook tasty and fresh vegetarian food. He then drives around the town of Madurai (most famous for it's amazing Meenakshi Amman Kovil - the temple of a 1000 pillars) feeding the destitute and the hungry. He often hand-feeds them and gives them haircuts along with a meal. His focus is on restoring the dignity of a human being. Is that not fundamental? Simply put, in this temple city, Krishnan is the Goddess Annapoorani to these castaway people. Contribute generously to the Sakthi foundation's Askhaya trust if you can (paypal accepted too. cool). Even a small amount goes a long way.
O.R. is the far less important part here, but one wonders how this amazing person chooses his 125 mile driving route? He has a limited quantity of freshly prepared food stocked in his van that has to reach 400 desperately hungry mouths all over his city as effectively and efficiently as possible. OR should be helping in such practical situations. We can't always be for and about profit-maximization models for corporations, weapons and target acquisition for the military, or abstract academic problems. The logistics of Mr. K's 'meals on wheels' operation contains a classical vehicle routing / traveling salesman problem element. A more efficient operation and utilization of scarce resources means that more people can be fed and more shattered lives can rebuilt and dignity restored. The google map of the city of Madurai is shown below.
View Larger Map
Who will optimize Krishnan's supply chain?
Monday, October 18, 2010
Chakravala - Decision Analytics in Ancient India
More than two thousand years ago, many priests in India had to double up as mathematicians. They practiced the Sanathana Dharma, 'the eternal way of ethical living' (or Hinduism as it is popularly known today). Hinduism is richly influenced by nature, as well as the earthly and celestial elements, and fire rituals were quite important in those times. Careful attention was paid to the geometry of the altar, since different shapes were required depending on the objective of the ritual. This naturally gave rise to analytics, and a 'textbook' in those days (800-200 BCE) was the 'Sulba Sutras' to help figure out the correct angles and lengths to optimally design them (that lead to the discovery of Pythagorean triples and trigonometry, among other things). Inevitably, the beautiful natural patterns inherent in numbers awoke the inner geek in some of these priests.
Among the many famous mathematicians who carried forward this rich Vedic tradition was an astronomer named Brahmagupta (~ 600 CE). He extensively explored solutions to linear Diophantine equations that are central to integer programming today. Of course, his bigger distinction is for 'much ado about nothing'. He is known to be the first human being to clearly define, publish, and use zero as a number! He also explored Diophantine equations of the second degree, and came up with ideas that led to a recursive, iterative solution method for such equations; again something that is very useful in modern numerical optimization. He generalized an idea discovered by Diophantus and used this to achieve some success in finding solutions to Pell's equation. This was generalized to the Chakravala (Sanskrit for 'cyclic') algorithm by Jayadeva (950CE) and Bhaskara II (1100CE). A key subroutine at an iteration involves a neat rational scaling operation, followed by the solving of a simple discrete optimization problem that finds an integer m, such that it minimizes |m2 − N|/k, where N and k are input parameters. Furthermore, they recognize that such problems have degenerate solutions, and in some cases, find minimal integer feasible solutions using this approach. This attention to detail toward handling numerical issues stands out. Recognizing and tackling degeneracy is at the very heart of modern decision-analytics practice!
The Chakravala turns out to be an easy-to-use iterative method to find good approximations for square roots of integers. Indeed, this approach has been recognized for its ingenuity and 'careful simplicity' that allows us to work with well-conditioned real numbers; ideas that we in the OR community know are critical to matrix refactoring within a successful dual simplex implementation, for example.
Among the many famous mathematicians who carried forward this rich Vedic tradition was an astronomer named Brahmagupta (~ 600 CE). He extensively explored solutions to linear Diophantine equations that are central to integer programming today. Of course, his bigger distinction is for 'much ado about nothing'. He is known to be the first human being to clearly define, publish, and use zero as a number! He also explored Diophantine equations of the second degree, and came up with ideas that led to a recursive, iterative solution method for such equations; again something that is very useful in modern numerical optimization. He generalized an idea discovered by Diophantus and used this to achieve some success in finding solutions to Pell's equation. This was generalized to the Chakravala (Sanskrit for 'cyclic') algorithm by Jayadeva (950CE) and Bhaskara II (1100CE). A key subroutine at an iteration involves a neat rational scaling operation, followed by the solving of a simple discrete optimization problem that finds an integer m, such that it minimizes |m2 − N|/k, where N and k are input parameters. Furthermore, they recognize that such problems have degenerate solutions, and in some cases, find minimal integer feasible solutions using this approach. This attention to detail toward handling numerical issues stands out. Recognizing and tackling degeneracy is at the very heart of modern decision-analytics practice!
The Chakravala turns out to be an easy-to-use iterative method to find good approximations for square roots of integers. Indeed, this approach has been recognized for its ingenuity and 'careful simplicity' that allows us to work with well-conditioned real numbers; ideas that we in the OR community know are critical to matrix refactoring within a successful dual simplex implementation, for example.
Tuesday, October 12, 2010
Popular Mechanics and the Frankenstein design principle
Popular Mechanics is a favorite magazine for the sheer variety of mechanical gizmos it throws up inside its pages (check out the Jaguar supercar). It is a permanent fixture in many auto-service shop waiting rooms where we spend a good part of a lifetime. The October 2010 issue of Popular Mechanics was a pleasant surprise - not one but two OR-related topics were covered. The first one was a short article on optimizing waiting experience in queues. The metriclastic US population (is that a new word?) that shuns neat divisions by 10, rightly resents having to spell Q using 5 letters, one of which is Q, and simply calls it a 'line'. On the other hand, 'line theory' is not too informative. Pop-mech doesn't mention OR explicitly, but we know that queuing theory and OR are inseparable.
The queuing article (online version here), among other things, mentions that a smart researcher in Taiwan, Pen-Yuan Liao, derived an equation to compute a 'Balking Index' that tells you when and how many customers are likely to flee a long line and 'defect' to a better one in a multi-Q system. Obviously, information like this helps determine optimal staffing levels to meet the required service levels, minimize costs, and improve the customer experience. Apart from just analyzing people standing in line, queuing models have many and diverse applications and is a whole field of study. There's also some expert comments in the magazine article by Dr. Richard Larson from MIT. His name would be familiar to the OR fraternity.
The second article talks about risk management in the context of the Gulf-Coast oil spill. This tab's summary of the article from an OR perspective is this: When it comes to designing and operating complex systems, there needs to be a greater emphasis on managing conditional expectations associated with low-probability high-consequence events. This is in addition to tracking traditional risk metrics (minimizing expected cost, probability of failure, etc), i.e. we should be tracking multiple risk objectives, something i recall working on many years ago as a grad student.
The Frankenstein principle
Dr. Petroski, a civil engineering professor at the Duke University quotes in the article, "When you have a a robust system, you tend to relax". And it's proven to be true, sadly. BP continually pushed the risk-envelope to boost profits without paying adequate attention to the associated safety trade-off. In part, this was due to a false sense of safety in a historically robust system. There's always a first time, and shockingly, there was no plan 'B' in the event of a catastrophic failure. Bhopal, Chernobyl, Gulf coast and a few more like these have occurred in just the last 30 years. BP engineers were left having to prove that components would fail rather than answer the question "is it safe to operate?" - two completely different propositions. This practice of hastening project completion by placing an unfair burden of proof on the scientists and engineers may be widespread.
The Frankenstein design principle extends Murphy's law. It simply states that if for some crazy reason, you want to build something monstrously complex, then at least design it assuming apriori that at some point it will fall apart and come back to snack on your aposteriori.
The queuing article (online version here), among other things, mentions that a smart researcher in Taiwan, Pen-Yuan Liao, derived an equation to compute a 'Balking Index' that tells you when and how many customers are likely to flee a long line and 'defect' to a better one in a multi-Q system. Obviously, information like this helps determine optimal staffing levels to meet the required service levels, minimize costs, and improve the customer experience. Apart from just analyzing people standing in line, queuing models have many and diverse applications and is a whole field of study. There's also some expert comments in the magazine article by Dr. Richard Larson from MIT. His name would be familiar to the OR fraternity.
The second article talks about risk management in the context of the Gulf-Coast oil spill. This tab's summary of the article from an OR perspective is this: When it comes to designing and operating complex systems, there needs to be a greater emphasis on managing conditional expectations associated with low-probability high-consequence events. This is in addition to tracking traditional risk metrics (minimizing expected cost, probability of failure, etc), i.e. we should be tracking multiple risk objectives, something i recall working on many years ago as a grad student.
The Frankenstein principle
Dr. Petroski, a civil engineering professor at the Duke University quotes in the article, "When you have a a robust system, you tend to relax". And it's proven to be true, sadly. BP continually pushed the risk-envelope to boost profits without paying adequate attention to the associated safety trade-off. In part, this was due to a false sense of safety in a historically robust system. There's always a first time, and shockingly, there was no plan 'B' in the event of a catastrophic failure. Bhopal, Chernobyl, Gulf coast and a few more like these have occurred in just the last 30 years. BP engineers were left having to prove that components would fail rather than answer the question "is it safe to operate?" - two completely different propositions. This practice of hastening project completion by placing an unfair burden of proof on the scientists and engineers may be widespread.
The Frankenstein design principle extends Murphy's law. It simply states that if for some crazy reason, you want to build something monstrously complex, then at least design it assuming apriori that at some point it will fall apart and come back to snack on your aposteriori.
Wednesday, October 6, 2010
Video analysis - followup to previous post on "Should Steve Smith have gone for the run-out?"
Updated Oct 7: youtube video.
As can be seen from the video footage of the last few minutes of the test match, Steve Smith came incredibly close to settling the issue by taking the initiative in a moment of cricketing chaos. He was fielding at point, and fired in the throw at a pretty acute angle - a bold gamble. He brushed against legend but it ended up being India's greatest sporting victory. Another great article by Australian sports writer Peter Roebuck, can be read here.
As can be seen from the video footage of the last few minutes of the test match, Steve Smith came incredibly close to settling the issue by taking the initiative in a moment of cricketing chaos. He was fielding at point, and fired in the throw at a pretty acute angle - a bold gamble. He brushed against legend but it ended up being India's greatest sporting victory. Another great article by Australian sports writer Peter Roebuck, can be read here.
Tuesday, October 5, 2010
OR and cricket: Should Steve Smith have gone for the run-out? - India versus Australia, 2010
Nearly a year ago, the mathletics blog of Dr. Wayne Winston has an interesting analysis of whether Pats coach Bellicheck should have gone for it on a critical 4th down, and put the coach's decision down to his confidence in Tom Brady. Yesterday, some thing similar (but far more serious) happened on the last day (D5) of one of the greatest test cricket matches in history.
The result
Check out the amazing scorecard. In the 120-year history of test cricket, there have been only 12 such finishes.
The match situation
It is day 5 of the contest. About 26 hours of play time has passed and we are into the bottom of the 4th and final innings. India is batting and has lost 9 of their 10 wickets on a wicked last-day pitch with widening cracks and the ball spitting off the pitch. Many have gotten out to bouncers. Just an hour ago, India was down and out having lost 8 wickets with 92 runs still to get. A remarkable partnership between two injured players brings the match to a screaming knife edge. Australia requires 1 wicket to win. India needs 6 runs. At the crease is the injured Indian genius VVS Laxman overcoming back spasms with painkillers and with sheer grit, he is attempting to steal a miraculous win. But the one who is taking strike is P Ojha, a spin-bowler and India's no.11 player, who can't really bat. Bowling is Australian fast bowler Mitchell Johnson who can bowl past speeds of 95mph (there are others who can crank it up to 100mph).
The event
Here's cricinfo's description of the third-from-last ball of the match (edited version here):
Johnson to Ojha, 4 runs, 90.5 mph, Lbw Shout And oh boy what we get .. Four Over throws! That looked out. Was there some wood on leather? Oh well ... What an insane little game this is! .. Steve Smith fires the throw and the ball misses the stumps and runs through the vacant covers. No Aussie fielder could back that up. But that throw was on. Had he hit - and he didn't miss by much - Ojha would have been run out. .....
(india wins 2 balls later)
Post-mortem
Many cricket fans have criticized Steve Smith's decision to take a shy at the stumps. The Australian captain himself felt it was the right call and praised the rookie. If he had hit the wicket it would have been match over. Indeed several sports writers have called it a gutsy and worthy call. I know that if it was an Indian fielder instead, he would have been roasted by India's trigger-happy media.
Probability Model
Probability that australia wins = A. Probability that India wins = 1-A.
There are two scenarios:
1. If successful hit (probability p), then match over, australia win with probability 1.
2. If miss (probability 1-p) then there are two sub-outcomes:
2a. if fielder backing up, no overthrows, and australia win again with probability A (reset).
2b. if no protection, then overthrows, and australia win with probability A' < a =" p(1-A)"> A.
If (2b) is given:
p(win given hit) = p + (1-p)A'
This is statistically a good decision provided p + (1-p)A' >= A. A simple condition where this holds true would be if he were such a good fielder that statitically he hits the wicket more than 100A % of the time, i.e. if he felt that his chance of hitting the wicket was at least as good as the chance that Australia currently has of winning the game (fixing p = A would result in the LHS being > A)
Let's play with some numbers
1. Let's assume that with every run scored, the chance of success for Australia proportionally drops, so the cost of each overthrow run is A/6. For a worst-case 4 overthrows, this gives A' = A-4A/6 = A/3
2. so steve's accuracy rate had to satisfy:
p(1-A/3) >= 2A/3, or p >= 2A/(3-A)
3. If we assume that with just a single wicket to get, but only 6 runs to score, its anybody's game, and set A= 0.5. then steve's accuracy rate had to be atleast 1/2.5.
4. On the other hand, if you start with the premise that A is lower, say 25%, then steve only required an 18% accuracy to justify the throw. In other words, if you perceive that you have little chance of winning, then it is certainly a great idea to take the risk.
Modeling Ideas
You can also calculate 'A' in a more sophisticated manner by looking at the competing counting process to determine P(wicket falls before 6 runs are scored). The probability that a wicket falls in some 'n' balls is a geometric distribution. Each ball is a Bernoulli trial. The distribution of runs per ball could be Poisson. India scored 6 runs in the previous 3 overs (18 balls), so purely statistically, you can extrapolate that to say there's about 18 balls to get the last wicket. All said and done, a 50-50 chance is the most practical choice for 'A' here.
Conclusion
If Steve Smith was generally able to hit the stumps 40% of the time (i.e. slightly less than even chance), then it would have a good call from a statistical point of view. I haven't gotten a chance to review to video to see if it was an easy versus difficult angle to hit the wicket, but on average, 40% does look like a fairly high required conversion rate.
Statistically it was not a great call especially if he knew there was nobody to back up. All the pressure previously built up on the batsman was released. But cricket is played on the field and making a match-defining split-second decision after 26 hours of exhilarating play is no easy ask. No guts, no glory. It's the Aussie way and the glorious game of cricket is better off with that choice, (especially since India won :-)
The result
Check out the amazing scorecard. In the 120-year history of test cricket, there have been only 12 such finishes.
The match situation
It is day 5 of the contest. About 26 hours of play time has passed and we are into the bottom of the 4th and final innings. India is batting and has lost 9 of their 10 wickets on a wicked last-day pitch with widening cracks and the ball spitting off the pitch. Many have gotten out to bouncers. Just an hour ago, India was down and out having lost 8 wickets with 92 runs still to get. A remarkable partnership between two injured players brings the match to a screaming knife edge. Australia requires 1 wicket to win. India needs 6 runs. At the crease is the injured Indian genius VVS Laxman overcoming back spasms with painkillers and with sheer grit, he is attempting to steal a miraculous win. But the one who is taking strike is P Ojha, a spin-bowler and India's no.11 player, who can't really bat. Bowling is Australian fast bowler Mitchell Johnson who can bowl past speeds of 95mph (there are others who can crank it up to 100mph).
The event
Here's cricinfo's description of the third-from-last ball of the match (edited version here):
Johnson to Ojha, 4 runs, 90.5 mph, Lbw Shout And oh boy what we get .. Four Over throws! That looked out. Was there some wood on leather? Oh well ... What an insane little game this is! .. Steve Smith fires the throw and the ball misses the stumps and runs through the vacant covers. No Aussie fielder could back that up. But that throw was on. Had he hit - and he didn't miss by much - Ojha would have been run out. .....
(india wins 2 balls later)
Post-mortem
Many cricket fans have criticized Steve Smith's decision to take a shy at the stumps. The Australian captain himself felt it was the right call and praised the rookie. If he had hit the wicket it would have been match over. Indeed several sports writers have called it a gutsy and worthy call. I know that if it was an Indian fielder instead, he would have been roasted by India's trigger-happy media.
Probability Model
Probability that australia wins = A. Probability that India wins = 1-A.
There are two scenarios:
1. If successful hit (probability p), then match over, australia win with probability 1.
2. If miss (probability 1-p) then there are two sub-outcomes:
2a. if fielder backing up, no overthrows, and australia win again with probability A (reset).
2b. if no protection, then overthrows, and australia win with probability A' < a =" p(1-A)"> A.
If (2b) is given:
p(win given hit) = p + (1-p)A'
This is statistically a good decision provided p + (1-p)A' >= A. A simple condition where this holds true would be if he were such a good fielder that statitically he hits the wicket more than 100A % of the time, i.e. if he felt that his chance of hitting the wicket was at least as good as the chance that Australia currently has of winning the game (fixing p = A would result in the LHS being > A)
Let's play with some numbers
1. Let's assume that with every run scored, the chance of success for Australia proportionally drops, so the cost of each overthrow run is A/6. For a worst-case 4 overthrows, this gives A' = A-4A/6 = A/3
2. so steve's accuracy rate had to satisfy:
p(1-A/3) >= 2A/3, or p >= 2A/(3-A)
3. If we assume that with just a single wicket to get, but only 6 runs to score, its anybody's game, and set A= 0.5. then steve's accuracy rate had to be atleast 1/2.5.
4. On the other hand, if you start with the premise that A is lower, say 25%, then steve only required an 18% accuracy to justify the throw. In other words, if you perceive that you have little chance of winning, then it is certainly a great idea to take the risk.
Modeling Ideas
You can also calculate 'A' in a more sophisticated manner by looking at the competing counting process to determine P(wicket falls before 6 runs are scored). The probability that a wicket falls in some 'n' balls is a geometric distribution. Each ball is a Bernoulli trial. The distribution of runs per ball could be Poisson. India scored 6 runs in the previous 3 overs (18 balls), so purely statistically, you can extrapolate that to say there's about 18 balls to get the last wicket. All said and done, a 50-50 chance is the most practical choice for 'A' here.
Conclusion
If Steve Smith was generally able to hit the stumps 40% of the time (i.e. slightly less than even chance), then it would have a good call from a statistical point of view. I haven't gotten a chance to review to video to see if it was an easy versus difficult angle to hit the wicket, but on average, 40% does look like a fairly high required conversion rate.
Statistically it was not a great call especially if he knew there was nobody to back up. All the pressure previously built up on the batsman was released. But cricket is played on the field and making a match-defining split-second decision after 26 hours of exhilarating play is no easy ask. No guts, no glory. It's the Aussie way and the glorious game of cricket is better off with that choice, (especially since India won :-)
Monday, October 4, 2010
Is this umbrella optimally designed?
Building retail pricing products for a living, i spend an inordinate amount of time analyzing online deals. And you get to see lots of innovative new gizmos on sale. The umbrella shown in the video below was on sale and caught my attention.
It was introduced in the market a couple of years ago and has won multiple design awards. It's aerodynamic and looks like a bicycle helmet extended into an umbrella. I checked out the wind tunnel tests - impressive. It doesn't turn inside out. It's got an eye-protective design built-in and also provides better frontal vision. If you are a geek, you'd feel that you would never want to be caught under the old dome again. It is well-marketed. Check out these product stress test videos. I mean the 300 Spartans could have survived using the Senz as a shield.
Let's apply some practical OR tests.
First look at the actual human feedback at Amazon.com. There aren't too many data points sadly. Some like it and some don't. Next we look at the analytics hidden inside the design of the umbrella. We also examine its external functionality. A really nice analytical innovation allows the umbrella to not fight the wind but mildly orient itself along the path of least resistance. Several stress tests empirically prove this.
Conclusion: Handles wind really well and better vision, so you don't feel like you are in a tent.
However, there's something missing in these tests. Let us turn to robust optimization analysis. All the talk is about gale force winds, wind tunnels. etc. What about some simple vertical rain at terminal velocity? How would it perform in Cherrapunji, India or the town of Mawsynram in the nearby Indian state of Meghalaya, which received 1000 inches of rain in 1985. How does it handle those good old pesky, incessant drizzles?How about sleet and randomized rain loads? How about the inevitable sidewalk drenching from the tires of a car on a wet road?
Conclusion - It appears that it is does not perform the basic, everyday function of an "umbrella for a rainy day" as robustly as it tackles wind. There are a couple of feedbacks in Amazon which highlight this basic limitation.
Question: In a randomized rain situation, can i run in a straight line with an aerodynamic umbrella like the Senz to introduce a favorable directional bias in the forces and improve its rain-performance?
Note that when it is steadily raining, and without an umbrella of any kind, the amount of water that your body/dress absorbs is practically the same, whether u walk or run to cover a fixed distance.
In many places in the world, people regularly use an umbrella to block out the hot sun. Since the total area is relatively smaller when compared to the traditional umbrella, it covers less.
Conclusion: less protection against the sun.
Finally, the most interesting comment was a person who said two people couldn't fit under this umbrella. It's going to be a disastrous end to a date when your partner is under your aerodynamic umbrella and getting all wet in the rain.
Final conclusion: The old dome is on average, more robust for most normal rain/sun/slush situations, and is much less expensive. The inner geek will compel you to get a Senz for the cool wind analytics. Or if you are some weather channel tv journo who shows up in hurricane/tornado hit areas. But guys, don't take the Senz with your girlfriend on a rainy day, and certainly not your wife (and most certainly not both - under any umbrella. sorry, couldn't resist).
It was introduced in the market a couple of years ago and has won multiple design awards. It's aerodynamic and looks like a bicycle helmet extended into an umbrella. I checked out the wind tunnel tests - impressive. It doesn't turn inside out. It's got an eye-protective design built-in and also provides better frontal vision. If you are a geek, you'd feel that you would never want to be caught under the old dome again. It is well-marketed. Check out these product stress test videos. I mean the 300 Spartans could have survived using the Senz as a shield.
Let's apply some practical OR tests.
First look at the actual human feedback at Amazon.com. There aren't too many data points sadly. Some like it and some don't. Next we look at the analytics hidden inside the design of the umbrella. We also examine its external functionality. A really nice analytical innovation allows the umbrella to not fight the wind but mildly orient itself along the path of least resistance. Several stress tests empirically prove this.
Conclusion: Handles wind really well and better vision, so you don't feel like you are in a tent.
However, there's something missing in these tests. Let us turn to robust optimization analysis. All the talk is about gale force winds, wind tunnels. etc. What about some simple vertical rain at terminal velocity? How would it perform in Cherrapunji, India or the town of Mawsynram in the nearby Indian state of Meghalaya, which received 1000 inches of rain in 1985. How does it handle those good old pesky, incessant drizzles?How about sleet and randomized rain loads? How about the inevitable sidewalk drenching from the tires of a car on a wet road?
Conclusion - It appears that it is does not perform the basic, everyday function of an "umbrella for a rainy day" as robustly as it tackles wind. There are a couple of feedbacks in Amazon which highlight this basic limitation.
Question: In a randomized rain situation, can i run in a straight line with an aerodynamic umbrella like the Senz to introduce a favorable directional bias in the forces and improve its rain-performance?
Note that when it is steadily raining, and without an umbrella of any kind, the amount of water that your body/dress absorbs is practically the same, whether u walk or run to cover a fixed distance.
In many places in the world, people regularly use an umbrella to block out the hot sun. Since the total area is relatively smaller when compared to the traditional umbrella, it covers less.
Conclusion: less protection against the sun.
Finally, the most interesting comment was a person who said two people couldn't fit under this umbrella. It's going to be a disastrous end to a date when your partner is under your aerodynamic umbrella and getting all wet in the rain.
Final conclusion: The old dome is on average, more robust for most normal rain/sun/slush situations, and is much less expensive. The inner geek will compel you to get a Senz for the cool wind analytics. Or if you are some weather channel tv journo who shows up in hurricane/tornado hit areas. But guys, don't take the Senz with your girlfriend on a rainy day, and certainly not your wife (and most certainly not both - under any umbrella. sorry, couldn't resist).
Thursday, August 26, 2010
OR Theory, as opposed to OR Practice
An interesting exchange at where else but OR-exchange on "will OR take over the world" ? I would suggest a read-up there and to post your views to keep the discussion going. As one of the participants, a suggestion was made that OR has gone well beyond its mandate and overtaken the world (which gives me a convenient excuse to link to the good old pomo generator. We should build an OR-theory version some time :-), and that there was a crying need to get back to Terra firma.
Sadly, OR practice has very little to do with OR theory now-a-days. It doesn't matter if the department is part of the school of engineering, humanities, or management. Yes, theory has its place. OR theory is particularly enchanting, but an equal part of OR-academia has to be about training kids to think about practical solutions for the real world today, where OR enables a better understanding of real problems for real human beings. This balance is skewed today.
In short, academic OR (today) is almost all about answers, but in OR practice, the 'value-add' comes from asking the right questions. Given the right question, finding a good prescriptive answer in practice is, relatively speaking, a piece of cake (NP-Hard or not, bleeding-edge solver or not). Going to the customer and saying they have an unsolvable problem scenario because the solver that sliced thru your complex MIP model said it was 'infeasible' is just not done. Playing the good OR guy and walking your customer through a well-intentioned slide slow of analyzing an irreducible inconsistent subsystem to explain it is not much better. All that we have done so far is show how ineffective our efforts has been so far! After all, the customer was in business for decades without OR and did pretty well. So a first step in OR practice is to somehow get the customer to tutor us on how they optimized their business well enough to feed their families in this world (when we were happily experimenting with n-dimensional representations in hyperspace until our advisor kicked us out of school with a PhD), so we at least don't make a complete fool of ourselves. A second step would be to apply common sense, but then OR programs rarely get ranked and papers seldom get accepted based on such uncool stuff.
Sadly, OR practice has very little to do with OR theory now-a-days. It doesn't matter if the department is part of the school of engineering, humanities, or management. Yes, theory has its place. OR theory is particularly enchanting, but an equal part of OR-academia has to be about training kids to think about practical solutions for the real world today, where OR enables a better understanding of real problems for real human beings. This balance is skewed today.
In short, academic OR (today) is almost all about answers, but in OR practice, the 'value-add' comes from asking the right questions. Given the right question, finding a good prescriptive answer in practice is, relatively speaking, a piece of cake (NP-Hard or not, bleeding-edge solver or not). Going to the customer and saying they have an unsolvable problem scenario because the solver that sliced thru your complex MIP model said it was 'infeasible' is just not done. Playing the good OR guy and walking your customer through a well-intentioned slide slow of analyzing an irreducible inconsistent subsystem to explain it is not much better. All that we have done so far is show how ineffective our efforts has been so far! After all, the customer was in business for decades without OR and did pretty well. So a first step in OR practice is to somehow get the customer to tutor us on how they optimized their business well enough to feed their families in this world (when we were happily experimenting with n-dimensional representations in hyperspace until our advisor kicked us out of school with a PhD), so we at least don't make a complete fool of ourselves. A second step would be to apply common sense, but then OR programs rarely get ranked and papers seldom get accepted based on such uncool stuff.
Monday, July 26, 2010
Analytics in Acadia
Living close to the Acadia national park has turned me into a local tourist guide for friends and relatives who consider any visit to Maine incomplete unless they spend a day there. By applying OR and data analysis, I've kinda figured out the right days to visit Bar Harbor in summer and escape the tourist crowd. On days having a very high bliss factor, an OR person can relax there and think about the naturally elegant analytics hidden all around.
The main scenic route (the park loop road) is a nice 'hard-coded' feasible solution to the TSP that requires us to touch all the popular spots in the park while constraining the grade in the resultant road to be within a safe level, while also reducing the amount of earth to be moved. Of course, too short a path is not very enjoyable, while too long a path will find tourists driving relatively fast to skip the repetitiveness, so the total length of the Hamiltonian circuit should ideally be within some desired bound.
As we think about path lengths, there is an equally interesting observation one can make about the beautiful Maine coastline while driving along the circuit - it certainly looks long. Now, if you look at the map of the US, the California coast seems much longer in comparison. However, if you take into account the bays and undulations and increase the level of detail, the Maine coastline is comfortably longer - the fractal coast length of Maine is more than 2000 miles long (or so i heard). The fractal dimension of the Boothbay, ME coastline was calculated to be 1.27.
Per Wikipedia, 'Maine' is the only single-syllable state-name and also the only state to share a border with a single US state (New Hampshire), which means that we require just two colors to map this region of the US. We share a border with New Brunswick, CA, whose DOT, along with Remsoft, Inc., were Edelman finalists this year. I attended their presentation at the INFORMS practice conference, and it was a really fine one, and I hope our US DOTs learn from them to ensure that the economic stimulus money is optimally spent.
The main scenic route (the park loop road) is a nice 'hard-coded' feasible solution to the TSP that requires us to touch all the popular spots in the park while constraining the grade in the resultant road to be within a safe level, while also reducing the amount of earth to be moved. Of course, too short a path is not very enjoyable, while too long a path will find tourists driving relatively fast to skip the repetitiveness, so the total length of the Hamiltonian circuit should ideally be within some desired bound.
As we think about path lengths, there is an equally interesting observation one can make about the beautiful Maine coastline while driving along the circuit - it certainly looks long. Now, if you look at the map of the US, the California coast seems much longer in comparison. However, if you take into account the bays and undulations and increase the level of detail, the Maine coastline is comfortably longer - the fractal coast length of Maine is more than 2000 miles long (or so i heard). The fractal dimension of the Boothbay, ME coastline was calculated to be 1.27.
Per Wikipedia, 'Maine' is the only single-syllable state-name and also the only state to share a border with a single US state (New Hampshire), which means that we require just two colors to map this region of the US. We share a border with New Brunswick, CA, whose DOT, along with Remsoft, Inc., were Edelman finalists this year. I attended their presentation at the INFORMS practice conference, and it was a really fine one, and I hope our US DOTs learn from them to ensure that the economic stimulus money is optimally spent.
Sunday, June 27, 2010
Oracle Crosstalk 2010: Yes, OR can help retail
Analytics is a hot topic for retailers. Several presentations during this conference returned to this theme and is a huge positive sign for OR in this industry. However, how to apply science smartly to the tons of sales data being collected (and retailers collect this like holy dust nowadays) and to automate robust decision making is another question altogether - 99% of the retailers do not have the right skill sets to pull this off. It is not easy building this system in-house from the ground up, and companies like Oracle Retail can do this better and faster, allowing retailers to focus on their core business areas. Few if any, were even aware of 'OR' (is OR by any name still OR ?). On the other hand, the general consensus was that revenue and supply chain optimization is a must to compete in this tough economy (honey, i shrunk the margins). A panel of investment experts with representatives from major financial institutions, both government and private, felt that in addition to top-line growth, being able to optimize the use of scarce resources to achieve operational excellence is one of the keys for survival in this new economy.
The level of hype surrounding the virtual region that lies at the intersection of social networking and mobile technology is staggering with numbers going off the charts (literally). How can OR grab a share of the science pie here? For example, I liked the way Wet Seal has been innovating and surely this area is going to see new and innovative applications being developed soon. Experts from Google and other tech-heavy companies weighed in on this as well and all signs point to an interesting retail shopping experience in the near future. Get your scan-ready smart-phone out and interactively and collaboratively shop in a real store with your virtual friends. The line between brick-and-mortar stores and the virtual shopping world is rapidly blurring.
On a side note, it was great visiting Chicago after a few years. The single most beautiful landmark there is the dazzling Swaminarayan Mandir (loosely translates to 'temple') in Bartlett. Hand-sculpted from Italian Marble and Turkish limestone by thousands of Indian craftsman, this Mandir does not rely on machine-tools and does not contain a single metal part or fastener in keeping with the sacred Indian tradition of Mandir architecture. Interlocking stones are used throughout, with individual stones weighing between a few grams to 5.2 tons. Pretty amazing. It is open to the public and is a must-see for visitors. The gardens and fountains surrounding the temple are well-maintained and pleasing to the eye. Inside the complex, smartly designed fiber-optic lighting and hidden underground heating add an invisible high-tech layer to this construction, and combines with the silence that must be observed within the ethereal sanctum-sanctorum to create a deeply personal and spiritual experience. The food served in the community center in the basement is excellent, and is strictly vegetarian, of course.
The level of hype surrounding the virtual region that lies at the intersection of social networking and mobile technology is staggering with numbers going off the charts (literally). How can OR grab a share of the science pie here? For example, I liked the way Wet Seal has been innovating and surely this area is going to see new and innovative applications being developed soon. Experts from Google and other tech-heavy companies weighed in on this as well and all signs point to an interesting retail shopping experience in the near future. Get your scan-ready smart-phone out and interactively and collaboratively shop in a real store with your virtual friends. The line between brick-and-mortar stores and the virtual shopping world is rapidly blurring.
On a side note, it was great visiting Chicago after a few years. The single most beautiful landmark there is the dazzling Swaminarayan Mandir (loosely translates to 'temple') in Bartlett. Hand-sculpted from Italian Marble and Turkish limestone by thousands of Indian craftsman, this Mandir does not rely on machine-tools and does not contain a single metal part or fastener in keeping with the sacred Indian tradition of Mandir architecture. Interlocking stones are used throughout, with individual stones weighing between a few grams to 5.2 tons. Pretty amazing. It is open to the public and is a must-see for visitors. The gardens and fountains surrounding the temple are well-maintained and pleasing to the eye. Inside the complex, smartly designed fiber-optic lighting and hidden underground heating add an invisible high-tech layer to this construction, and combines with the silence that must be observed within the ethereal sanctum-sanctorum to create a deeply personal and spiritual experience. The food served in the community center in the basement is excellent, and is strictly vegetarian, of course.
Friday, June 18, 2010
Oracle Cross-talk, June 22-24, Chicago - strong OR presence
Operations Research at Oracle Retail will have a strong presence in this year's edition of Oracle Cross-talk, to held next week between June 22-24 in Chicago, where (paraphrasing the press release) " ... retail executives and retail industry experts from around the world will share insights, demonstrate innovations and better understand the role of technology in new retail business strategies...".
There are a few analytics-heavy sessions planned, and being an attendee as well as an 'optimization facilitator' this time, I hope to spread the OR gospel and gain insight into the progress of OR-usage in this industry over the last 5 years, the level of user acceptance, and value added.
There are a few analytics-heavy sessions planned, and being an attendee as well as an 'optimization facilitator' this time, I hope to spread the OR gospel and gain insight into the progress of OR-usage in this industry over the last 5 years, the level of user acceptance, and value added.
Sunday, June 13, 2010
The Reverse What-if: more hard-won insight into OR practice
The real fun in O.R practice is when your optimization product (say a recommendation system) is evaluated by it's first customer. Usually this is the point where you throw away the last 6 months of your textbook work and build something that your customer can actually use rather than what you wanted to build.
If you are in the business of providing software-as-a-service, you can do several iterations with a customer and that practice is more forgiving, but i am learning the hard way that building an air-tight OR product and then handing it off to a customer is mighty hard and you only have one or maybe two chances to get it right.
(note: some dramatic license exercised for illustrative purposes)
Today's tab focuses on the 'what-if', the practice of walking a customer thru a choreographed sequence of optimization scenarios. An obvious choice is to start with a somewhat unconstrained model, say, only having boxed variables, and then show the user or the consultant how the solution changes as you throw in, one by one, all those beautiful constraints your system can handle. At the end of this process, if everything goes well, you end up with a real and optimized solution that business can use and will save them many $$.
Unfortunately, this approach of "increased complexity" rarely works. The procedure described above is nice if you are trying to teach a student about OR. The average business user doesn't really care about this. He/She probably understands real-life solutions much better than you. She/we wants your system to work well and maybe help get a bonus at the end of the fiscal year. In fact, you are better of looking at its dual, the reverse-what if.
The reverse what-if, as you would guess, starts with the best approximation of the customer's reality and then you navigate from there. Otherwise, the customer has little patience for all the n-1 steps in the 'straight' what-if which represent imaginary solutions he doesn't care about. The n'th step brought him to reality, which he already understands better than you, so you haven't helped him much.
The reverse what-if perfectly ties in with Rosenthal and Brown's practical philosophy of starting with a legacy solution. Your recommendation system should be able to represent the legacy recommendation, else your product is not going to earn your customer's vote. Even if they purchased it, they may end up just using your GUI and throw your analytics into the trash. Unless you are providing an order of magnitude improvement in business value (in which case, you should start your own company!), revolutionary solutions are a hard sell. Yes, a customer values seemingly non-intuitive solutions that your OR unlocks to make him more money, but to truly ensure user-adoption, you need demonstrate this improvement from the legacy solution.
It also goes to user experience. In fact, it's about avoiding home-sickness. Being able to return to something familiar is critical for user acceptance. How many times have we initially cursed websites who suddenly redesigned and changed everything and you cant find your favorite menus in the same place? Windows OS always provides us the option of returning to something that resembles their previous release, even though they know they fixed a million bugs since their prior release. And we gradually outgrow the old if the new performs as advertised. I still use my favorite music player Winamp's classic skin. Feels like home.
Comments welcome.
If you are in the business of providing software-as-a-service, you can do several iterations with a customer and that practice is more forgiving, but i am learning the hard way that building an air-tight OR product and then handing it off to a customer is mighty hard and you only have one or maybe two chances to get it right.
(note: some dramatic license exercised for illustrative purposes)
Today's tab focuses on the 'what-if', the practice of walking a customer thru a choreographed sequence of optimization scenarios. An obvious choice is to start with a somewhat unconstrained model, say, only having boxed variables, and then show the user or the consultant how the solution changes as you throw in, one by one, all those beautiful constraints your system can handle. At the end of this process, if everything goes well, you end up with a real and optimized solution that business can use and will save them many $$.
Unfortunately, this approach of "increased complexity" rarely works. The procedure described above is nice if you are trying to teach a student about OR. The average business user doesn't really care about this. He/She probably understands real-life solutions much better than you. She/we wants your system to work well and maybe help get a bonus at the end of the fiscal year. In fact, you are better of looking at its dual, the reverse-what if.
The reverse what-if, as you would guess, starts with the best approximation of the customer's reality and then you navigate from there. Otherwise, the customer has little patience for all the n-1 steps in the 'straight' what-if which represent imaginary solutions he doesn't care about. The n'th step brought him to reality, which he already understands better than you, so you haven't helped him much.
The reverse what-if perfectly ties in with Rosenthal and Brown's practical philosophy of starting with a legacy solution. Your recommendation system should be able to represent the legacy recommendation, else your product is not going to earn your customer's vote. Even if they purchased it, they may end up just using your GUI and throw your analytics into the trash. Unless you are providing an order of magnitude improvement in business value (in which case, you should start your own company!), revolutionary solutions are a hard sell. Yes, a customer values seemingly non-intuitive solutions that your OR unlocks to make him more money, but to truly ensure user-adoption, you need demonstrate this improvement from the legacy solution.
It also goes to user experience. In fact, it's about avoiding home-sickness. Being able to return to something familiar is critical for user acceptance. How many times have we initially cursed websites who suddenly redesigned and changed everything and you cant find your favorite menus in the same place? Windows OS always provides us the option of returning to something that resembles their previous release, even though they know they fixed a million bugs since their prior release. And we gradually outgrow the old if the new performs as advertised. I still use my favorite music player Winamp's classic skin. Feels like home.
Comments welcome.
Wednesday, June 9, 2010
June sports roundup with an O.R eye
May was spent writing and rewriting analytical specification documents for some exciting new retail O.R products, and when it was done, it is June. which tends to be the best month of the year for international sports fans. Apart from the main course of cricket, there's the NBA finals, which looks like going the distance, and the tennis at Roland Garros and Wimbledon, where baseline power-duels are becoming increasingly boring to watch. We had the spelling bee during the weekend, where Anamika Veeramani ('stromuhr') won this year's edition, while another Indian-American Aadith Moorthy won the other bee - The National Geographic ("where would you speak Tswana?"). Amazingly, both had perfect scores throughout the competition. The spelling bee in particular seemed more interesting this year. Unlike the past where gifted kids with 10Tbs of RAM seemed to do a "total enumeration" by memorizing entire dictionaries, this time the words were chosen such that you invariably had to apply analytical methods - 'word root signatures' - and construct an optimal prediction from pieces of noisy data, without a computer and within the time limit. Consequently, total enumeration failed this time, and made for better TV viewing on ESPN, apart from being a small victory for O.R.
It is increasingly important to read and experience other cultures, with so many words from all corners of the world. Any fan of the Asterix comic book series would have spelled 'Menhir' right, while anybody who's dined at a Punjabi Indian restaurant would have drank 'Lassi' for lunch. On the other hand, the word expert who walks the kids through the definitions needs to do his own homework. Either he needs to brush up his pronunciations of these new words, or there needs to be more than one expert doing the talking (Only french-rooted words ever seem to be get pronounced right). More and more analytic job descriptions require you to work harmoniously with cross-cultural teams in this new world. Now, in addition to knowing your AMPL, you have to correctly spell or pronounce the interviewer's name (without the middle initial, to make it easy), Aransanipalai K. Ananthapadmanabhan, to get the job. Good luck.
Talking about rainbow warriors, the FIFA football world cup starts in a couple of days in the diverse nation of South Africa (yes, Invictus is based on a true story). A whole bunch of analytical work has been devoted to the deadly business of penalty kicks, which seems to determine winners in recent times. A conclusion is that a spot-kick taker can increase the odds in his favor by acting upon the recommendations from this analysis. It is not a total crap-shoot, and some teams are consistently better at this, e.g., blood and guts Germany, while others such as the soccer hooligans from across the pond are abysmal. Of course, once the goalkeeper and the striker both starting applying analytics-based prayer techniques at this sports ritual, its going to cancel out and we are going back to square one. Until then, sports analytics witch-doctors bearing stochastic gifts can ride the gravy train.
update: also see here for more on the science of penalty kicks.
It is increasingly important to read and experience other cultures, with so many words from all corners of the world. Any fan of the Asterix comic book series would have spelled 'Menhir' right, while anybody who's dined at a Punjabi Indian restaurant would have drank 'Lassi' for lunch. On the other hand, the word expert who walks the kids through the definitions needs to do his own homework. Either he needs to brush up his pronunciations of these new words, or there needs to be more than one expert doing the talking (Only french-rooted words ever seem to be get pronounced right). More and more analytic job descriptions require you to work harmoniously with cross-cultural teams in this new world. Now, in addition to knowing your AMPL, you have to correctly spell or pronounce the interviewer's name (without the middle initial, to make it easy), Aransanipalai K. Ananthapadmanabhan, to get the job. Good luck.
Talking about rainbow warriors, the FIFA football world cup starts in a couple of days in the diverse nation of South Africa (yes, Invictus is based on a true story). A whole bunch of analytical work has been devoted to the deadly business of penalty kicks, which seems to determine winners in recent times. A conclusion is that a spot-kick taker can increase the odds in his favor by acting upon the recommendations from this analysis. It is not a total crap-shoot, and some teams are consistently better at this, e.g., blood and guts Germany, while others such as the soccer hooligans from across the pond are abysmal. Of course, once the goalkeeper and the striker both starting applying analytics-based prayer techniques at this sports ritual, its going to cancel out and we are going back to square one. Until then, sports analytics witch-doctors bearing stochastic gifts can ride the gravy train.
update: also see here for more on the science of penalty kicks.
Subscribe to:
Posts (Atom)