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 (ℓ¹) 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.

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!

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

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" :)

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.

The Best Decisions are Optimally Delayed

The lessons learned from the last few years of practice have convinced me that analytics and OR (OR = Operations Research), or at least MyOR is mainly about learning the art and science of engineering an optimally delayed response. Good analytics produces an optimally delayed response.

But why introduce a delay in the first place? Isn't faster always better? 'Science of better' does not always mean 'science of faster'. From age-old proverbs we find that in between 'haste makes waste or knee-jerk reaction' and being 'too clever by half' lies 'look before you leap'. If we view Einstein from an OR perspective: "Make things as simple as possible, but not simpler", the reason seems clearer. We must make situation-aware and contextually-optimal decisions as fast as possible, or as slow as necessary, but not faster, or slower, i.e., there exists a nonzero optimal delay for every response decision. A middle path in between a quick-and-shallow suboptimal answer, or a slow-and-unwieldy 'over-optimized' recipe. Of course, one must work hard during this delay to maximize the impact of the response, and put Parkinson's law to good use, as suggested below:

#orms methods often *delay* product response to find superior answers. Tricky to pick optimal (delay, improvement) pair :)
— (@dualnoise) August 1, 2014

See this old post on 'optimally delaying an apology' to maximize benefit to the recipient, or recall the best players of every sport being able to delay their response by those few milliseconds to produce moments of magic, or Gen. Eisenhower delaying the call to launch D-Day. In the same way, a good OR/analytics practitioner will instinctively seek an optimal delay. For an example of this idea within an industrial setting, read this excellent article by IBM Distinguished Engineer J. F. Puget on taxicab dispatching that he shared in response to the above tweet. Implication: If your analytics system is responding faster than necessary, then slow it down a bit to identify smarter decision options. The 'slower' version of this statement is more obvious and is a widely used elevator pitch to sell high-performance analytics and optimization tools.

The history of the 'optimal delay' is many thousand years old, going back to the writing of the world's longest dharmic poem, the Mahabharata, which also includes within it, the Bhagavad Gita, one of the many sacred texts of Hinduism.

