OR in Restaurants

The topic for this month's INFORMS blog challenge is "OR and Food". I suspect that a number of my fellow bloggers will jump on the diet problem example, also known as the Stigler diet. That also happens to be the name of Tim Hopper's blog, so I'm inclined to leave it to him. Also, while LP diet models may be suitable for selecting animal feed, I think the Geneva Conventions prohibit their use on humans.

My expanding circumference and history at restaurants (*, **) makes it reasonable for me to write, instead, about applications of OR to food service. There are, in fact, a surprising (at least to me) number and variety of these.

• Here at Michigan State University we have The School of Hospitality Business (SHB), the second-ranked hospitality business school in the country (behind Cornell's). Years ago, one of my colleagues from SHB, Dr. Michael Kasavana, told me that restaurant chains (and perhaps individual restaurants) use linear programming as part of menu engineering.  (***) That's Mike getting credit in the first footnote of the Wikipedia entry, putting him one up on me in the Internet fame competition.  See, for instance, "How Do Restaurants Use Linear Programming for Menu Planning?" for a (very) non-technical introduction. Unfortunately, I couldn't find a more suitable link for an OR-savvy audience.
• Researching this entry, I tripped over a few papers using Data Envelopment Analysis to determine whether restaurants in general, and specifically their use of IT in at least one case, are operating "efficiently".
• I found a doctoral dissertation entitled "Managing Restaurant Tables Using Constraint Programming", whose connection to OR should be self-explanatory. The problem encompasses the assignment of tables to diners, both via reservations and walk-in traffic, the possible combination of tables for larger parties, negotiation of reservation start times, and possible on-the-fly reallocation of tables.
• Linear programming has been applied to staffing problems, including the staffing of restaurants (where service personnel, including cooks, are assigned to shifts).
• The "Caterer Problem" is a classic LP/IP application, in which a hypothetical caterer using linen napkins has to plan how to cover demand at minimum cost by acquiring new napkins and laundering soiled napkins (typically via either of two methods with differing lead times and costs). I don't know how often LP models are actually used by caterers or restaurants, but "it's the thought that counts".
• It is well-known that simulation is used to help design both facilities and production systems. Simulation modeling at Burger King was documented in an Interfaces article, and they apparently went so far as to distribute a simulation model to restaurant operators as part of a "Productivity for Planning for Profit Kit". Although I can't find the articles documenting it, BK famously redesigned their restaurants (quite a while back) using a simulation model.  At that time I was a fairly regular BK customer.  Originally, when I walked up to the counter inside, there would be multiple production lines oriented orthogonal to the counter, so that beef patties started at the back of the store and, in the process of moving toward me, magically transformed into ready-to-eat hamburgers.  One day I entered a BK and discovered that there was now a single, U-shaped production line, with the long sides parallel to the counter. A patty started at one end of the line and morphed into a burger by the time it reached the other end of the line. Apparently this redesign was the result of a simulation study.

So OR has its fingerprints all over the food service industry ... and is therefore to blame for the steepest ascent trajectory of my waistline. (This being an election year, I will join the candidates in abdicating all personal responsibility.)

(*) True story #1: In graduate school, friends would invite me to dine with them at a local all-you-can-eat buffet restaurant just to watch the carnage. 

(**) True story #2: A local sub shop once experimented with pizza sales. Someone posted a handwritten sign on the wall: "Pizza by the slice, Sunday noon to 4:00, all you can eat".  So I stopped by on Sunday. The following week, the sign was amended: "Pizza by the slice, Sunday noon to 4:00, all you can eat except Paul".

(***) True story #3: Early in my career, I was teaching linear programming to MBA students.  This being before the advent of free or affordable optimization software, I was in fact teaching them the simplex algorithm, by hand.  (I have since realized the error of my ways.)  At the end of one term, a young lady in the class came up to me, identified herself as a hospitality business major, and proceeded to "chew me a new one", pointing out to me in graphic detail just how useless all this simplex stuff was for her, particularly given her concentration.  I later learned that, the very next term, she had a course in her major from the aforementioned Prof. Kasavana ... in which she had to solve linear programs ... by hand.  The universe does, in fact, have a sense of humor.

Resolutions, Seasonality and Transient Effects

Today is New Year's Day (at least on the Gregorian calendar), and it is traditional for some people to usher in the new year by making personal resolutions. The theme for this month's INFORMS blog challenge is "O.R. and Resolutions", and to an O.R. person "resolutions" frequently implies "transient responses".  We make a resolution, attempt to adhere to it for a while (introducing a transient change in our behavior), then eventually revert to what we were doing pre-resolution (return to steady state).

I work out at a local YMCA. The Y does its programs in seven week sessions for the most part, with one- or two-week gaps sprinkled around near holidays. I'm not privy to enrollment data, but through decades of empirical study I and other members have identified a distinct seasonal pattern. Building use spikes at the start of the first session of the year (which will be tomorrow). Regulars who come in the evening will discover that parking spots are suddenly quite scarce. The spike is visible but considerably smaller in the mornings. Morning attendance skews toward retirees and the odd academic (pardon the redundancy). I suspect that retirees are less inclined to make resolutions, or alternatively more inclined to stick with them. Academics probably simply forget to make resolutions (just as we forget about matching socks, etc. -- we're too occupied with "profound" thoughts).

