Tuesday, August 25, 2015

The One-Dollar Haircut

Every year, I travel more than 9K miles to my native place in Tamil Nadu, India, to get my $1 haircut.
(pic source: http://jhingu.com)

The local barber is an expert and does it the old-fashioned way. A comb to sift, and super-quick scissors acting as efficient cutting planes to produce a nice, convex-hull hairdo. No fancy machinery, seating, lighting, or A/C in his environment-friendly shop, and not a single nick, or hair out of place when he's done. This keeps his customers happy and operating cost low. It's a dollar regardless of crop density. Perhaps the argument is that for the sparse-headed, the cost of searching goes up even as the actual cutting time reduces. If the shop is full, spill-over customers can sit in makeshift chairs outside the shop, and sip chai from the adjoining 'tea-kadai'.

The Indian barber shop is also an instance of the 'elastic' capacity model that is key to understanding how the Indian economy has chugged along. Here is what Prof. R. Vaidyanathan, Professor at the Indian Institute of Management, Bangalore, in his superb book 'India, Uninc' has to say:


Data shows that it this 'unincorporated' economy built from the ground-up by entrepreneurs that is responsible for much of India's GDP and employment, and not the stock market that grabs headlines. Despite the recent crash of the global markets, the Indian elephant is likely to remain solid, like it did after 2008.

The traditional Indian way of doing business may be initially bewildering to the external observer, which may have led to this 'Uninc' being categorized by Nehruvian India's west-educated officials as "unorganized". Actually, it is anything but, and appears to be based on balancing constraint-enforcing 'order' and constraint-relaxing 'chaos'. This traditional Indian approach, which I personally view as dharmic optimization, yields astonishingly high and sustainable levels of quality and efficiency when done right, but can also be disastrous when either order or chaos is excessive.

End Note: Apparently, the global wig supply-chain sources much of its hair from India.

Wednesday, July 22, 2015

How many songs does your favorite internet radio station hold?

Can we even measure the number of songs 'stocked' by our favorite internet radio station (IRS) ? Douglas Hubbard who wrote "How to Measure Anything" would say yes. At least, we can get a reasonable and useful estimate. In fact, it may be tough to identify what an 'exact' answer is here since new songs may be continually added, and less popular ones deleted over time.

This problem appears to resemble another one: How many fish are there in a particular lake? As DH notes, just because we may never see all the fish the lake or hear every song in the IRS, it does not automatically mean that we cannot estimate its size. As part of my self-education in Indian logic, I understand this as follows: when we cannot directly perceive and verify (pratyaksha pramaana), we can try to infer this unobserved truth (~anumaana). Sometimes, we can use comparison (~upamaana) to solve this problem. Here are examples of historically significant events in India where estimating unobserved quantities turned out to be important:

1. Estimating the size of native volunteers ready to take on the occupying British Raj as part of 'Operation Red Lotus' in 1857 (covert sampling and proportions)

2. Estimating the number of refugees inside the Red Fort (without entering) after the 1947 partition of India (comparison of proportions)

3. Estimating the size of jute crop in 1930s Bengal (random sampling)

4. The number of civilians killed in the Bengali holocaust of 1943 (random sampling). The blog carries excerpts, but you should read Madhusree Mukerjee's book for an in-depth analysis.

Using the overlapping sample approach and the fish example in DH's book: catch some fish (say 1000), tag them, and let them swim happily around the lake. Again catch fish (say, 1000) and count the proportion of tagged fish (say 5%), indicating that we tagged roughly 5% of all the fish, giving us an estimate of about 20k. We can also calculate, say, a 90% confidence interval for the chosen sample size. Which brings me to the reason for this blog. I noticed that too many songs on the Ilayaraaja radio station offered by Google-music repeated during my office commutes last week. No problem re-listening to Ilayaraaja musical scores like this one (based on Shamukhapriya ragam is my semi-educated guess).



20 songs were mentally tagged on day-1 and released back into the radio station, and 20% of those tagged songs were streamed back to me on day-2. This experiment was repeated a couple of times, yielding similar results, indicating that Google-music's Ilayaraaja station roughly currently stocks about a hundred songs, and I will soon be hearing only repeats.


Sunday, July 5, 2015

Finding an optimal parking spot for shopping

Here is the original discussion at 'Punk Rock OR'.  The blog below studies a parking objective in the shopping context, and where the entrance to the shopping complex and the exit are at different locations. The cost to be minimized consists of at least two components:
(objective-a) the 'work' done searching for a good parking spot, as well as
(objective-b) the total physical work done after parking. This includes the work done while walking to the entrance, as well as the work done after shopping and exiting the building. Let's focus on objective-b here, given that objective-a has been analyzed before, using the following notation.

Parking coordinates (O, D), where
O = walking distance from the parking spot to the entrance, and
D = walking distance from the exit to the parking spot.
M = mass of the person,
S = expected mass of purchased items, and
(μ, g) = constants denoting the coefficient of friction during walking, and the acceleration due to gravity, respectively.

Work done = force * distance = μg * mass * distance (A prior blog shows how to optimize our in-store shopping route.)

Objective is to minimize: M*O + (M+S)*D

A minimal work objective suggests these simple rules:
1) Heavy shopping: park close to the exit. 
2) Light shopping: park to minimize total walk.