(pic link: http://www.indianetzone.com)

The story about how this epic came to be written is as follows:
Krishna Dvaipana (the Veda Vyasa) wanted a fast but error-free encoding of the epic that could be told and re-told to generations thereafter. The only feasible candidate for this task was the elephant-faced and much beloved Ganesha, the Indian god of wisdom and knowledge, and remover of obstacles. The clever Ganesha agreed to be the amanuensis for this massive project on the condition that he must never be delayed by the narrator, and must be able to complete the entire epic in ceaseless flow. Veda Vyasa accepted but had his own counter-condition: Ganesha should first grasp the meaning of what he was writing down. This resulted in a brilliant equilibrium.

Veda Vyasa composed the Mahabharata in beautiful, often dense verse that Ganesha had to decipher and comprehend even as he was writing it down without lifting the piece of his tusk that he had broken off to inscribe, from the palm leaves. If Ganesha was too slow, it would potentially give Vyasa the opportunity to increase the density and frequency of incoming verses that may overload even his divine cognitive rate. If he went too fast, he would risk violating Vyasa's constraint. Similarly, if Vyasa was too slow, he would violate Ganesha's constraint. If he went too fast, his verse would lose density and risk becoming error-prone, and of course, then Ganesha would not have to think much and perhaps write it down even faster. Imagine if you will, a Poisson arrival of verses from Vyasa divinely balanced by the exponentially distributed comprehension times of Ganesha. Writer and composer optimally delayed each other to produce the greatest integral epic filled with wisdom ever known; written ceaselessly in spell-binding Sanskrit verse, without error, and flowing ceaselessly to this day without pause.

I can think of no better way to celebrate Ganesha Chathurthi than to recall and apply this lesson in everyday life.

Indian elections 2014: Long words, short story

Can long, archaic words be used to maximize overall brevity (and levity)? Take the 2014 Indian general elections that recently concluded. Although the final results will come out on May 16 (the amazing Narendra Modi as Prime Minister), exit polls already give us this clear-enough picture:

India has understood that the phoney "Idea of India" brand of secularism is nothing but antidisestablishmentarianism in disguise, and we are witness to the historical floccinaucinihilipilification of the Nehru-dynasty by the Indian voter.

Traveling Salesman Problem in a Portrait?

I'd planned to stop blogging until May this year to do my small bit in helping Narendra Modi become the next Prime Minister of India in the Indian general elections to be held very soon - one that will determine the future of my family there, as well as the destiny of 1.2 Billion Indians. India has suffered from a curse of culpable silence in the last ten years, but now it seems, that is changing, thanks to inspiring examples like these that asks people to come out and 'Vote for India' (thanks to @sarkar_swati,  faculty at U-Penn, for sharing this video).
------------------------------------------------------------------------------

By sheer coincidence, this brief blog, like the previous one, is related to Asian (Japanese) art, and one i felt 'compelled' to do. Thanks to @SimoneCerbolini for sharing this beautiful portrait on twitter. What is interesting about this art is that it was done, as Simone tweets, using "a single thread wrapped around thousands of nails. Artwork "Mana" by Kumi Yamashita"

The artist, Kumi Yamashita, has a facebook page, and here is another picture from there.

The effect is stunning, and one marvels at the human 'cognitive shift' that convinces us that within this collection of thread and nails, is a lady. Here is a brilliant talk by neuroscientist V. S. Ramachandran (Director, Center for Brain and Cognition, UC, San Diego) on 'Aesthetic Universals and the Neurology of Hindu Art' that explains this in depth.



From the operations research perspective, we gravitate toward the mathematical problem hidden in this portrait: determining the least length of thread to traverse through all these nails. A mathematical optimization model that can be used to answer this question is the celebrated 'Traveling Salesman Problem' (TSP), which is known to be difficult to solve, in theory. In practice, however, extremely large instances have been solved to provable optimality.

Here is another page that displays a collection of pictures from the artist's 'constellation series'. It also includes this ultra-close up that lets us see how the threading really progresses at the micro-level.

Each nail is traversed multiple times, and a greater density of thread is used to create a darker shade (e.g. the eye and the brow). Additionally, there appears to be a greater density of nails in that area. Can a thread-traversal path generated by a TSP solver (e.g. concorde) produce a similar effect to the eye and the brain? I'm not sure, although it may still produce 'a reasonable picture of a lady'. If the density of nails is increased in these areas, then perhaps the TSP-artwork may do a good job. Alternatively, it may be possible to modify the TSP network structure to induce such an effect.

Optimize Your In-store Holiday Shopping Route

Remember the last time you were not tired after holiday shopping in a busy mall, bulk shopping at a discount-club store, or weekend shopping at a crowded grocery store?

(source links: http://info.museumstoreassociation.org, http://binaryapi.ap.org)

Hopefully, the simple and preliminary 'operations research (O.R)' analysis in this post can help make the experience a little less stressful and maybe even let us enjoy a bit of retail therapy that we can't get online.  The shopping optimization problem addressed here is simple one, albeit with a twist. This post was triggered by an observation made after recent shopping expeditions to a nearby Costco outlet.

We have a long shopping list of L line-items (i) of various quantities N(i) that we have to pick up in a store. How should we optimally reorder our shopping list to reflect the sequence in which we pick up these items?




Version 1
The simple version aims to minimize total shopping time. For example, we can formulate this as an instance of the so-called traveling salesman problem (TSP) that finds the shortest sequence that starts at the entrance, visits each of the L 'cities' once, then the checkout counter, and ends at the store exit (entrance). A google search shows this 2009 research paper by researchers at UPenn, which shares the technical details and interesting results for this version.

To simplify our problem, we assume that the topology of the store is prior knowledge, and we can roughly pre-assign items in the same aisle to the same 'city'. The resultant problem is to find the order of visits to the aisles of interest to us. If the aisles are neatly arranged as node intersections in a rectangular grid, then we simply have to find the shortest rectilinear "Manhattan" distance tour in this grid. Depending on the type of the store, the store-layout itself may be optimized by the retailer based on the observed foot-traffic and 'heat-map' data. For example, it may be designed to retain the customer in the system to increase chances of purchase (exploratory tour, store selling expensive luxury/fashion products), or quickly out of the system (routine tour, obligatory products like groceries), or based on some other goal. Store space and layout problems are known to be commercially useful optimization problems in the retail industry.

Picture linked from an iTunesApp (Concorde) page of Prof. Bill Cook that solves TSPs :)

Version 2
Let us additionally assume that product attributes have an impact on our order. Suppose one or more items in our list is located in the frozen section at a grocery store, then we may prefer to get there at the end of our tour. Luckily, many stores appear to anticipate this (?), and locate this section towards the end of the store. Thus if 'maximum freshness' or 'minimum damage' is an additional consideration, this may alter the TSP route and the final ordering of items in our shopping list.

Version 3
This was the problem that was of immediate interest to me today. Costco sells stuff in bulk, so the items tend to be heavy, and considerable energy is expended moving the cart through the store. At the risk of mangling undergrad physics, let us proceed with our analysis...
Let μ be the (constant) coefficient of rolling friction between the wheels of the shopping cart and the store-floor. Then the work required to move mass m through distance d = force x displacement =μmgd, where g is the (constant) acceleration due to gravity. Thus a squeaky-wheeled cart will make us work extra hard. Speed of shopping is a consideration if we want to keep track of power (force x velocity). Covering the same tour length in half the time requires twice the power, i.e. the rate at which our body expends stored energy.

Carry versus Cart (reinventing the wheel)
If we had zero rolling friction, technically the only work involved is in lifting items and putting them in our cart. We can assume that this work is independent of our order of visit and is a fixed quantity. On the other hand, if we are not working with a wheeled-cart, but carry our stuff in a market-basket or shopping bags, then we have to raise the potential energy of the items to height 'h' (mgh) all the way until checkout, and also overcome the sliding friction between our shoes and the floor, which would probably be higher than the rolling friction, as illustrated below.

(link source http://static8.depositphotos.com)

Why is a shopping experience increasingly stressful over time?
As we add items to our cart, the work done per unit time (power) required increases. In the continuous case, this problem closely resembles our 'optimal snow shoveling problem' analyzed during a February snow storm. The accumulated objective function cost there increases as the square of the distance. Here, we look at the discrete situation. When we visit city 'i' to pick up N(i) items each having mass m(i), we instantaneously add mass N(i) * m(i) that we have to lug around until checkout. After picking up k-1 items, my total work done will approximately be:
μg * sum (i = 0,... k-1) W(i) * d(i, i+1), where i = 0, represents the store entrance, m(0) represents the mass of an empty shopping cart, and
W(i) = sum(j = 0, .., i) N(j) * m(j) = total mass carried from city i to i+1.

In other words, the 'cost' accrued while traversing any pair of cities also depends on the items we picked up earlier, i.e., it is no longer memory-less and varies depending on the cities visited earlier.

Result: our shopping gets increasingly more tiring over time

If one of the items in our shopping list involve a heavy item, then our optimal solution may no longer be the shortest time tour.  We now have to solve a minimum-effort TSP. Operations Researchers have also looked at methods for solving a path-dependent TSP in the past. A simple heuristic approach would be to break the trip into two tours. The earliest items stay with us the longest, so we first find the optimal sequence through the light items, followed by the shortest tour through the heavy items. We also have to organize the shopping cart carefully enough to ensure that our light items do not get squished by heavy products, and our ice-cream doesn't melt. I'm sure there are better algorithms than the one provided here.

Recommendation
If we want to burn calories while shopping then a good way to do that, based on our previous discussion is (a) carry our items, (b) pick up the heaviest items first, and (c) take the longest route to maximize energy expenditure (d) walk briskly. This health-and-fitness article provides ten tips for exercising that includes these ideas. For the rest of us who are looking to minimize effort, we simply do the opposite:

We sort our shopping list items in decreasing order of expected weight (frozen stuff goes to the bottom too), while also ensuring that the aisles of adjacent items in the list are close to each other, and we are not revisiting aisles or zig-zagging much.  Some swapping may be required to find improved sequences. Many of us have probably evolved into efficient shoppers over time, and naturally take these steps and more, but if there an opportunity for improvement that the 'science of better' can uncover for us to make our shopping less stressful, let's take it.

Happy Holidays!

Update 1: December 17, 2013
IBM Smarter Retail article says:
"..... Most recently, Lowe’s has offered the customer a product location functionality that is integrated with their wish list. According to Ronnie Damron, .....Whether customers are browsing the store for ideas or searching for a specific item in a hurry, we think the Product Locator feature will simplify the shopping process, creating a better experience that encourages customers to come back again and again.”

Optimizing Shubh Laabh: Harmonious Profitability

Sustainable machine-generated, data-driven decisions
The growing popularity of 'Big Data' coupled with 'machine learning' techniques coincides with an increasing use of automated, machine-computed solutions for a a variety of business problems that were once solved and optimized based (predominantly) on human inputs. Machine-generated solutions have been shown to be superior to these previous methods on the measured performance metrics in many instances, and companies all over the globe have deployed advanced analytics and business optimization models (e.g. built using Operations Research) to achieve incremental profitability, cost reductions, or improved system efficiency. However, all is not well. Some solutions are sustainable, and work well over time, while others begin to run into a seemingly endless stream of human or environmental issues, and fall by the wayside. 

What differentiates sustainable machine-generated optimizations from the unsustainable ones? The answer is not straightforward, and this post explores one aspect. For an example of what kinds of issues can crop up, see this BBC news article: "Amazon workers face increased risk of mental illness", as well as this older article on 'unhappy truckers'. A portion of the BBC article highlighted below is color-coded to show where sustainable decision optimization could be potentially applied to improve upon the status-quo):

 "..... Amazon said the safety of its workers was its "number one priority."

Undercover reporter Adam Littler, 23, got an agency job at Amazon's Swansea warehouse. He took a hidden camera inside for BBC Panorama to record what happened on his shifts.

He was employed as a "picker", collecting orders from 800,000 sq ft of storage.

A handset told him what to collect and put on his trolley. It allotted him a set number of seconds to find each product and counted down. If he made a mistake the scanner beeped.

"We are machines, we are robots, we plug our scanner in, we're holding it, but we might as well be plugging it into ourselves", he said.

"We don't think for ourselves, maybe they don't trust us to think for ourselves as human beings, I don't know.

..... Prof Marmot, one of Britain's leading experts on stress at work, said the working conditions at the warehouse are "all the bad stuff at once".

He said: "The characteristics of this type of job, the evidence shows increased risk of mental illness and physical illness."

"There are always going to be menial jobs, but we can make them better or worse. And it seems to me the demands of efficiency at the cost of individual's health and wellbeing - it's got to be balanced." "

I spent the early-mid 2000s redesigning, and improving airline crew scheduling optimization systems. This period also happened to be the industry's most tumultuous: 9-11, out-of-control fuel and labor costs exacerbated by the invasion of Iraq, repeated strikes by various worker unions followed by contentious negotiations that lead to multiple CBAs (collective bargaining agreements) being ripped up and rewritten, and companies lining up to file for Chapter-11 bankruptcy protection, etc. Endless problems. The office atmosphere got quite intense when the R&D team somehow managed to find itself in the middle of these events, and facing heat from all sides (management, unions, soaring passenger complaints) on the kinds of solutions that were generated by our decision support systems (The US airline industry pioneered the use of such techniques). The analytical lessons empirically learnt from such episodes are hard to replicate in classrooms. One such lesson was "pay a lot of attention to the impact of your model on the people and environment". The application of this lesson has been explored in this space in a variety of contexts earlier: here (Gandhi's methods), here (Smart-Grid), here (Airline Crew scheduling), and here (Conflict resolution). The issue is revisited here by borrowing an idea from traditional Indian business philosophy to see if new insight can be generated toward answering our question on sustainable business optimization.