After the initial spike in attendance, there is a bit of gradual erosion, as "resolvers" discover that exercise is in fact a euphemism for physical exertion.  There's an abrupt drop (think step function) right around the end of the first seven-week session, and then a bit more erosion as attendance returns to a new steady state, barely distinguishable from the pre-New Year's steady state. Other seasonal patterns occur later in the year: a drop in building use during the summer, when outdoor activities and vacation trips lure people away; and a modest increase (noted only in the evening) between mid-April and perhaps mid-May (which I think of as "preparation for bikini season", and which does not seem to involve any retirees).

Besides offering an example of seasonality, the New Year's resolution phenomenon offers a metaphor for O. R. practice. The "resolver" diets, exercises, stops smoking or whatever for a while because the "boss" (their conscience) is paying attention.  When the "boss" stops watching, the "resolver" makes excuses for why the new regime is too difficult, and reverts to previous behavior.  An O. R. solution to a business problem that is implemented top-down, without genuine commitment by the people who actually have to apply the solution (and change behaviors in doing so), is likely to end up a transient response leading to a return to the previous steady state.

Addendum: Thanks to Mary Leszczynski for pointing out an article in Atlantic Monthly titled "This Is Why You Don't Go to the Gym". The article suggests that penalizing yourself for skipped workouts is a way to motivate follow-through on that New Year's resolution to get in shape. I've occasionally given some thought to why I'm as regular with my workouts as I am. One factor, which fits with the article, is that a little voice in the back of my head reminds me that I've already paid for the workout. (I'm a bit of a cheapskate, so that little voice gets heard.) Another factor is that I mainly do group workouts (aerobics, Tae Kwon Do), with occasional solo forays to the weight room or stationary bicycle. Group workouts can be more fun, but they also mean that slacking will be noticed by someone other than yourself. At my age, though, the principal motivator is fear of the alternative (what my body will turn into if I don't work out).

OR, the Environment, and the Law of Unintended Consequences

The topic of the INFORMS blog challenge for September is "OR and the Environment", and I'm slipping this in just under the wire.  My guess is that most if not all of the other challenge entries will extol some way in which the use of OR helps the environment.  I shall be (slightly) contrarian here.

*****

Problem: Reduce the cost of shipping raw materials and manufactured goods by sea.

Solution: Companies use OR techniques to pack vessels more efficiently (reducing the number of loads), route vessels more efficiently (reducing transit times and, hopefully, total travel distances), etc.

Short-term Environmental Impact: Fewer ships covering less distance means less consumption of fossil fuels, so less air (and water) pollution.

Long-term Environmental Impact: Lower shipping costs make it more cost effective for manufacturers in Europe and the US to purchase materials and components from distant countries such as India and China, shifting the manufacturing operations from regions with relatively stringent environmental reg (medium environmental regulation) ulations to regions with more lax regulations. The increased volume being shipped by ocean more than offsets the reduction in distance per shipment and results in an increase in ocean traffic.

*****

Problem: Make alternative fuel sources for automobiles more cost-effective.

Solution: Employ OR techniques to improve the manufacture and distribution of gasohol (gasoline/alcohol mixtures), reducing the pump price and therefore expanding the consumption of gasohol.

