How many newsvendors?

Last October in India, I was traveling with my father on a day-train from Bangalore to Chennai. About halfway into the journey is a station called Jolarpet, where the train stops for about 10 minutes. As at other stations, there are dozens of vendors – each with a simple wheeled stall, or a wooden basket or a steel container – engaged in a frenzy of small scale entrepreneurship. They hawk all sorts of stuff: snacks, tea, coffee, water, bananas, flowers, and cheap Chinese goods - toys, combs, and, in what became a curiosity among our fellow travelers, pens that double as flashlights. But my father was most interested in those who sold vadas, a South Indian specialty, a round fried snack with a hole in middle – like a donut, but not sweet – made from a batter of rice flour and white lentils (I’ve described just one variety). My father feels the vadas sold by vendors at the Jolarpet station are very good, better than those made in the train’s pantry. They are piping hot, the texture is perfect, and the timing – late afternoon – is just right to munch on them and wash them down with coffee.

Three fairly busy trains – including the Bangalore-Chennai Brindavan Express on which we were traveling that day – arrive at Jolarpet station at about the same time late in the afternoon. That’s boom time for vendors selling vadas. “How many get sold?” my father wondered. “Maybe a thousand of them, maybe even more.”

As soon as he said this, I began in my own nerdy way to think about the newsvendor problem. For those who might not be aware, the newsvendor problem is stylized situation but one that arises in myriad forms and in varied contexts all over the world. Here’s the simplest form of the problem: How many newspapers should a newsvendor decide to produce given that demand for newspapers is uncertain on any day? If she underproduces she loses the opportunity cost; if she overproduces, the cost of producing those extra newspapers is wasted – they can’t be sold the next day as the news will by then be old. If she has some idea of the distribution of the demand, the optimal number of newspapers will be that point on the demand distribution curve that will balance the expected lost opportunity cost and the expected wasted production cost.

In selling vadas too vendors at Jolarpet station must face a similar dilemma: how much should one make? Just as newspapers are useless the next day, vadas need to be sold immediately, since nobody will buy them cold. The timing – more specifically the decision of when to make the batter and fry them –is as important as the decision of how many to produce. The ingredients – cooking oil, rice and lentil flour – aren’t perishable (in other words they can last a long time), but once a vada is made, it is perishable, since a cold vada is unacceptable.

How do these vendors do their planning? I am guessing it’s informal, based on intuition, and sharpened by experience. But I wouldn’t be surprised if the more competitive among them kept records of how much they sell each day, so they can get a sense of the demand distribution, which is, of course, directly related to how full the trains are, which in turn is related to the time of the year. Festival seasons mean packed trains, and more sales; there are probably periods of relative lull as well.

There’s also the aggregate planning component about how much lentils, rice flour and cooking oil to buy. And the operational level decisions: listening to the announcements at the station, and using that information adequately – such as to delay the frying based on whether a train is late.

There’s a certain beauty in this sort of informal decision-making. The vendor at Jolarpet station probably isn’t rich. He most likely does not have access to computers or Excel that might allow him to collect data and analyze it (though I could be wrong about that assumption). But he’s still using some model - however obscure it may be to us - and he’s adapting all the time.

When you look situations this way, it would seem elements of operations research are omniscient. Consider just the newsvendor problem. Imagine how the thousands of restaurants all over the world, small and large, might do their daily planning of perishable products. Think of how manufacturers order their raw materials subject to uncertain customer orders, how hospital emergency rooms might plan their staffing given uncertainty in patient arrivals.

In each of these applications, some sort of planning, however crude, is being used. Which makes me wonder: How many newsvendor-like problems are solved each day?

My algorithms class

One of my favorite classes during my doctoral studies at Arizona State University was Design and Analysis of Algorithms. This was back in the fall of 2002. Goran Konjevod was the instructor.