(pic link source: http://www.indiabazaar.co.uk)

(Updated: November 30, 2013 Finally found the link to article that inspired this post)
It is interesting to note that for centuries, traditional business communities in India had adopted the policy of Shubh Laabh (written in Hindi in the picture), which roughly translates into 'auspicious/harmonious profit' (Aravindan Neelakandan, co-author of 'Breaking India' in the linked article notes: "Lakshmi symbolizes the wealth that is holistic: it is wealth that puts welfare (Shub) before profit (Laabh)." The pursuit of wealth and profitability was never frowned upon in Hindu society, while unconstrained profit maximization was recognized as a socially destabilizing and ecologically unsustainable objective.  'Shubh Laabh' recognizes and respects the presence of long-lasting and latent side-effects that arise from business decisions (that can bring you 'bad luck') and attempts to balance them equitably with the more immediate goal of profitability (Laabh). These traditional businesses employed some operational form of Ahimsa (the principle of minimal harm) to optimize Shubh Laabh:

Rule a) limit harm (hard-constraint version)

Rule b) minimize harm (soft-constraint version)

Let us see how this idea can be incorporated within modern decision optimization systems. Amazon appears to have satisfied all legal requirements via (a) by making safety a top priority. It has probably ensured that the statistical rate of accidents is below some stringent threshold. In the airline world, (a) is achieved by ensuring total compliance with respect to all FAA- and CBA-mandated safety rules. However, this represents a necessary condition that tolerates a certain level of error as 'legally acceptable collateral damage'. The resultant formulation is: maximize profitability subject to safety regulations. However, this in itself is an insufficient specification if we want our algorithms to minimize harmful side-effects. An Ahimsa-based model would additionally consider (b) and eschew profit achieved at the cost of a reduced employee quality-of-work-life (QWL) or environmental degradation, as unsustainable and counterproductive in the long run. 