Short-term Environmental Impact: Some of the demand for a non-renewable source (fossil fuels) with a relatively high pollutant output is shifted to a renewable source (crops such as corn) with a lower pollutant content.

Long-term Environmental Impact: Crops previously grown as animal feed or for human consumption are diverted to the more profitable biofuel production, causing shortages or price increases in food. In some countries, this causes farmers to clear forest areas for replanting with food crops. Forests capture carbon more efficiently than food crops do, and clearing a forest by burning it releases significant amounts of carbon. (There are also arguments in both directions as to whether biofuels actually produce a net gain in energy or reduce net pollution when the activities involved in growing the crops are factored in.)

*****

Does this mean that I think OR is bad for the environment?  Not at all; but it's not automatically good for the environment either.  What OR brings to the table that might be most important, in the context of environmental impact, is a systems perspective.  Hopefully OR practitioners can help decision-makers view problems in sufficient breadth, and yet with sufficient (model-aided?) clarity, to recognize the secondary and tertiary effects of their choices. That still leaves the issue of getting environmental impact on the table as a criterion for evaluating choices -- which is a political, not mathematical problem.

USENET: A Remembrance

Although I've already submitted a post to the July INFORMS blog challenge ("O.R. and Social Networking"), I cannot let the topic go by without a (an?) homage to sci.op-research. It is probably premature (albeit barely) to write an epitaph for USENET: in fact, its traffic apparently continues to grow, and where once you needed access to a USENET server, now much of it is accessible via Google Groups.

(image source: Wikipedia)

I suspect, though, that the traffic growth is more a tribute to our insatiable appetite for naughty pictures, bootleg videos and software, and passionate debates about atonal musicians than a testimonial to continued use of USENET as a social network for professionals.

I'm sure a lot of younger people think "social networks" started with MySpace and Facebook. For those of use who predate the Internet (yes, kids, a few of us remain), social networks were once both virtual and analog (cf. "Old Boy Network"). After the introduction of the Internet, but before the advent of the World Wide Web (second note to the kiddies: yes, the two are distinct, and came into being several years apart), we began to enjoy a new way of connecting with people outside our sphere of physical contact: bulletin boards systems (BBSes). These tended to be text only and slightly cumbersome, but they were for many of us the first medium for broadcast communication, where your message is not directed at a specific individual, unlike letters, telephone calls etc. (For me they were the second such medium; I was an amateur radio operator briefly in my teens.)

Then came the mother of all BBSes, USENET.  I think it caught on first with system operators, programmers and other "computer geeks", then with a smattering of other technical types. (Bear in mind that, in the early days of the Internet, access was somewhat limited, largely to universities and the military here in the U.S.)  Then came the flood of, um, less technical stuff (alt.animals.otters? alt.amazon-women.admirers??).  Circa 1993, Mohan Sodhi came up with the idea for a USENET group for operations researchers, and sci.op-research was born.

