Monday, November 26, 2012

Review of WVLPSolver: A Java-based Linear Programming Library

Pure Java based optimization tools released under benign licenses are popular in decision-analytics embedded industrial applications. They reduce maintenance efforts and deployment costs, keeping IT managers, analytical support engineers, and developers happy. No platform-specific issues to deal with. No license and patent infringement headaches.... It's a win-win for everybody, provided these 'free' analytical tools withstand the rigors of a production environment.

Recap: This tab summarized a set of pure Java tools a while ago here, talked about a DIY Java solver here that gets you to within a factor of 10-20 of CPLEX on combinatorial LPs, and chatted about "GooPLEX v1.0" some years ago here.

The new WVLPSolver library is introduced here (courtesy:  Bharath Krishnan, data scientist at CQuotient). This new solver is worth a look because its v1.0 appears to be more well thought out compared to the initial version of 'Gooplex'. In particular, WVLPSolver seems to employ a revised simplex scheme that would allow it to work with a minimal simplex tableau (see an old but remarkable (if extreme) illustration of this advantage). Per the introductory post, it employs the reliable Colt library, and is released under the Apache license. These three factors alone may allow this tool to become a useful workhorse in specific situations ("think small"). Great work by the developers, and hope they continue to improve upon this initial release.

Big Data produces a variety of decision problems (recent post related to this topic). In some situations, and depending on the problem structure, you may end up needing to solve tons of small but independent optimization problems, and in other cases, relatively fewer giant monoliths where a considerable amount of sophistication is required to produce consistently good answers. In the former case, an IT manager has to decide whether he needs to budget for a million-instance licensed version of an industrial-strength solver that works cross-platform, or hack-a-heuristic that generates "user-optimal solutions" but may end up confusing users, or go with a nice, pure Java LP brew. Each option has its advantages and disadvantages depending on the context. For analytics start-ups that offer solutions having a relatively small OR footprint, the last option may sound appealing.

Monday, November 12, 2012

Operation Red Lotus and Jules Verne

Around the World in 80 Days
One of the few positive side effects of Hurricane Sandy knocking out power for nearly a week was the rediscovery of a childhood joy of reading history books and stories of valiant Indian queens and kings by the candlelight. Globe-trotting dreams of kids in 1970s socialist India who couldn't afford to set foot on an airplane were kindled by reading and re-reading stories like Jules Verne's fascinating adventure travelogue 'Around the World in 80 Days', a book written a hundred years earlier in 1873.

Indian Rebel
Just a few years before Jules Verne wrote some of his most popular books, the English government was engaged in a bloody, all-out war for economic power in the Indian subcontinent. The rebellion against the colonizers in 19th century India was not just a local mutiny of Sepoys (hired soldiers), and not just an uprising of the peasants; native rulers (Rajas), dashing queens (Ranis), naturalized Indian kings of the dying Mughal dynasty, military leaders, intellectuals, priests, bankers,  traders, farmers, ... entire populations participated in the struggle to free India socially, economically, and culturally in what came to be recorded as the first war of Indian Independence fought in 1857. This is one of the many excellent findings recorded in the historical book "Operation Red Lotus" written by Parag Tope, a descendent of Tatya Tope, chief coordinator of the Indian war machine during that time period.

Jules Verne's Captain Nemo of 1870 appears to be a character straight out of this war. A hi-tech sea-faring native prince seeking vengeance against the English, Nemo is not far from reality. Native rulers set up navies that relied on the construction of relatively sophisticated ships to safeguard overseas trade interests that were being overrun by the piracy of the English East India Company (EEIC). This is hardly surprising given that the world's first dockyard was built in India and the maritime prowess of native kings on both sides of the Indian coast is legendary. However, the key battles of the 1857 war were fought inland in Northern India.

Operation Red Lotus

A wealth of information from recently recovered original correspondence to Tatya Tope during this time period appears to have encouraged the writing of this book. This excellent review summarizes the findings. While there is ample evidence to suggest that the strategy and tactics employed by the Indian resistance in 1857 was indicative of a comprehensive and long-term approach, claims of an sustainable war effort cannot be taken seriously (to paraphrase Gen. Omar Bradley) unless it can be shown that there was a feasible logistics solution in place. Operation Red Lotus (ORL) answers this question in the affirmative.


pic source

The Lotus Code: Operations Research and Logistics?
ORL is mainly about how Tatya Tope and other leaders on the Indian side designed a simple and neat supply chain to support the war effort and maintain an army of newly unemployed native soldiers, bereft of any provisioning infrastructure. Tatya's first step, like we do in the corporate world today, was to forecast enterprise-level demand - but he had to do this without tipping off the Red Shirts. Toward this, he exploited the contempt the colonizers had for 'backward' Indian rituals and traditions. Tatya Tope secretively sampled demands at the platoon level using a red-lotus based numerical code. The English were puzzled to see a spate of red lotuses being passed around the garrisons in many cities they controlled and initially attributed it to yet another weird 'blood red' native custom. The number of petals in a red lotus is approximately the same as the number of soldiers in an EEIC platoon.

 (source colorbox.com)