For large-scale systems such as a retail supply-chain or airline crew schedules, a reasonably skilled analytics professional should be able to incorporate requirements (a)-(b) within their decision support algorithm which, among alternative near-optimal solutions (and there are often many of these), selects one that also maximizes worker QWL, and/or minimizes harm (e.g. reduces carbon footprint). This requires the human-and-environment-variables in the system be treated positively as an active and equal partner based on mutual respect, by explicitly including their requirements as part of the primary goal (objective function), going beyond a legalistic/adversarial approach of treating these variables as a 'loss-making noise that has to be managed' by specifying a minimum tolerance constraint.

To summarize
It is possible to achieve sustainable profitable solutions via automated decision support systems that are also harmonious and sustainable, by paying due respect to all the stakeholders (including Ms. Nature), right from the design phase.

An old blog discussed Rajiv Malhotra's use of 'mutual respect' (as opposed to mere tolerance) as a simple but powerful basis for two heterogeneous groups of people, or people subscribing to conflicting thought systems, to achieve a fair and sustainable equilibrium in their interactions. It appears that such a mutual respect:

a) is implicitly present in the idea of Shubh Laabh, which in turn

b) can be employed as a key guiding principle of 'sustainable design' when building decision support algorithms for managing complex business problems, where multiple, and potentially conflicting, goals have to be delicately balanced.