For a while, at least, sci.op-research was a way for individuals in the O.R. community to ask and answer questions, and for the occasional non-O.R. person to get help.  By 2009, Mike Trick was ready to pronounce it, and the rest of USENET, irrelevant. Today, sadly, it has little non-spam activity. (Mike gets the self-fulfilling prophecy award for creating OR-Exchange, which likely is the nail in sci.op-research's coffin.) Someone with a quick O.R. question or thought today may think Twitter first; for a longer question, they likely will look to a web forum (such as OR-Exchange). Google+ may yet become another viable alternative for communications with and among O.R. people.

Still, in its heyday sci.op-research (and at least portions of USENET) served a useful purpose ... and not just to let O.R. professionals network with each other. One time I answered a question from a practitioner (MS in some engineering discipline, no formal O.R. training that I recall) that led to an exchange of emails as we pinned down the answer to his question.  A year later he contacted me again, offering co-authorship in a paper (which landed in a respectable journal). To this day I've never met my co-author. Neither the collaboration nor the paper would have happened without USENET.

Social Networks at Work

The theme for the INFORMS Blog Challenge for July is "O.R. and Social Networking". I suspect that most posts will deal either with how O.R. tools can be applied to social networks (algorithms that recommend new "friends", managing network traffic, ...) or how social networks can benefit O.R. people. I hope to take a slightly different tack here. Operations research, management science and analytics propose to help people make better decisions and help systems operate more smoothly, and I think we have something to offer in better understanding and managing the role of social networks in the workplace.

Let me start by disclaiming any originality of the following ideas. Researchers in organizational behavior have already taken note of social networks in and between organizations. The central notion is that individual workers and groups of workers gain productivity by leveraging contacts in other units of the same organization or in other, separate organizations. Often those are direct contacts, but sometimes not. (To be concrete, if we picture a social network as a graph with actors or groups of actors as nodes and relationships as edges, direct contacts are nodes adjacent to a given node. Indirect contacts are nodes connected to a given node by a path of length greater than one.) There are various reasons why an organization might be concerned about social networks within it and between it and other organizations:

• If workers become more productive by exploiting links, the organization might benefit from fostering the development of such links.
• A social network within an organization may improve intra-organizational communication.
• Conversely, a social network within an organization might contribute to the development of cliques and cause a rise in "political" behaviors.
• Contacts with members of allied organizations might improve the relationship between the organizations (for instance, helping coordinate a supply chain).
• Contacts with members of competing organizations might foster cooperation on some issues, but also might lead to leakage of proprietary information.
• Individuals with many valuable connections (nodes with high degree, either weighted or unweighted) may be of particular value to the organization, warranting extra effort to retain and reward them.
• Unmanaged development of social networks, both within the organization and leading to the outside, might result in the workforce being divided into "ins" (highly connected individuals) and "outs" (nodes with low degree). To the extent that the social network improves performance, the "outs" may be at a disadvantage in career development. This can undermine mentoring and retention efforts, and may be a particular concern for minorities and non-domestic workers.

To manage social networks, organizations need to be able to quantify them. This means:

• defining what constitutes a network;
• mapping the network;
• finding a way to quantify things such as influence level and value to productivity (which may not be symmetric, meaning the network is directional);
• identifying options for creating or manipulating networks (decision variables);
• estimating the cost and potential impact of each option;
• assessing risks of various options (including allowing networks to grow unmanaged); and
• finding an optimal program of network construction/management.

(Being an optimization guy, I had to squeeze that last item in.) The measurement aspects, including mining existing data (emails, phone records, reports) to help identify existing networks, sound like analytics; the mapping, analysis of costs and impacts, and prescriptive recommendations sound like operations research. So I think we have something to contribute here.

And the great thing about being a blog author is that I'm not required to come up with any solutions (or even brilliant insights). :-)

Hitting the Muggles from All Sides

The theme of the June INFORMS Blog Challenge is "O.R. for Muggles". I mention that at the outset because I do not want to be accused of using the word "Muggles" to drive search engine traffic to my blog. (For that I use references to naughty videos featuring Dumbledore.) The rationale for the theme is articulated as follows:

[T]hese conversations tend to reach an already involved audience. We’d love to spread the word about OR/MS and analytics to a wider audience.

 So we shall assume here that "Muggles" are people who are not part of the O.R. community (and not students likely to join the O.R. community).

If our goal is to spread the word about the value of O.R. and analytics, and particularly if the ultimate aim is to generate work for O.R. experts and to raise its prestige (and priority) in academic institutions, we might want to adopt a three-pronged strategy.

Top Down

This approach targets C-level executives (or at least executives as high in the corporate food chain as we can reach) along with their governmental counterparts. The key is to convince them that they can achieve competitive advantage using O.R. and analytical modeling (or that they will suffer a competitive disadvantage if they fail to do so). Hopefully they will then give marching orders to subordinates to seek out opportunities to exploit this wonderful new (?) type of magic.

Business honchos are famous both for being very busy and for having short attention spans. Discussing mathematical or statistical details would be the kiss of death here. What might work would be to present them with short, non-technical but compelling stories of organizations that have benefited significantly from O.R. or analytics. Benefiting from O.R. models hard-coded into "canned" software is not what I have in mind; the stories need to involve customer-specific analysis by human (or plausibly human) experts.

I'm pretty sure consultants have been doing this for years, and I think INFORMS is doing a decent job as well. Publicizing the Edelman awards is a step in the right direction, although my impression is that the Edelman videos are way too long to engage a C-level executive. We should probably be doing more along this line, though, perhaps including more focus on non-profits and government organizations. How you get to these people is a question above my rather modest pay grade. Articles in key publications (Forbes? Business Week? Harvard Business Review?) may be part of the answer. Guest speakers at business round tables may be another component.

Bottom Up

Here we try to plant seeds in the minds of students about to enter the working world. I don't mean students majoring in O.R., industrial engineering, management science and augury (oops, make that "analytics"). We need to target generic business students (especially MBA candidates) and try to convince them that there is an arsenal of really useful tools that may avail them down the road (provided they acquire artisans capable of using those tools).

I'm inclined to grade our performance here as at best a C. When I began my academic career (about the same time transistors -- not integrated circuits -- were pushing vacuum tubes out of the computing business), it was fairly common for both undergraduate and graduate business curricula to include mandatory "quantitative methods" courses. Unfortunately, we tended to shoot ourselves in the foot (repeatedly) by putting way too much emphasis on theory and hand computation, too little emphasis on the business consequences of the solutions to the models ("you will save $XXX") ("and earn a quick promotion"), and way too little emphasis on problem identification and classification (where you will actually see this problem in the "real world", how your problem might be amenable to a "transportation model" even though it has nothing to do with transportation, why your actual mess will not be nearly as neatly structured as a textbook problem, etc.). This was exacerbated by a lack of user-friendly software, or perhaps any software at all.

The result was that we produced, at least in the U.S., generations of business graduates who's main take-away from their quant methods course was that they hated it and never wanted to deal with that stuff again. Their lack of enthusiasm when giving feedback to administrators paved the way for other disciplines to push aside quant methods courses and grab their space in the curriculum.  Quant methods is still required at many schools, and is very popular at some, but its "footprint" in the curriculum is often diminished, and it is all too frequently no longer required at all (excluding perhaps a basic statistics course).

Software and hardware are ubiquitous now, and the software quality is quite good. Based on recent market-leading textbooks, though, I believe we are still focusing general quant methods courses heavily on application of specific O.R. tools (linear programming, simulation, decision trees). Some skill building is fine, but it is hard to say whether planting graduates with good skills at small-scale modeling in supply chain, marketing or finance positions will lead organizations to attack larger and more complex problems (where O.R. analysts are needed), or will diminish the need for workers with O.R. training (because the generic business graduate can do enough of the analysis on his or her own). Perhaps more critically, it is not clear to me that a non-O.R. graduate with decent modeling skills for the scope and scale taught in a classroom will necessarily be able to identify larger opportunities that would justify bringing in consultants or creating an internal O.R. group.

The key here may be to dial back a little on teaching specific models and algorithms, and put more emphasis on general modeling and problem-solving skills (including recognizing the actual problem and delineating its scope).

Sideways

This is the direction that I think is most often overlooked. Small to medium businesses (SMBs), small non-profits and small governmental institutions (think your local school district) are probably underserved by the operations research community, particularly as they may tend not to be lucrative potential clients for consultancies. The key decision makers are often not business school graduates, and may have no idea that O.R. and analytics even exist (unless they know "analytics" in the sense of parsing web server logs). Presentations at local Chamber of Commerce meetings, participation in local business forums (do your local businesses have a LinkedIn group?), and even pro-bono consulting will help show people both what O.R. is about and how it can pay off. My guess is that this group is particularly ripe for word-of-mouth marketing.

As I said, this segment is probably not particularly lucrative monetarily. Every once in a while, though, one of those SMBs will take off and become a large company; hopefully they will remember the role O.R. played in their growth. Organizations in this category that benefit from O.R. help may also have the ear of politicians and university administrators, which may foster some growth in O.R. curricula. Finally, press reports of success stories at this level may catch the eyes of executives in larger firms.

Will Analytics Drag O.R. Back to Its Roots?

The INFORMS blog challenge for May is "O.R. and Analytics", so here goes ...

There are about as many definitions of "analytics" as there are explanations for the recent global economic crash. My take on "analytics" has been that, at least until now, what it meant to business executives was "take this huge pile of data and make sense of it". Operations research models in the real world have always relied on some level of data analysis, because models contain parameters and parameters must be estimated. (Outside the real world -- which is to say in academe and government service -- modelers get to make up whatever parameter values they like.) That said, I've never really associated heavy duty data analysis with O.R. Statisticians analyze data and data miners try to read sheep entrails (according to the statisticians); O.R. analysts build and use models.

As the term "analytics" grabs mind share among executives, though, O.R. societies and O.R. practitioners are trying, to borrow a phrase from Microsoft, to "embrace and extend" it. The societies see this as a way to boost membership and conference attendance, and both the societies and practitioners see it as a way to enhance the visibility of O.R. to the people who will (hopefully) employ O.R. analysts, directly or as consultants. I would not be surprised if the data analysis crowd see this as O.R. people trying to share the spotlight uninvited. Fortunately, since their forte is recognizing patterns as opposed to prescribing solutions, they'll see us coming but probably won't be able to keep us out.

Extending the O.R. brand will require more than just saying "operations research ... including data analysis" or "operations research is analytics ... plus so much more". If we're serious about this, we'll need to reconsider what we mean by "operations research", and perhaps how we go about its practice. Therein lies an opportunity to return to O.R.'s roots.

The history of O.R. traces back to World War II, and the stories from that era have a common thread. Someone has a problem. The problem appears somewhat quantitative in nature (or at least amenable to measurement and quantification). We want to model it, and see what the model suggests might solve the problem. Absent from this description is any pigeon-holing of the problem as a linear program, or a queueing problem, or a discrete event simulation. One of the classic examples was finding ways to move men and materiel from the U.S. to the U.K. more safely during the Battle of the Atlantic. The answer involved determining the optimal shape of a convey (which was not a mathematical programming problem, the word "optimal" notwithstanding), recognizing that small convoys of fast ships (small possibly meaning a single ship) might not need an escort (they were too fast for the U-boats to pick on), and so forth.

As O.R. bloomed after the war, we developed more and better tools (theory, algorithms, software) ... and along the way, we became more specialized. So now we have experts in optimization and experts in simulation and so on, and we tend to adhere to the maxim (which I will shamelessly bastardize) that if you're really good with a screwdriver, everything looks like a screw. At a recent INFORMS conference, I attended a session about teaching modeling to MBAs. Given the topic, I suspect most of the attendees were fellow academics, so I apologize if I offend any practitioners by tarring them with the same brush. At one point in the session, the presenters posed a scenario to us (the Red Cross is thinking about paying for blood donations, and wants some consulting on it), and, with not much more detail than what I just gave, turned us loose on it. The optimizers started writing optimization models. The simulators started sketching out simulation models. If there were any decision analysts in the room, I'm sure they were drawing decision trees. In other words, most of us framed the problem in terms of our favorite tools, rather than fleshing out the problem (which was quite vague) and then looking for tools (possibly mathematically unsophisticated tools) that would match it.

As we try to figure out how data mining and "business intelligence" (note that I'm skipping all oxymoron jokes here, a severe exercise in restraint) fit with O.R., perhaps we can seize the opportunity to starting conceptualizing (and teaching) O.R. as first and foremost sorting out and describing what the problem actually is. My very limited understanding of data mining suggests that it leans more toward letting the data tell you what it wants to tell you than to making the data fit a preconceived model; extend that to the overall problem, rather than just the data, and we're back to something I think the progenitors of O.R. would recognize.

Data Mining and Pharmaceutical Bar Tending

In a recent article in OR/MS Today (a sequel to his excellent article in Analytics), Douglas Samuelson writes about various OR opportunities as the health care industry in the U.S. reacts to the Mother of All Health Care Bills.  OR in health care also happens to be the theme of this month's INFORMS blog challenge (for which today's post is my entry). 

Let me focus on one particular statement in Samuelson's latest article:

Another aspect of uncoordinated care is polypharmacy, the use of multiple prescription medications in combination, with too little attention to possible interactions. According to the medical examiner’s official report, polypharmacy killed high-profile celebrities Anna Nicole Smith and Michael Jackson, both of whom used multiple doctors and multiple pharmacies. Safety testing is usually done one medication at a time, so interactions can take quite some time to become identified and publicized. This is a growing problem, and information technology offers a promising answer.

I've seen statistics asserting that accidental drug interactions cause a staggering number of "adverse results" (dying being counted as an adverse result).  Those events include not only prescriptions of multiple drugs whose interactions are unknown, but prescriptions of combinations with known interactions where the prescriptions may be issued by multiple doctors and/or filled at multiple pharmacies.  My physician's office asks patients to bring all their meds with them on visits (but of course I don't).  My guess is that many patients never think to mention some medications they are taking (or incorrectly remember names, which is fairly easy given the choice between an unpronounceable generic name and a brand name devoid of mnemonic value).  There are also patients who partially self-medicate (borrowing unprescribed medications from friends or relatives, taking left over pills from long-expired prescriptions, or ordering cheap drugs over the Internet, from suppliers who couldn't spell "prescription", let alone recognize one).

Since drug manufacturers cannot possibly test all possible combinations of medications, to a large extent risky interactions have to be identified the hard way.  As Samuelson states in the quote above, information technology (combined with data analysis) offers some hope there.  If changes to the health care system lead to more thorough (and more accurate) record keeping, there is an opportunity for data analysis to ferret out potential problems, which can then be tested in laboratories.  Better use of electronic record keeping will also help pharmacists detect when a customer is purchasing drugs that may interact in unfortunate ways, even if the purchases are being made at multiple pharmacies.

I think there is one more opportunity for "predictive analytics", though, and that is in identifying patients likely to be at greatest risk of an adverse interaction.  Just as considerable effort is going into profiling likely terrorists, so that time and energy screening travelers or inspecting cargo can be focused where it will do the most good, we can think about profiling patients.  If analytics allows us to identify patients at greatest risk, whether it be due to their errors or to errors by doctors or pharmacists, then perhaps either government or insurers can intervene (assign a case manager, warn pharmacists to ask extra questions, use a cell phone application to nag the patient, ...) and reduce the danger.  Making intelligent, data-driven decisions to achieve the best possible outcome:  sounds like OR to me.

The Diogenes Problem

Shiva Subramanian's post yesterday about "The honest politician and other rare events", his contribution to the January INFORMS blog challenge, got me thinking about the following OR problem.  Suppose that, in Philip José Farmer's Riverworld (of recent TV movie fame), we are able to take all the politicians that ever were (excluding those still living) and pack them into a finite rectangular enclosure.  Suppose further that we are able to assign a probability to each of them being honest (and that the probability function is not identically zero, which may be the hardest assumption to swallow in this Gedankenexperiment).  Now let's say we are able to map out a path for Diogenes that minimizes the expected time until his first encounter with an honest person (I'm assuming both male and female politicians are present) in the room.  Would that path be a space-filling curve?