Goran had a penchant for stimulating thought and that showed in the sort of questions he chose from textbooks for his assignments and exams. Here’s one I remember enjoying very much. I like it particularly because of its dark, authoritarian overtones – it brings out the Stalin in you. Not the mass-murdering Stalin but a clinical and efficient one. I am joking, of course, but you'll see what I mean when you read this:

An evil king has a cellar containing n bottles of expensive wine, and his guards have just caught a spy trying to poison king’s wine. Fortunately, the guards caught the spy after he succeeded in poisoning only one bottle. Unfortunately, they don’t know which one. To make matters worse, the poison the spy used was very deadly; just one drop diluted even a billion to one will still kill someone. Even so, the poison works slowly; it take a full month for the person to die. Design a scheme that allows the evil king to determine exactly which one of his wine bottles was poisoned in just one month’s time while expending at most O (log n) of his taste testers.

And no, the answer is not that we need a human rights commission to investigate this, though that might be a tempting lateral-thinking answer! Don’t ask me for the solution to the question either; I’ve long forgotten it!

What I do want to state is that I was quite inspired by the class. I was doing a PhD in Industrial engineering, but the class taught me the computer science way of looking at problems, and illustrated how intelligent one could be in designing algorithms. Without a doubt, the class was why I eventually went to write a dissertation on algorithmic complexity of certain scheduling problems. Thanks very much, Goran. All the troubles – the poor grades, the hobble to the final exam dodging a nail* – were certainly worth it!

A lot of Goran's papers, many of them OR papers on approximation algorithms and polyhedral theory, are available on his site. He also has an origami gallery.

* I overslept on the morning of the final exam. The exam was scheduled for 7:40 am, but I woke at 7:45 am. When I saw the clock, I screamed; my roommate woke with a start. As luck would have it, I’d left my bike at school the previous night. I had no time to brush. I had no time to wear my shoes either; so I chose an old pair of sandals, one of which incidentally had an iron nail inextricably lodged in it. I hobbled a mile to the exam, making sure I did not step on the portion of the sandal that had the nail. I was in my nightclothes, but mercifully at the time, my nightclothes didn’t differ much from what I wore during the day. I got to the exam at about 8:05 am, and did what I could in the time I had. It shall suffice to say that I somehow scraped through.

Delivering malaria bed-nets

The picture below is from allafrica.com and is of a doctor in Mali showing visitors where bed nets are stored.

One of the pressing problems facing African aid organizations is the delivery of malaria bed nets. This distribution and logistics problem isn’t just about crunching numbers; there’s a lot of thoughtful fieldwork and intelligent strategies that go into it. I feel a lot of operations research problems are like that: they might have algorithmic and mathematical components to them but what gets the job done is a large scale coordinated effort by people using information and resources intelligently.