The opinions expressed in this article are personal.

Optimizing a Kid's Birthday Party

The previous post was about virtual books. This brief post is about children's books, and the nice idea of requesting kids to bring their used books to a birthday party. Suppose there are N kids, with kid(i) bringing book-set B(i). The optimization problem is fairly simple to state. Get the kids to exchange their books in such way that total satisfaction is maximized after the exchange.

A distributed optimization approach could, for example, let kids do their own thing and perform two-opt book swaps until every kid achieves their user-optimal solution, or no candidate is available for swapping.

A centralized optimization scheme may require a parent to create a library of sum(i)|B(i)| books, acquire book-attribute preferences from kids, the attribute vector for each book, and using this information to (informally) solve a partitioning problem that assigns |B(i)| books to kid(i) such that it maximizes the preference sum.

A Karmic optimization approach, which I personally prefer, could let the kids enjoy the cake and ice-cream, while a parent mixes the books up and organizes a fun lottery where the books pick the kids.

Regardless of how the books are assigned, if we do this over a sufficient number of birthday parties, the kids would eventually get to read a variety of books at no extra cost.

Operations Research for the SmartGrid - 2: Optimization Problems

In this sequel to part-1,  an overview of a few, specific optimization models employed within three different Smart-Grid areas is provided. I found these samples to be interesting from a practitioner's perspective. INFORMS publishes a lot of good papers in these areas, and is an excellent source of references.