OR v. CYA

People who work in operations research tend to believe that governments (and everyone else, but especially governments) would benefit from making more and better use of it. At the heart of operations research is logical, dispassionate analysis of how a system works, and how it can work better, quantifying options and possible outcomes using hard data where possible.

One of the most challenging areas in operations research is risk analysis. The challenges are many, and frequently the most difficult aspects are not algorithmic but rather in assessing probabilities using scant or messy data (how likely is a nuclear power plant to release radiation? we happily lack a large sample of incidents) and in attaching values to outcomes. Particularly problematic is assigning a value to a human life. It is done all the time, by insurers, by juries and, consciously or not, by government agencies. Adding to the difficulty is that mathematical analysis may produce results we as people find uncomfortable.

An example I've heard more than once (for which I have no citation) is whether government (here the Federal Aviation Administration) should require that infants on airline flights be parked in some version of a car seat. I imagine most people, at least before hearing the arguments, would say yes. The picture of an infant turning into a projectile during turbulence or a hard landing is very discomfiting. Against that, the analyst weighs the facts that (a) requiring the infant to be in a conveyor most likely imposes on the parents the requirement to buy another ticket, (b) the cost of an extra ticket will, at the margin, impel some number of families to drive rather than to fly and (c) on a per-mile basis, commercial flight is safer than driving. So requiring a safety seat for infants on flights might, paradoxically, lead to more injuries or deaths to infants during long trips, rather than fewer. (I'm restraining myself from saying something about "throwing the baby out with the bathwater".) (Apparently, I was not successful.)