Consider this article by Steven Phillips (ExxonMobil's Medical Director for Global Issues and Projects), which discusses the entire supply chain of bed nets, beginning with their production in Vietnam to their delivery in Mali to countryside clinics and subsequently to pregnant women and young kids (the biggest malaria risk group). At the end of the article, Phillips emphasizes the disconnect between the world of numbers and the realities on the ground:

The source of my wonder was the disconnect between the bold overtures of some global campaigners and the gritty reality on the ground. Some think malaria requires a good calculator and money. Figure out the aggregate need, fund it, and procure the requisite commodities. This both discounts the complexity of the delivery of goods to the end beneficiary and undervalues the overwhelming diligence, creativity and dedication of the on-the-ground implementers.

And the following excerpt indicates the scale of the logistical effort:

The distribution plan called for 40 health districts to receive shipments in six regions of the country over a radius of 600 km from Bamako [in Mali]. A single transport company won the tender and used 60 runs by 40 trucks to deliver bales of uncrated nets. Transport was about 50 percent on "tire roads" which are paved, and 50 percent on unpaved dirt roads. It required ten days to accomplish this phase. Many of the roads would have been impassable in the rainy season. The paradox was striking – the nets could only be delivered reliably during the dry season, when malaria risk is the lowest.

From the 40 district locations nets were subdivided for shipment to 975 health centers. It took one to 10 days to accomplish this. While awaiting trans-shipment, the bales of nets were often subject to "outdoor warehousing" with a hired security guard sitting on top of the bales to prevent theft.

From the health centers, the nets were sent to 2,000-3,000 distribution points with a radius of 5-20 km. This was accomplished via a variety of transportation modes including bicycle, donkey-cart, camel and "push-push", a local cart-like conveyance pushed by human power.

For mothers who could not make it to the final distribution points, mobile teams on bicycles and motorcycles would deliver the nets to their villages and dwellings. In the end, all of Mali's 15,000 villages are covered.

___

The New York University economist William Easterly also discusses the complexity of delivering bed nets his book The White Man’s Burden: Why the West’s Efforts to Aid the Rest Have Done So Much Ill and So Little Good. Like Steven Phillips above, Easter argues that if the problem of delivering bed nets were so easy and required only money and some aggregate planning, then why don’t the poor have access to bed nets already? Why are they diverted to the black market, why do they become out of stock in health clinics, or why do they end being used as fishing nets or wedding veils?

Easterly then goes on to mention the excellent work done by Population Services International (PSI) on the bed net delivery problem in Malawi in southern Africa. (Incidentally, PSI is also involved in the effort in Mali I’ve excerpted in the first part of this post.) What was the PSI strategy exactly in Malawi that led to so much success? Easterly elaborates:

PSI sells bed nets for fifty cents to mothers through antenatal clinics in the countryside, which means it gets the nets to those who both value and need them. (Pregnant women and children under five are the principal risk group for malaria.) The nurse who distributes the nets gets nine cents to keep for herself, so the nets are always in stock. PSI also sells nets to richer urban Malawians through private-sector channels for five dollars a net. The profits from this are used to pay for the subsidized nets sold at clinics, so the program pays for itself. PSI’s bed net program increased the nationwide average of children under five sleeping under nets from 8 percent in 2000 to 55 percent in 2004, with a similar increase for pregnant women. A follow-up survey found nearly universal use of the nets by those who paid for them.

The Malawian workers of PSI, who had worked with the organization for a while, came up with the ideas of supplying nurses in antenatal clinics and the two-channel sales. The incentive based approach appears to work much better than the free delivery of nets. Easterly quite rightly cautions that the scheme "is not a magical panacea to make aid work under all circumstances; it is just one creative response to a particular problem."

My point here is that operations research is often not about fancy algorithms and mathematical models, but clear, common sense thinking tailored to a situation. Richard Larson of MIT mentioned the same thing during a talk he gave to participants of the INFORMS doctoral colloquium in Pittsburgh 2006. His main theme – something I find very relevant and part of the long-running debate between OR theory vs practice – was: How do we disentangle operations research from mathematics of the pointless and pretentious kind, and get back to what operations researchers do best: to find creative, applicable solutions? It’s a question that needs to be asked.

My adventures during a queuing study

In Spring 2003, I took a class on Queuing Theory as part of my PhD coursework at Arizona State University. One of the assignments towards the end of the term was to apply the queuing models we’d learned to a real situation. Expectedly, students headed to the nearest fast food chains, banks, traffic signals and congested elevators to diligently conduct their studies. A not-so-small number headed to their friends to just as diligently pilfer projects from prior years and repackage them as their own work.

I headed to the nearest Safeway grocery store. Why? Because I’ve been fascinated with American grocery stores from the time I first stepped into one. There is something in the size of these stores, the bright lighting, the glittering array of produce and processed food along aisles – vegetables that have so much sparkle as to seem unreal (strangely they do not taste as good as they look); monstrous bags of potato chips; boxes with muffins, their tops bursting with nuts and chocolate; an entire aisle for ice creams only – there is something in this abundance that leaves me agape. Such a cornucopia would have doubtless entered the dreams of Early Man resting in his cave next to his precious hunting tools; and doubtless, waking up the next day, he might have resolved to change the world around him to achieve that dream.

But to return to the particulars of my queuing project. The Friday before Easter, I sat outside the entrance of the Safeway store, next to the vending machine and bike stand, with a stopwatch, pen and piece of paper. I felt later that I might have been thought of as homeless, but this didn’t cross my mind then. I was too absorbed recording the arrival time of every customer into the store from 5 to 7 pm (A group such as a family or that arrived in the same car, I considered as a single customer.) I wanted to see whether the great claim made by mathematicians and queuing theorists about arrivals was true: the claim that the rate of arrivals, if they are sufficiently random and independent (as they are expected to be at a grocery store), follows a Poisson distribution; or conversely, the distribution of inter-arrival times is exponential.

The plot of inter-arrival times did indeed look exponential. On average a customer arrived at the store every 15 seconds; the standard deviation was 16.25 seconds, quite high, but not unexpected given the distribution. The data cleared goodness of fit tests with flying colors. I was excited! A fundamental assumption in many queuing models, of course, is that inter-arrival times are exponentially distributed, and here I had empirical confirmation of this from data I had painstakingly collected.

But arrival data was only the first part of my project. I planned to explore whether there were enough cashiers in the store to sustain this arrival rate, and if queues were reasonable. Since I now had to collect data in the store, I approached the manager, Scott.

I had seen Scott on my weekly shopping visits. He was a tall man, with blonde hair and an erect and dignified bearing. He was usually dressed formally in a white shirt and striped tie. He looked grim - I'd never seen him smile - but was always attentive to his customers' needs. “Hi,” he often said sagely to them. “Are you finding everything you need? Can I help you with anything?”

___

I explained my project to Scott, and told him it could be useful to the store. He looked at me skeptically. A frown creased his forehead.

“You can’t ask customers any questions. That’s just not permitted.”

“Oh, no, it’s nothing like that. I won’t be asking anything, just recording data on how many come in to the store, at what time,” – I’d already done that with arrivals but I didn’t mention it – “and doing a queuing study that may yield benefits to the store. Maybe I’ll learn something that Safeway can implement.”

It wasn’t the strongest pitch. Scott was still unconvinced and the frown remained. But he agreed. So I began doing rounds at the store, trying to remain inconspicuous, getting a sense of what people did, the amount of time they spent in queues, and the time checkout cashiers took to service them.

I was intrigued particularly by the rack or shelf that extended in front of each of the checkout counters. They consisted of the latest magazines, chocolates and candy with colorful wrappings, and such odds and ends as batteries. Customers would choose a magazine and toss it into their cart as they waited, their curiosity no doubt piqued by George Clooney's most recent affair or the most recent adoption from Cambodia, Kazakhstan or Malawi by a high profile actress - all this brazenly announced in The National Enquirer or People. Kids, on the other hand, would insist on having candy. Since a significant number purchased something from the rack – it was a reflex for some – I wondered if queues were really so bad after all. Sure, queues shouldn’t be too long for that can be frustrating, but maybe it actually helps the store to lengthen queues just a wee bit and provide an extra magazine or candy rack.

I considered this in my project, though with the deadline approaching I could only scratch the surface. The details are too specific to mention here, but I proposed a modified single server queuing model where queues are profitable, so long as they are not longer than the length of the rack (usually 4-5 people). I don’t think I did enough for the model to give any insights as far as Safeway was concerned, but I sure was excited with this seemingly perverse idea of increasing queue sizes.

The other analysis I did was standard, garden-variety stuff: Were there too few or too many cashiers? The answer was not simple. The store had a floating set of employees who would do other jobs in the store but when queues started building they would be called using the announcement system to open a new checkout counter. Thus lines never got out of control, and employees could be used flexibly to do other odd jobs at the store during periods of lull. I figured my queuing models with their set of assumptions weren't really applicable. After all, what could I suggest about staffing from my short visits that Safeway employees and the ever grave Scott hadn’t already figured from years of experience? There do exist other situations where a fresh perspective can help spot obvious flaws or suggest improvements, but this didn’t seem like one. Besides, people working in settings such as Safeway have rudimentary but intuitive ideas they develop themselves, and which they adapt with the passage of time and with experience; they don’t need degrees in operations research to develop this intuition. This is actually one of the key messages I intend to convey through Out of Kilter.

____

Finally, to finish this rather long post, here's how my project related visits to Safeway came to an abrupt end. I was trying to collect cashier service times – I’d already collected enough to build a distribution but wanted some more. My modus operandi was to choose a cashier, retreat to the rear of the corresponding aisle and observe from there. I couldn’t retreat too far since I wouldn’t have a clear view and I couldn’t be too close either for fear of attracting attention. Whatever my little tricks, there must have been an inadvertent surreptitiousness to my actions, for my eyes met once with a curly haired cashier’s and lingered for a while. He picked up the phone; I thought it was to address some customer issue. But a minute later, I heard a familiar voice behind me.

“Hi,” the voice said sagely. “How are you doing?”

Scott was dressed as usual: plain white shirt and striped tie. He wasn’t happy. “You’re making people nervous,” he said.

“But I informed you already that I would be collecting data in the store – I was trying to do it covertly so as not to disturb!”

“Yes, but you have to tell me when you intend to come in so I can warn my employees and so they don’t get edgy about some stranger spying on them, stopwatch in hand.”

I saw his point. Scott was just being a good manager. I agreed to inform him in the future, but I never returned – mostly because I had enough data for my project, but also because I was worried about becoming notorious as an undercover data collector. What if harassed employees were to put up an enlarged mug of mine at various locations with the stopwatch cord serving as a noose and a big red “BEWARE OF THIS MAN!” stamped diagonally across? Even worse, what if I were to be booted out of the store? How then would I buy the enticements along the aisles - bags of Lays, delectable Entenmann's pastries, desserts of Pepperidge Farms, things I had come to depend so much on?

So, you'll understand why I receded wisely, wrote up my project report, got a good grade, and continued to be an anonymous customer - one of the 'Poisson-arriving' masses!

Relationships that maximize HIV transmissions

A couple of months ago, I came across this review of Helen Epstein's book, The Invisible Cure: Africa, the West, and the Fight Against AIDS. The reviewer William Easterly, a well known development economist at New York University, points to an important insight in Epstein's book on why HIV transmission rates are so high in Africa.

The conventional view was that promiscuity contributed to the rapid spread of AIDS in the continent. The World Health Organization and The World Bank suggested in their 1997 report that the infections were because of “core transmitters such as prostitutes and the truck drivers and migrant workers who patronized them”. These views understandably produced a defensive reaction, and explain “the astonishing wall of silence surrounding AIDS that Epstein documents and that still prevails among both the African public and politicians.”

But were promiscuity and the sex trade really the main reasons why so many were infected? Epstein posits a more nuanced theory based on the studies of independent researchers. Its premise is that transmission rates are high because of the prevalence of concurrent long-term relationships in Africa. (In the West too, people tend to have multiple long term partners over the course of a lifetime but these relationships are typically not concurrent.)

In African countries the situation is exacerbated by the fact that both men and women tend to have more than one long term partner at the same time. This differs significantly from other places where women’s monogamy is strictly enforced, often due to religious conservatism. It is tragic and a strange irony that greater sexual freedom for women should aggravate the AIDS problem.

Concurrent relationships in certain regions of Africa are a product of work lifestyles. Men work long durations away from home, hence opening up opportunities for both men and women to have partners on the side:

In southern Africa (where the epidemic is concentrated), one of the few opportunities for gainful work open to men is to become long-distance migrants to the mines. Both husbands and wives may have other long-term partners during the months when they are separated. The African tradition of polygamy (described by historians like John Iliffe as a cultural response to maximize fertility in what used to be a lightly settled continent) has given way to modern relationships between older, well-to-do, gift-bestowing men and multiple young girlfriends. This is not so different from the successive trophy wives of American fat cats, but much more widespread since Africa's poverty often makes it a matter of survival for African young women to have a rich (older) boyfriend. The desire of young women for young boyfriends can be accommodated on the side.

And here’s the crux of the problem - why concurrent relationships are more likely to transmit the virus than one-night stands or serial monogamy:

For many reasons, concurrent, long-term sexual relationships are much more dangerous for the spread of AIDS than serial monogamy. When both men and women have concurrent relationships, they are part of a huge web of sexual partners by which the HIV virus moves through the population. Long-term relationships are much more likely to spread AIDS than one-night stands because of the low probability of a single sex act spreading the virus. Since the HIV-positive are most contagious soon after they themselves become infected, a long-term partner who has just become infected in another relationship poses much more risk than a prostitute who has been infected for a long time. Serial monogamy in the West kept the virus largely trapped within single relationships, a fact Epstein nicely illustrates with some clever graphs. Her explanation based on concurrent relationships has gained broad acceptance and has been confirmed by mathematical modeling and by surveys of sexual habits in various countries; but one still wishes the evidence was a little more extensive for such a critical issue.

From the operations research perspective, there is an intriguing question here: What types of relationships/sexual mores are more likely to cause a greater number of infections in a population? If a comparative simulation modeling exercise were to be done in isolation to analyze this, we might get some insights, though the model will likely ignore such complexities as cultural factors and the prevalence of AIDS education. From the excerpt above, it's clear that mathematical modeling has already been attempted. I’ll have to look the references in the book up to see what's been proposed so far.

Welcome to Out of Kilter

Let's start with a brief introduction. My name is Hari Jagannathan Balasubramanian (we'll return to the length of the name) and I am a post-doctoral research associate at the Mayo Clinic in Rochester Minnesota. I joined Mayo in September 2006, after finishing my doctoral degree in Industrial Engineering from Arizona State University. I work now on various research and education initiatives pertaining to operations research in healthcare delivery. Some of my past and current work also deals with scheduling theory and algorithms. This often puzzles some of my colleagues and friends since they are quite aware that I do little to schedule or plan my own tasks.

