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.

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. 

(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.

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)