Thus, the goodness of a parking spot depends on the shopping context. Let us figure out a good parking spot for the shopping scenario below.

Linear Store, Manhattan Distances
Consider a long, 'linear' store along the x-axis, with the exit @ x = 0, and entrance @ x = L. Assume 'Manhattan' walking distances ( 1) and that prior customers selected spots nearest the building along y-axis, and picked their spots along the x-axis based on individual preferences. Given this, the distance we can expect to walk to/from the store along the y-axis is already (near) minimal. This leaves us with a (non-convex) one-dimensional search for open locations x(i) along the x-axis over three regions. Let us split this task into two steps. 

Step-1: Find the best spot within each region
A) x(i) = -a  0 
Minimize M(O+D)+S*D = M(L+a +a) + Sa = ML + (2M+S)a*

B) 0 ≤ x(i) = b ≤ L
Minimize M(L-b + b) + Sb = ML +Sb*

C)  x(i) = L+c  L
Minimize M(c+L+c) + S(L+c) = ML+SL + (2M+S)c*

The optimal x* within each of these regions is the one closest to the exit. This is independent of S and L, and identifiable by greedy search.

Step-2: Finding the least cost spot among (a*, b*, c*)
The worst spot in B is no worse than c*, independent of S and L, yielding a binary choice: pick a* or b*.
x(i)  0: incremental cost = (2M+S)a*, a* ≥ 0
x(i) ≥ 0: incremental cost = Sb*, b* ≥ 0

For small values of S, b* dominates and is optimal for light shopping or window shoppers. As S increases and becomes comparable to M, b* is preferable when:
b*/a*  ≤ 1 +2(M/S)

Even if we 'shop till we drop' and carry our own weight, b* can be as much as 3a* and still dominate.

Practically speaking, b* is a solid bet, but when B is full, the shopper is forced to choose between disjoint regions A and C.
x(i)  0: incremental cost = (2M+S)a*
x(i) ≥ L: incremental cost = SL + (2M+S)c*

shoppers would prefer a* to c* unless:
(a*-c*) > L/[2(M/S)+1]

Scenarios:
i) Between spots equidistant from the entrance and exit, a* dominates c*, independent of S and L. 
ii) For the 'carry our own weight' scenario, a* is preferable when
(a*-c*)   L/3
iii) For unmanageably large S, a* remains preferable if:
(a*-c*)  L

We can now draw some conclusions.

Finding a Minimum-Work Parking Spot
Preferred order of parking is:
b* > a* > c*

which is out of order. The actual search pattern we employ may depend on whether the aisles in the parking lot are along the x- or y-axis. 

Light/medium shopping context
Clockwise, starting from the exit, scan B, park if feasible. Else scan C, and park if feasible. Else, turn around choose a spot in A. 

Heavy shopping context
Clockwise, starting from the exit, scan B, park if feasible. Else turn around, scan A, and park if feasible. Else, choose a spot in C.

Saturday, May 16, 2015

Activity Tracker Analytics - Part 1: Fun with Fit-Bits

I've been experimenting with fitness and activity tracking devices the last few months. Somehow, I ended up testing three of them (let's call them blue, red, and green), each from a different company, one of them being a 'fit bit'. Blue and red showed similar daily readings, which also seemed to tally with small manual walking samples I took. On the other hand, the cheap, low-end green device was way off and severely under-predicting. Rather than simply junk the green tracker, can we 'rescue' it by noting its measurements and then optimally re-calibrate it using a more accurate tracker? This is the simple idea of this blog.

Figure 1 shows a one-month sample of normalized daily step-count readings obtained from the three trackers.
Figure 1.