A native soldier who volunteered would pluck a petal and pass the flower on. After all soldiers made their choice, what was left of the flower was sent back to Tatya. By counting the reeds and/or the remaining petals in a returned lotus from a particular geographical location, noting the number of lotus-sampled platoons, and rolling up these estimates to a regimental level, Tatya was able to predict the approximate size of the native army by location. Having this fundamental information at hand, the planners calculated the provisioning required to sustain the war effort in its various stages, and also finalize the line of attack to capture and hold Delhi, the capital, as well as other strategically important cities. The next challenge was to geographically allocate supplies to satisfy this location-specific demand forecast given that the emerging native army did not have the resources or the time to rapidly create and manage their own own supply line. The only viable solution was to outsource this task, which was accomplished via the Chapati (an unleavened Indian bread) code.

The Chapati Code
After the flood of lotuses, the English were bemused to see Chapatis being exchanged by the chiefs of some villages. Alarm bells went off and they managed to intercept Chapatis embedded with lotus seeds.

 (source food fun freak blog)

The English concluded that this was not another strange custom and that the exchange of lotuses and Chapatis was some kind of a secret handshake. Red lotuses weren't found in the hands of villagers, and seeded Chapatis were not found in garrisons. What historians did not fully realize was that the lotus and the Chapati distribution were the code; not merely Boolean flags, but a vector representation of numerical information relating to troop strength and battle plans. We now know that the Indian war planners sent Chapatis to the various villages along a directional chain graph on a Euclidean plane whose source was a major garrison, and the sink was an important military objective.

[ORL book extract]

The men of the villages that were ready to support the war effort would requisition and stock food grains, and the women of the village would be required to prepare food in quantities proportional to the number of Chapatis they received. The village chief would pass on a similar number of Chapatis to the next village in the designated chain. There is little doubt now that this was a coordinated and planned war to achieve self-rule.

Breaking Down The Supply Chain
When the time was ripe, the sepoys mutinied on the pretext of greased cartridges (immortalized by the legend of Mangal Pandey),  catching the EEIC and the Victorian government in England off guard, and the initial phase of the war went against the colonizers. However, once they recognized the logistical method employed by the natives, the reprisals were eerily Nazi-like: swift, decisive and genocidal, and in keeping with a pattern that was repeated a few times before India's political independence in 1947.  Villages on these chain graphs that supported the war effort were interdicted. Emergency laws were enacted that essentially gave English officers the license to kill civilians based on suspicion. Large populations, including women and children were wiped out, successfully disrupting the Indian supply chain.

 (source: wikipedia)

(source columbia.edu)

Once the logistical backbone was broken, it was a matter of time before the colonials won the war. However, it turns out that the war also had some cascading international effects.

Global impact of the 1857 Indian War of Independence
The London government withdrew huge sums of money from their banks and investments, including prominent financial institutions in the U.S, to raise sufficient capital to fund and ship out tens of thousands of fresh troops to India to win the war, while publicly spinning this fiasco as a localized case of mutiny. This behavior did not escape the attention of some Americans who questioned the official version.
.
  [ORL book extract, pages 86-87]

ORL notes another pertinent question that George Train asked: "England says they are short of funds. Where are the hundreds of millions of silver that have been shipped there [India], disturbing the currency of the world?

The withdrawal of such huge sums of money by the English from US banks exacerbated the panic of 1857, and the resultant liquidity problem severely impacted the Northern states in the US besides triggering the world's first ever global economic crisis. Furthermore, the war hit the EEIC-pirated textile goods exported from India to the west, which reacted by sourcing more cotton from the southern US states that was being produced at even cheaper rates using African slave labor, thereby boosting the Confederate economy and morale. Thus, the Anglo-Indian war of 1857 appears to also have had some impact on the subsequent American civil war of 1861-65.


Jules Verne's Phineas Fogg is most likely based on George Train, a remarkable real-life American adventurer-entrepreneur who went around the world a few times, including a round trip in 67 days.

Legacy
It is less known that the Indian resistance achieved a few tangible victories for India in the long term. For brevity, we will have to leave that discussion for another day. India lost the 1857 war but those who resisted genocide became legend; none more so than the heroic young queen, Rani Lakshmi Bai. This coming Monday, November 19 is her birthday. Reading the immortal line in the Hindi poem about her in the candlelight as a kid, and then again a few days ago about her incredible exploits in ORL even as hurricane winds howled outside, never fails to bring a lump to the throat.

खूब लड़ी मर्दानी वह तो झाँसी वाली रानी थी।।


"She who gallantly fought a man's battle, was our Queen of Jhansi".