Managing Electric-Vehicle (EV) Charging within a Smart-Grid
EV System Perspective: 
EV problems are fun. Researchers in Hong Kong have investigated efficient online charging algorithms for EVs without future information, where EV charging is coordinated to minimize total energy cost. EVs arrive at the charging station randomly, with random charging demands that must be fulfilled before their departure time. Suppose that N EVs arrive during a time period T, indexed from 1 to N according to their arrival order.  The optimal charging scheduling problem minimizes a total (convex) generation cost over time T, by determining the best charging rate for EV i at time t, x(i, t), subject to various constraints.

The difficulty of an efficient charging control mainly comes from the uncertainty of each EV’s charging profile. Prior approaches assume that the arrival time and charging demand of an EV is assumed to be known to the charging station prior to its arrival. However, the HK team have come up with an optimal online charging algorithm that schedules EV charging based only on the information of EVs that have already arrived at the charging station. They show that their approach results in less than 14% extra cost more an optimal offline algorithm,   which can be potentially reduced even further.

EV User Perspective

Cool routing algorithms can also be developed from a user-perspective. One interesting work I came across takes a more holistic and rigorous view of the simple Tesla routing problem that I blogged out a while ago. Researchers in Europe look at a routing subproblem within the more general context of managing congestion at EV charging stations and minimizing the impact of EVs on grid performance. They employ an algorithm to compute the best charging points to visit to based on the estimated travel time (shortest-path, and reachability based on available battery power) to all charging points, and the point-specific charging cost. Input: O-D locations, initial battery level, desired charging level for the EV user, and the preferred time of departure. The optimal route, the subset of intermediate charging points, and the slot that the EV is going to charge at, are returned as output.

Demand Response and Pricing
Revenue Management and supply chain analytics folks will be pretty familiar with this area. Smart-devices can be programmed to automatically (with human overrides) respond to price changes by reducing or rescheduling electricity usage. Couple of differences here from standard RM/SCM problems : i) unlike supply chains that process manufactured widgets through warehouses and distribution centers, it is quite difficult to efficiently store and "ship" electricity using batteries, although the technologies are getting better each day. Thus, the electricity we use is probably produced less than a second ago, and marginal costs can spike during peak periods ii) electricity tends to be incredibly inelastic, making it stubbornly resistant to pricing changes, unlike say, smart-phones.

We noticed that prior approaches that apply peak-hour "congestion" pricing tended to 'migrate' rather than mitigate peaks. By carefully combining peak and off-peak pricing with accurate short-term load forecasting, and jointly optimizing the entire price profile, it is possible to proactively flatten the overall predicted load profile by inducing customers to make small shifts in their usage. Even a small peak shift-reduction during high-load days can result in a lot of savings. In fact, our experiment using actual Smart-Grid data showed that even a half a percentage point peak reduction using optimization could potentially lead to more than a 25% reduction in cost, which can benefit both the customers, as well as the utility companies.

Smart-Grid Control
Among the variety of problems solved here, researchers are also looking at the security-constrained optimal power flow that aims to minimize the total cost of system operation while satisfying certain contingency constraints.This smart-grid formulation extends the standard optimal power flow (OPF) problem, which determines a cost-minimal generation schedule cost while satisfying hourly demands, as well as energy and environmental limits, and meeting network security goals. Optimization methods used here include Benders decomposition, as well as Lagrangian multiplier techniques. Some of the newer variations employ distributed algorithms that are designed to work on a massive scale.

These are just a few samples that caught my attention. There are a variety of other problem areas being addressed (e.g. batteries, renewable energy sources, micro-grids), all of which perform some type of an optimization.

Inverse Rule of Project Timelines

Over the last decade and half, I've participated in a variety of internal and external commercial OR projects across multiple industries, many of which involved competitive bids. These projects somehow always ended up being one of two types - either long and routine, or interesting but cruelly short. Every time I came across that exciting project full of nice OR work, the deadlines were killing. The duration of the project/pilot/proof-of-concept appeared to be inversely proportional to the degree-of-sophistication. It seemed quite puzzling at first, but there are some plausible explanations for it, and perhaps this phenomenon shows up in other STEM-area projects too.

