Friday, October 14, 2011

Long-distance convergence

The first picture tracks the achieved percentage reduction in a certain minimization objective function value (a shortest path distance) relative to it's initial value, over time.



Not monotone convergence, but still pretty good, and the relative gap finally goes close enough to zero (within a tolerance of 0.5%). Most would be happy to see this solution performance on any O.R decision problem instance in practice.

The next picture tracks the raw values corresponding to the first plot - the shortest path in miles, between the location of my ORMS job and that of my wife's (non ORMS job). The time scale is in years. This also happens to be the commute distance (logarithmic scale).



Average convergence rate = 581 miles/year
Total cost incurred = 27,500 mile-years (counting from year "-2")

Sometimes, superlinear convergence feels terribly slow, but in this era of labor restrictions, we'll chalk this down in the 'wins' column.

Saturday, October 8, 2011

Jumbo decision models to protect the environment

As the population increase in India leads to scarce resources becoming scarcer, villagers in rural India increasingly encroach on jungle areas and vice-versa. In Orissa, the government has decided to take the help of elephants to manage this conflict.

This is a true story.


These magnificent, emotional multi-tuskers with a long trunk and an even longer memory, are much loved and venerated in India. Loved this particular song sequence as a kid.




Elephants require relatively larger habitats to survive, and in recent times, we increasingly hear of elephants and other wild animals in India going on the rampage among civilian populations located close to their territory.

To tackle this problem, the government of Orissa (a beautiful, culturally rich state in eastern India) came up with a novel control method based on self-governance: train 50 Col. Hathis and position them at vantage points. These smart jumbos serve dual purposes:

Online: actively discourage militant pachyderms from venturing too far out

Offline: speed up the learning curve for newbie wild elephants undergoing training.

An initial pilot has been successful.  Read this brief but amazing report for the real costs involved, benefits that can be realized, and the encouraging preliminary results.An interesting O.R. challenge is to maximize the effectiveness of this method without adding additional capital expenses. How should the forest officers position these limited number of smart elephants to maximize their effectiveness in controlling the herds? For example: given p 'Kunki' elephants, we can determine an optimal positioning of these elephants by solving the corresponding p-median like location-allocation problem to better control intrusions, cover more (convex?) territory, or utilize fewer Kunkis to effectively accomplish the same task.

Is this a first example of how OR and elephants can combine to help protect the environment?

Credits

A Jumbo-sized thanks to the brilliant and multi-talented Vijayendra Mohanty for inspiring this post.

This post is humbly dedicated to Shehla Masood (1973-2011).

How long is a game of snakes and ladders?

The detailed answer can be found here. You can stop right now or roll the dice and play on ...

The game originated in India more than 800 years ago and is still popular there. Other board games (Chaturangam or chess, and Pachisi or Ludo) also originated here, and a future post will explore the familiar stochastic OR topic of 'a gambler's ruin' in ancient India. Here's a picture of a native SNL board. The original Indian name of the SNL game translates to 'the path to salvation' and was supposed to be morally educational as well as enjoyable for kids. It's actually pretty profound.

From an Operations Research perspective, the game can be modeled as a Markov Chain. The moral lessons for kids in the Markovian property of SNL seems to be that no matter how terrible a path you took to get to a certain point, you retain the same possibility of salvation by consistently performing good deeds. Note the absence of any non-Markovian historical baggage of original sin. Similarly, a lifetime of virtuousness can be temporarily undone by a single big act of indiscretion that can literally bring you back to square one. As kids, we always felt nervous about the long snake lurking around the 99th square waiting to yank us down.

Per the paper (linked above) published in 1993, simulations indicated that the average number of moves for a 10X10 square game of SNL was around 39. More precisely, using the Markov Chain state transition equations, the authors (Althoen, King, and Schilling) calculate the exact expected number of moves in the "Milton Bradley version of Chutes and Ladders" to be equal to this impressive but twitter-unfriendly ratio:

225837582538403273407117496273279920181931269186581786048583
5757472998140039232950575874628786131130999406013041613400

or approximately 39.2. Other interesting results based on a sensitivity analysis of this value wrt adding or dropping snakes and/or ladders include:
- a six-sided die based game of SNL with no snakes or ladders lasts around 33 moves on average. A unit snake seemingly prolongs the game more than a ladder can speed it up. I felt that pretty acutely as a kid. Yet again, in true Steve Jobsian fashion (or maybe not), it turns out that the seemingly idle SNL time in Bangalore, India was a solid foundation for a career in O.R practice.