Out of Kilter will consist of notes and some personal perspectives on operations research (OR), interpreted broadly and applied to just about anything. As a quick preview, I plan to do a post on a difficult land allocation problem that arose in 1947 as a result of the traumatic partitioning of the Indian subcontinent; the nature of sexual relationships in southern Africa and their role in maximizing HIV transmissions; something as trivial (and hopefully fun) as how I pack my laundry into the washer because of a thumb-rule I learned while studying an OR problem; how auto-rickshaw drivers in the increasingly congested city of Bangalore might be thinking of maximizing their revenues; and something as contemporary and vogue (in the OR community at least) as using models for improving access to primary care and disease modeling. My intention is not to be very technical; rather I’ll try to illustrate, whenever possible, aspects involving people and their decision-making.

Why, you might ask, the name Out of Kilter? No particular reason, except that it lends a touch of drama. Some of you may know that out-of-kilter refers to an algorithm developed by Ford and Fulkerson for certain fundamental network flow problems (see this article for an introduction). But let us not delve too much further, because if we do my ignorance – or rather my lack of recollection of networks and graph theory – will be swiftly revealed.

I also maintain another blog with a title just as strange - Thirty letters in my name. I write about history, travel, and literature in that blog - all topics I am very, very passionate about. Hopefully aspects from there will influence what goes on here and vice-versa, even though the two blogs might at first glance seem incompatible.

Shall we begin, then?