If the project isn't novel, and requires some reinventing of the wheel, it's considered low-risk and delegated to the Rodney Dangerfields in the trenches. If it turns out to be something new and shiny, senior pros are brought in to unleash their deadly math modeling dance moves on the client: a bewildering Bangra of reformulations and theorems, culminating in the East Coast Shuffle: the final formulation will always be solvable to optimality as a DP (thanks to a west coast friend for this discovery). A final spin through OR-FX chartware, and the gobsmacked customer is humbled into signing, provided the price is right, and of course, resistance to publication by any journal is futile. Problem is, the senior pro clock is relatively expensive. To keep the bid competitive, the total cost is treated like a knapsack constraint, which makes total time the casualty.

Result? like cricket matches that end in a draw after five days, lets just say that OR is the winner here.

(Written in jest, and any resemblance to real for-profit firms is not just coincidental but highly unlikely given the suboptimality of the inverse rule)

Industrial Applications of Analytics/OR at INFORMS 2013

I will be presenting three practice talks around the theme of 'industrial applications of analytics and OR' at the INFORMS annual conference, 2013. Each of them involve some type of optimization; each one is a different context - energy, fashion retail, e-commerce; each one a different setting (product, service, decision support tool) having varying client objectives and requirements.

3 - The core decision optimization problem turned out to be a discrete nonlinear formulation, and in each case, solved with the help of CPLEX after reformulations and/or decomposition.

2 - of the more challenging decision problems will be analyzed using results on real client data.

1 - of these solutions, apparently, was turned into a commercial product a while ago.

0 - number of theorems proved. Left to the journal paper and smarter co-authors.


Monday 8 - 9:30 am: Real-time personalized deals

New Directions in Pricing and Revenue Management)

Tuesday 8 - 9:30 am: Pre-pack optimization in Fashion Retail
Theory and Practice in Retail

Tuesday 11 - 12:30 pm: Dynamic pricing in a Smart-Grid
Topics in Dynamic Pricing and Mechanism Design

Sine-Generator in the Aryabhatiya, 1500 years ago

Came across this post by Rajiv Malhotra on facebook, and am posting a screenshot.  More research and findings continue to trickle in about the discoveries and creations of ancient Indian mathematicians, and this sloka (verse) is not an isolated example. The focus of this brief post is on the design of the sloka from the data compression optimization aspect.

Brevity and conciseness was important to ancient Indian scientists and linguists for various reasons. Their success in optimally designing such slokas to be memorized by maximizing the density of information carried per unit syllable, while also (and this is important) ensuring that the sloka is logically sequenced and constructed, and relatively easy to memorize, is utterly remarkable. In particular, the affection for the minimal among those Sanskrit grammarians is legendary. There is an oft-repeated saying in ancient India that the joy experienced by a grammarian who manages to achieve a half-a-syllable reduction is only equaled by their joy upon the birth of their child. The choice of the objective function drives the design approach. In contrast with the previous example, we have the Vedic chants in Sanskrit, the world's oldest, unbroken surviving oral tradition, where redundancy was deliberately added to minimize error in oral transmission (an achievement that may have contributed toward India having the world's oldest, unbroken civilization). In this case, what was memorized and repeated was much, much longer than the original verses in order to optimize information and audio fidelity.


(Mysore is a city in Karnataka, India, whose state language is Kannada)

Update (Sept 5, 2013)
The English transcript of the sloka can be found here in the Nature Journal (thanks to Srikrishna ‏for sharing this link).

Update 1: December 15, 2013
A superb post at http://hindufocus.wordpress.com on a compressed Sanskrit verse for remembering the value of Pi to 32 decimal places.
"..... Here is an actual sutra of spiritual content, as well as secular mathematical significance.

gopi bhagya madhuvrata
srngiso dadhi sandhiga
khala jivita khatava
gala hala rasandara

..... The translation is as follows:

O Lord anointed with the yogurt of the milkmaids’ worship (Krishna), O savior of the fallen, O master of Shiva, please protect me."