Enter your friendly federal, state or local government representatives. They are locked into a perpetual (re)election cycle, so making decisions that would at first blush seem insensitive or uncaring is bad for business. When it comes to national security, the worst thing they can do is appear to do nothing. The guiding principle seems to be that good theater trumps good analysis.

Thus, after the attacks on the World Trade Center and Pentagon in 2001, the federal government instituted a variety of security procedures at airports that many fliers view as cosmetic at best. Some of the perpetrators were in the U.S. on expired student visas, so the federal government made student visas harder to get (and, in the process, scared off a significant number of international students, costing U.S. universities a fair bit of money.) In the aftermath of an attempt to smuggle explosive devices into the U.S. on cargo flights, the Transportation Safety Administration has moved up its target date for screening of 100% of air cargo, a move that was already in the works. What is unclear is the extent to which any rigorous analysis of costs and benefits went into any of these decisions. At least some of the new policies likely have helped avert additional attacks. Some may have created new jobs. Some assuredly imposed new costs on businesses, and some make air travel (already less than a thrilling prospect for those of us in sardine class) even less comfortable.

Whenever another event triggers a panicky reaction (and I'm waiting to see what the Tucson shootings yield), I think back to what my English relatives lived through during the Blitz, and the "duck-and-cover" drills of my childhood. (I lived about midway between New York City and Brookhaven National Laboratory, so I figured no matter which way the wind blew I was going to be in the radiation's path.) Back then people seemed a bit more accepting of risk, and the fact that Bad Things Happen and sometimes they just cannot be prevented, and elected officials were less concerned about theatrics.