The blue and red represent the 'good trackers', and the green one, which we wanted to junk, is the green line. This plot shows that although trackers from different manufacturers can differ significantly in terms of the absolute number of steps they count, their relative readings between days is likely to be more consistent. If you walk more, it is quite likely that the tracker will count more steps. Comforting.

This February 2015 JAMA article discusses the quality of readings from a variety of activity trackers.  Here is a snapshot of a paragraph from the preview page of this journal article.


(Picture source: preview page from http://jama.jamanetwork.com)

It appears that this paper also mentions good 'intra-device' repeatability. This consistency of response (something that is incredibly important to ORMS decision support systems) offers hope for our green tracker.  However, there is also plenty of scope for noise. The counting is done based on an accelerometer/sensor, and therefore, acceleration is what it detects and translates into step counts. If you are not a smooth driver during your morning and evening commute, you will have 'walked' a lot. I've taken a lot of steps driving my lawn mower tractor for 45 minutes. Different trackers respond differently to specific types of activity. Exceptions aside, these devices are generally quite useful. Moreover, they do really tell us if our exercise levels have increased or dropped over time, which is a very useful and healthy thing to know. This second figure below shows the ratio of step counts between two successive days.

Figure 2

The green-tracker looks pretty reasonable compared to the other two when it comes to reporting the relative response over time. During peak days, it closely matches the blue tracker, while on other days, it sticks reasonably close to the blue and red lines. Therefore, the green tracker is not a total write-off. We can rescue it by re-calibrating it upward. For example, let us assume the average of blue and red as the 'true' reading and employ linear regression (minimizing sum of squared 'error') to identify the green correction, as shown in Figure 3 below.

Figure 3.

For this specific usage profile, scaling the green reading up by 12% and adding 0.32 gets us close to the red and green numbers. However, the presence of peak-days may have skewed our calibration, so this may not be an 'optimal' idea. Let us remove the peak-days, and also swap the X and Y axes to get a 'normal day' recalibration. The result is shown in Figure 4 below.

Figure 4.

Aha! This regression equation is interesting. The R-squared value drops a bit, but more importantly, it suggests that we may do not need to do scaling. We can do something as simple as adding 0.36 to the green reading. Of course, the relative response plot in Figure 2 should have given us that clue. Did the green-tracker company engineers miss a trick here: Do these missing '0.36 steps' represent a default 'idle' activity level that they forgot to account for? If the green engineers spread the 0.36 over 16 waking hours, their final readout would be in good shape. Let us compare the output of this (0.36 + green) with the blue-red plot in our last and final figure.

Figure 5.

By simply adding 0.36 to the count of the cheap tracker, we have obtained a good daily step count that compares well with the more expensive 'blue-red' trackers. Go Green!

Tuesday, March 24, 2015

Mumbai Dabbawalas: Operational Excellence Based on Trust Chains and dharma

Most business case studies, research papers, and news articles on the Mumbai dabbawalas (MD) focus on, and rightly marvel at the fact the MDs were awarded a remarkable 'six sigma' western certification based on the less than one-in-million statistical error rate in their daily delivery of home-cooked meals to many thousands of Mumbai workers for over a hundred years now. As background, here is one of the earlier articles, written ten years ago, on this astonishing team. Please read this article first, since the remainder of the discussion will assume familiarity with the MD supply chain. The MDs have built a zero carbon-footprint, health-enhancing, almost perfectly-reliable, organically sustainable, hyper-personalized supply chain. Profitably achieving even one of these objectives would be considered a victory for modern day supply chains. Rather that again focus on what they achieved and how (and both questions are of great interest to the Operations Research and business analytics community), the more interesting questions for me as I began learning about the dabbawalas were:
how can they sustain this? and why do they?

Business case studies and news articles skip these questions. Luckily, I found at least two sources of information that I could tap into to try and answer these questions to my own satisfaction. We'll start with the 'how', and then the deeper, related question of 'why'.

How do they sustain it?
We turn to Prof. P. Kanagasabapathi's gem of a book "Indian Models of Economy, Business and Management (3rd Edition)", and see what he has to say about MDs. I must add this: I have come to learn, over the last few years that the Indian economy is like a complex number. It has a real part and an imaginary part. The latter is covered by CNBC, Bombay Stock analyses, and Ivy-league university economic theories faithfully imported and regurgitated in Indian colleges, and gobbled up by students and economists.  If we want to understand how the real part works, read this book, and Dr. R. Vaidyanathan's equally brilliant 'India, Uninc'. Both are data-driven books, and offer us the reality based on deep insights into how the Indian society and mind actually function. They are available in paper and Kindle editions, and ridiculously under-priced.

Let us see what Prof. PKS has to say (emphasis in bold / square bracket is mine):
"...the dabbawala business in Mumbai is an innovative business designed and executed by a group of uneducated and undereducated people from the ordinary classes to suit the local conditions. The business plan is so designed to make it perfectly functional, while at the same time keeping it cost effective.

"....see how the supply chain management works. The dabba-wallas are semi-literate people, with rural backgrounds from Pune district. They belong to the warrior [clan] of Malua, which fought for [the great Indian king Shivaji] in the earlier days. In the 1890s, one Mahado, a migrant from their area started the supply of lunch boxes. Today under the banner of Nutan Mumbai Tiffin-box Suppliers Association, more than 4500 of them are involved in supplying nearly 2,00,000 boxes every working day. Braving Mumbai weather conditions and difficulties involved in multiple transfer points, these `ordinary' people make only one mistake for eight million deliveries "I.It is no wonder that the Forbes Global Magazine gave them a Six Sigma efficiency rating on par with multinational companies such as Motorola and General Electric. In fact, the efficiency of dabbawallas is much better than the Six Sigma levels fixed by the experts for world class performances. As a result they are now admired as the model for the global corporations...While mega corporations use the most modern technologies and employ highly qualified technical and management experts to reach higher levels, how could these ordinary people from village backgrounds with only their common sense and limited resources better the benchmarks fixed for the most efficient companies in the world? Is it not due to the effective teamwork and most efficient planning? Are these people not practising the most effective methods to serve their customers? In the case of modern corporate sector, they search for different methods to sell their products. In some cases, the products may not be essential to the customers. But still they try to look for different ways to attract customers and sell their products. In the case of dabbawallas they have devised a way to serve the customers who would like to eat home-made food, and in the process they have made it so well that they have become world-class service providers.

We start to get some answers above on the 'how'. Now we turn to find answers for how they're able to sustain this:
".. community relationships provide certain benefits and cost advantages in business. One is trust, which is very important for business. Communities generate high levels of trust due to their close-knit relationships. Second is the lower transaction costs compared to the rates determined by the markets. As a result, efficiency is increased and costs are reduced..."

Trust. It can dramatically reduce costs and boost efficiency. Every multinational company's employee brochure strongly emphasizes the importance of 'trust' and 'teamwork'. However, it is not easy build a high degree of cross-organizational trust in today's western workplace. why? Dr. Kanagasabapathi quotes Francis Fukuyama:
"The ability to associate depends, in turn, on the degree to which communities share norms and values and are able to subordinate individual interests to those of larger groups. Out of such shared values comes trust, and trust, as we will see, has a large and measurable economic value." Trust results in `social capital.'"

Trust can arise out of that bi-directional relationship called mutual respect. This blog I wrote a few years ago views mutual respect as a necessary and sufficient condition for building trust in a workplace.  If one party dilutes its commitment, and merely tolerates rather than respect, this trust is broken. The modern workplace is contractual. Order is enforced, and chaos is contained by a variety of standard background checks, zero and non-zero tolerances, and legal penalties. One of India's most important thought leaders, S. Gurumurthy has pointed out that 'Capitalism requires employers, Communism banks on employees. Traditional Indian economies are entrepreneurial and require neither'. Rather, they rely on trust chains built upon mutual respect, which produce social capital. To learn more about social capital, Dr. P. Kanagasabapathi turns to Aiyer:
"From time immemorial, groups of people have created strong communities, based on commonly observed rules and mutual self-help. These social links discourage deviant behaviour through ostracism and other social penalties, create a climate of trust in which agreements are honoured and grievances redressed, and facilitate collective action against threats from outsiders and risks from natural disasters. This is social capital..."

Thus, the MDs have been able to sustain their dizzying levels of operational reliability and quality levels by achieving a high degree of trust within their organization and the mutual respect between self and customer.

Why do they?
The 'why' takes us even deeper. For this, I'm indebted to the head of the Indian embassy in Vancouver, Canada. Listen to his brief talk about the MDs in this You Tube video (watch from 9:33)




The Dabbawalas are doing their dharma, their cosmic duty. This idea of cosmic/sanctity implies an unmanifest motive to their duty. The effect that dharma has on the dabbawala output is real, measurable, and has made him go far beyond the so-called 6-sigma level of quality. As the consular head points out in his talk, when the Dabbawalas handle, deliver, and serve food, they also perform a sacred service, a seva.  As mentioned in a previous blog here, an Indian business model seeks not unconstrained profit maximization, and nor is it non-profit, for neither are sustainable, but it shubh laabh, or auspicious profitability. There is a harmonious balance between the worldly and the unmanifest. The Indian idea of seva is different from the western conception of service. As Gurumurthy once pointed out (via the wonderful anecdote of Swami Vivekananda and the philanthropist Rockefeller), the Indian giver thanks the receiver, not the other way around. While the manifest, material benefit does indeed go to the receiver, the higher, unmanifest benefit from this good Karma accrues to the giver. Who, then is the giver, and who is the receiver? The entrepreneurial Dabbawala will continue to serve, innovate, and sustain operational excellence provided there is: demand for his service, trust at every point of interaction in the supply chain, and he chooses to do his dharma.

Tuesday, February 24, 2015

Hunting for Optimality

OK. Sometimes, we really do need to find 'the' answer. Recall the scene from Jaws: "It's a shark, not the shark". But in general, seeking 'the' one and only, true, unique, prophetic optimal solution to real-life decision problems is an exercise in futility. It makes sense to talk about the best practically achievable solutions given resource constraints, costs, and priorities, which can then be iteratively refined over time. While filling out a healthcare quiz about better nutrition and weight management, I was delighted to see this question.


The health-care researcher who designed this quiz deserves a round of applause.

But how do Operations Researchers find such solutions? Sometimes, the problems are provably cute (journals love to publish these).

But very often in practice, you end up dealing with this:


No fear. Well-designed practical algorithmic approaches employing robust, industrial-strength optimization tools like CPLEX can help OR'ers recover high quality solutions to challenging, seemingly intractable, messy-data riddled, real-world decision problems.

Losing out on the perfectly good in a quest for the perfect seems pretty silly.

Sunday, February 8, 2015

RT if you agree, FAV if you don't: Does it work?

A simple way of binary polling on twitter that reaches a large number of voters, especially if the polling handle (@H) is sufficiently popular, is to get followers to re-tweet (RT) the message if they agree with the proposition P, and 'favorite' (fav) it if they disagree.


In the above poll, while Kejri is as phoney as they come, the result shouldn't be this skewed.

(This is just a cursory analysis)

Suppose m followers of @H RT, and fav. This gives us a m/n ratio among @H's followers. Next:
a) The message gets forwarded to the followers of the m "RT" handles
b) The message is not forwarded to the followers of n "fav" handles

and this RT'ing process continues. As long as the 'agree' nodes in RT chain via (a) represent random samples, this poll can work reasonably despite only the ayes propagating the message. i.e., the RT probability of the followers of an 'agree' handle (@YES) should not be influenced by @YES' RT (i.e., there are no significant 'vote-banks'). If birds of the same feather flock together, this assumption may not hold, and we are likely to see a disproportionate number of 'agree'. On the other hand, if the poll reaches any 'disagree' handle whose followers are also likely to disagree, the poll does not reach any of these followers, skipping many of the 'disagree' nodes of the social network. The final result may be skewed favorably toward 'agree'. Of course, the nays need not just 'fav'. Then can create their own separate tweet that links this poll, and share this with their followers. Perhaps @H can send out a modified tweet:

'Proposition P: RT if agree. Fav and share this msg if u don't'.

This additional step may restore some balance. However, the burden of extra work falls on the 'fav' group, and only the enthusiastic 'fav' folks are likely to oblige. The final result may remain skewed in favor of 'agree' but could yield a better result compared to the unmodified polling tweet.

Alternatively, @H could send out two independent tweets, the first requesting an RT for agree, and the second, an RT for 'disagree'. Will this 'RT competition' work better? (RT if you agree, RT if you don't :)

Sunday, January 18, 2015

Strike Rate Analysis of AB de Villiers' Innings of 149(44)

A quick blog on today's amazing knock by AB.

Here's the archive of Cricinfo's online commentary for the cricket match where South African batsman AB de Villiers scored the fastest ever ODI cricket century. Here are the stats. He batted just 44 balls for his 149 runs that included 16 sixes. Here's a graph of his cumulative strike rate throughout the innings in runs per 100 balls.

His highest cumulative strike rate was 400 after the first ball, and thereafter, the lowest it ever reached was 200, after 4 balls. His first fifty took 16 balls, and his second fifty was even faster, coming of just 15 deliveries, giving him the record 31-ball century. He scored no runs of the last two balls he faced, causing his final strike rate to dip below 350 and end at 339.

AB was at the crease for just 44 minutes. In comparison, the slowest international hundred (in test cricket, which can be very different) in history consumed 557 minutes.

As far as instantaneous strike rates throughout the innings, we can observe a 13-ball stretch (28th to the 40th ball) where he scored 63 runs to move from 82 to 145, at a strike rate of 485 - suggesting that in that period, like Viv Richards, AB was in two minds - whether to hit the bowler for a 4 or 6.

Here's a grainy YouTube video of today's innings.

 

The previous fastest ODI century consumed 36 balls, which yields a strike rate of less than 300. AB's final strike rate in this innings is higher than the expected book-cricket team strike rate of around 325.



Tuesday, January 6, 2015

Some OR aspects of Hidden-City Airfare Ticketing

Read this interesting discussion and reader comments on  "Hidden city" airfare ticketing (HCAT)

(picture is linked from this dealnews.com post)

The article quotes a NY times post that explains HCAT nicely and ends like this: "If you want to travel to Dallas, the best way to get a reasonable fare is to book the flight to Los Angeles instead, and simply get off the plane at Dallas."

The passengers don't appear to be doing anything illegal by getting off. Nobody has been arrested yet, at least. The airline is within its rights to employ all legal means to curb this practice. UA is suing a 22-year old for his website that seems to help people with HCAT. Some of the reader comments in response to these HCAT articles are interesting.

Is this seemingly weird pricing structure a rare but predictable outcome of optimally managing fares for a hub-spoke network? Or is it due to some less-than-realistic assumptions underlying the combinatorial optimization formulations within their revenue management, fleeting, and schedule planning models?

Consider the hotel analogy: Do hospitality RM systems create situations where one can purchase a cheaper hotel stay for 3 nights including a weekend but check out on Friday night? Surely one would expect a price consistency-check layer in place that would prevent such a scenario. Of course, when one has to consistently price to maximize revenue expected from predicted demands for millions of different itineraries, it can get quite complicated.

In OR revenue management practice, we have had to build pricing engines to manage request-for-quotes (RFQs) for a bunch of items that often involve complex demand interactions. If the customer is allowed to cherry-pick and is not bound to an all-or-nothing type bundle deal, the pricing optimization analytics we develop will naturally have to account for this. While life would be so much more easier if customers did not cherry-pick, explicitly blocking cherry-picking is not a great idea since it completely eliminates customer flexibility. Customers will simply take their business elsewhere. Thus, one option is to manage cherry-picking using 'soft' constraints.

Economics can make companies adopt seemingly strange pricing and assortment management practices. The rough equivalent of HCAT for Starbucks is 'the case of the missing short coffee cup' discussed in Dr. David Simchi-Levi's book on Supply Chain Management (SCM):
"they will serve you a better, stronger Cappuccino if you want one, and they will charge you less for it"... but why does this cheaper, better drink ...languish unadvertised?... Businesses try to discourage their more lavish customers from trading down by making their cheaper products look or sound unattractive...the bottom end of any market tends to get distorted" As far as I know, Starbucks has not blocked the book authors.

The book mentions how & why, in the early days of the railway, in some places, a 3rd class carriage was deliberately left roofless even though it was pretty cheap to build one. The customer utility of the least profitable option is (ruthlessly) reduced, enough to discourage trade-downs but not bad enough to lose their economy customer segment to competitive options. Thus, if you want to deplane at Dallas, it seems that you will have to take your chances and not make it a habit. If we try to advertise or game this, it is apparent the companies are SCM-bound to come after us and make HCAT a most unattractive option.

Happy New Year!



(views expressed in this blog are personal)

Saturday, November 29, 2014

Calvin and Hobbes TSP

Even if Calvin finds the correct, feasible tour traversing the 23+ 'cities', it is never going to be Hobbes-optimal.


(pic source: twitter)

Thursday, November 20, 2014

The Contextual Optimization of Sanskrit

I'd written a blog for the INFORMS conference earlier this month based on my practice perspective, which emphasized the importance of contextual optimization rather than despairing over the 'not infallible' theoretical worst-case nature of certain mathematical problems. This is something well-internalized by those in the large-scale and non-convex optimization community, where 'NP-Hardness' is often the start, rather than the end point of R&D.

The wonderful 'Philip McCord Morse Lecture' at the recently concluded INFORMS conference in San Francisco by Prof. Dimitris Bertsimas of MIT touched upon this point, and the 'conclusions' slide in the talk explained this idea really well. To paraphrase, 'tractability of a problem class is tied to the context - whether the instances you actually encounter can be solved well enough'. I mentioned the Sulba Sutras in that blog - a well known body of work that epitomizes the Indian approach to mathematics as Ganitha - the science of computation. The genius, Srinivasa Ramanujan, was a relatively recent and famous example of a mathematician hailing from this tradition. The Indian approach is often algorithmic and more about rule generation than infallible theorem proving. Not that Indians shied away from proof ('Pramaana'. For example, see 'Yuktibhasa'). As I understand it, this sequential process of discovery and refinement does not lose sleep over theoretical fallibility, and consists of:
a) in-depth empirical observation of, and a deep meditation on facts,
b) insightful rule generation,
c) iterative, data-driven refinement of rules.
This quintessential Indian approach is applied not just to math, but to practically every field of human activity, including economics, commerce, art, medicine, law, ethics, and the diverse dharmic religions of India, including Hinduism and Buddhism. Panini's Sanskrit is a great example of this approach.

Panini, the famous Sanskrit grammarian (along with Patanjali) is perhaps the most influential human that much of the world does not know much about. His fundamental contributions to linguistics more than 2000 years ago continues to transform the world in many ways even today. Noted Indian commentator, Rajeev Srinivasan, has recently penned a wonderful article on Panini and Sanskrit. You can learn more about Panini's works by reading Dr. Subhash Kak's (OK State Univ) research papers (samples are here and here). This blog was in part, triggered by this article, and talks about Sanskrit and its contextual optimizations.

Abstract: Sanskrit recognizes the importance of context. Two examples that show how Sanskrit is optimized depending on the context, in two entirely opposite directions, is shown below.

Optimization-1. The grammar is designed to be entirely context-free as Rajeev Srinivasan's article explains, and anticipated the 'grammar' of today's high-level computing language by more than 2000 years: precise with zero room for ambiguity of nominal meaning. To the best of my knowledge, punctuation marks are not required, and order of the words can be switched without breaking down, although there may be personal preferences for some orders over the others, and the sentence remains unambiguously correct. An optimization goal here therefore is to generate a minimum (necessary and sufficient) number of rules that result in an maximally error-free production and management of a maximal number possible variations of Sanskrit text. In this case, Panini appears to have achieved the ultimate goal of generating a minimal set of rules that will produce error-free text, forever. There are other well-known optimizations hidden in the structure and order of the Sanskrit alphabet - more on that later.

Optimization-2. The final interpretation of many keywords in Sanskrit ARE contextual. Which means there are multiple, related interpretations for some words that have a nominal/generic meaning, but you have to optimize the final interpretation at run-time by examining the context of usage, to recover the most suitable specific choice. If the first optimization helped eliminate fallibility, this second optimization in a sense re-introduces a limited fallibility and a degree of uncertainty and freedom by design! This feature has encouraged me to reflect (recall Ganesha and Veda Vyasa), develop a situational awareness while reading, pay attention to the vibrations of the words, and grasp the context of keywords employed, rather than mechanically parse words and process sentences in isolation. A thoughtful Sanskrit reader who recognizes this subtle optimization comes away with a deeper understanding.  For example, Rajiv Malhotra, in his book 'Being Different' (now in the top-10 list of Amazon's books on metaphysics) gives us the example of 'Lingam'. This can mean 'sign', 'spot', 'token', 'emblem', 'badge', etc, depending on the context. Apparently, there are at least 16 alternatives usages for 'Lingam' of which one best suits a given context is picked, and not simply selected at random. And of course, the thousand contextual names ('Sahasranamam') for Vishnu is well known in India. Some well-known western and Indian 'indologists' have ended up producing erroneous, and often tragic translations of Sanskrit text either because they failed to recognize this second optimization, or because they misused this scope for optimization to choose a silly interpretation, leading to comic or tragic conclusions.

Again, this contextual optimization approach by the ancient Indians is not just restricted to Sanskrit, but is employed gainfully in many areas, including classical arts, management, healthcare, ethics, etc., and of course dharmic religion. This contextual dharmic optimization has perhaps helped India in getting the best out of its diverse society, as well as keep its Sanskriti refreshed and refined over time. For example, the contextual ethics of dharma (ref: Rajiv Malhotra's book) has a universal pole as well as a contextual pole that allows the decision maker faced with a dilemma, to not blindly follow some hard-wired ideological copybook, but contemplate and wisely optimize his/her 'run-time' choice based on the context, such that himsa is minimized (dharma is maximally satisfied). Some posts in this space has tried to explore the applications of this idea'.

An earlier blog discussed a related example of seemingly opposite goals for contextual optimizations. When it came to mathematical algorithms, data, and linguistic rules in Sanskrit, a goal was to be brief and dense, minimize redundancy, and maximize data compression, so that for example, an entire Sine-value table or generating the first N decimals of Pi can be both encoded and decompressed elegantly using terse verse. Panini's 'Iko Yan Aci' in the Siva Sutras is a famous example of a super-terse linguistic rule. On the other hand, when it comes to preserving long-term recall and accuracy of transmission of Sanskrit word meanings as well as the precise vibrations of mantras (e.g. Vedic chants) that are critically linked to the 'embodied knowing' tradition of India, the aim appears to be one of re-introducing controlled data redundancy to maximize recall-ability, and error-reduction. This optimization enabled Sanskrit mantras to be accurately transmitted orally over thousands of years.

To summarize, contextual optimization is a powerful and universal dharmic approach that has been employed wisely by our Rishis, Acharyas, Gurus, and thinkers over centuries to help us communicate better, be more productive, healthier, creative, empathetic, scientific, ethical, and interact harmoniously with mutual respect.

update 11/22/2014: 'optimize the final interpretation at parse-time / read-time' is the intent for optimization-2, rather than the computer-science notion of 'interpretation at run time'.

Saturday, October 25, 2014

Lassoing the Exponential

An abbreviated version was blogged for the INFORMS 2014 annual conference as 'Not Particularly Hard'.
-------------------------------------

While working on a new retail optimization problem a few weeks earlier, a colleague was a bit disappointed that it turned out to be NP-Hard. Does that make the work unpublishable? I don't know know, but unsolvable? No. The celebrated Traveling Salesman Problem (TSP) is known to be a difficult problem, yet Operations Researchers continue to solve incredibly large TSP instances to proven near-global optimality, and we routinely manage small TSP instances every time we lace our shoes. Why did I bring up laces? In a moment ...

Hundreds of problems that are known to be difficult are 'solved' routinely in industrial applications. In this practical context it matters relatively less what the theoretical worst-case result is, as long as the real-life instances that show up can be managed well enough, and invariably, the answer to this latter question is a resounding YES. The worst-case exponential but elegant 'Simplex method' continues to be a core algorithm in modern-day optimization software packages. 

This issue of contextual optimization is not a new one. For some ancient people who first came across 'irrational' numbers, it was apparently a moment of uneasiness: how to 'exactly' measure quantities that were seemingly beyond rational thought. For some others, it was not much of an issue. Indeed, there is an entire body of Ganitha (the science of calculations, or mathematics) work in Sanskrit, the 'Sulba Sutras', almost 3000 years old, where irrational numbers show up without much ado. 'Sulba' means rope or lace or cord. If we want to calculate the circumference of a circle of radius r, we can simply use (2πr) along with an approximation for 'π' that is optimally accurate, i.e., good enough in the context of our application. If we we did not have a good enough value for π, we could literally get around the problem: simply draw a circle of radius r, and line up a Sulba along its circumference to get our answer. For really large circles, we can use a scaled model instead of ordering many miles of Sulba. Not particularly hard. Encountering a really difficult optimization problem can be a positive thing, depending on how we respond to it.  Often, there are alternative approaches to business problems that at first glance, appear to have  insufficient data: this tempts us to throw in the towel and send the problem back to the customer and say "infeasible" or "unbounded". Instead, we can use a Sulba and Lasso our decision variables. This could well be an ORMS motto:
"When the going gets NP-Hard, Operations Researchers get going" :)

Saturday, September 6, 2014

Jugaad for Moto-E Video chat

I recently got a family member in India a really cheap but very useful smartphone, the Motorola Moto-E.

 

A problem is that this phone only has a front-facing camera. Moto-E holders have to turn the phone around for us to see them during a video chat, depriving them of a view. Of course, if both callers are using Moto-Es, video-chats get a bit more frustrating.  A simple Jugaad to fix this is to have the Moto-E holders sit in front of a dressing mirror during the video-chat. I'm sure somebody figured this out long ago but I got a small kick out of it.