In there era of sound-bite politics and tweet-length policy discussions, though, I'm afraid that OR is trumped by the political credo CYA. Better to be seen doing something pointless than to be perceived as doing nothing.

(The preceding rant was motivated by the INFORM blog challenge for January: O.R. and Politics.)

OR and ... Parking??

'Tis the season to shop our brains out.  Two trips to a local mall today (neither, oddly enough, for the purpose of shopping) has me reflecting on the science (art?) of finding and selecting parking spots.  Choosing a parking spot involves elements of stochastic search (anyone have a link for this?), optimization of a distance function, and (when the mall is busy) stochastic stopping rules.

The application of stopping rules is fairly obvious, although the rule to use may not be.  You're running a search pattern through the packed parking lot of a mall, looking for an empty spot, when lo and behold you find one.  Now comes the stopping rule:  do you grab it, or do you continue the search, hoping for one closer to your immediate destination (the first store you plan to hit)?  If you pass it up and fail to find something closer, it likely will not be there the next time you go by.  Add an objective function that balances your patience (or lack thereof), your tolerance for walking, the cost of fuel, any time limits on your shopping spree and the possibility of ending up in a contest for the last spot with a fellow shopper possessing less holiday spirit (and possibly better armed than you), and you have the stopping problem.

The other obvious aspect is optimization of a distance metric, and this part tends to amuse me a bit.  Some people are very motivated to get the "perfect" spot, the one closest to their target.  My cousin exhibits that behavior (in her defense, because walking is painful), as did a lady I previously dated (for whom it was apparently a sport).  Parking lots generally are laid out in a rectilinear manner (parallel rows of spaces), and most shoppers seem to adhere rather strictly to the L1 or "taxicab" norm.  That's the appropriate norm for measuring driving distance between the parking spot and the store, but the appropriate norm for measuring walking distance is something between the L1 and L2 or Euclidean norm.  Euclidean norm is more relevant if either (a) the lot is largely empty or (b) you are willing to walk over (or jump over) parked cars (and can do so without expending too much additional energy).  Assuming some willingness to walk between parked cars, the shortest path from most spots to the store will be a zig-zag (cutting diagonally across some empty spots and lanes) that may, depending on circumstances, be closer to a geodesic in the taxicab geometry (favoring L1) or closer to a straight line (favoring L2).  The upshot of this is that while some drivers spend considerable time looking for the L1-optimal spot (and often waiting for the current occupant to surrender it), I can frequently find a spot further away in L1 but closer in L2 and get to the store faster and with less (or at least not much more) walking.

This leaves me with two concluding thoughts.  The first is that drivers may be handicapped by a failure to absorb basic geometry (specifically, that the set of spots at a certain Euclidean distance from the store will be a circular arc, not those in a certain row or column of the lot).  Since it was recently reported that bees can solve traveling salesman problems (which are much harder), I am forced to conclude that bees have a better educational system than we do, at least when it comes to math.  The second is that, given the obesity epidemic in the U.S., perhaps we should spend more time teaching algorithms for the longest path problem and less time on algorithms for the shortest path problem.

[Confession:  This post was motivated by the INFORMS December Blog Challenge -- because I thought there should be at least one post that did not involve pictures of food!]