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.

The Most Desperately Needed Degree Program

This morning I stumbled across an article on Yahoo! Eduction with the provocative title "College Majors That Are Useless". Curiosity made me look at the article. What I saw made me double down on my morning coffee intake, since I assumed my brain was not yet functioning.

Two disclaimers are warranted. First, my majors were mathematics and mathematics (with a little statistics in between), so I have no personal attachment to the listed majors. Second, and somewhat contrary, I've spent almost 39 years at Michigan State University (the former Michigan Agricultural College), a land-grant institution with a very strong College of Agriculture and Natural Resources (CANR) and a respected agricultural extension service. While we are a typical, well-rounded university (strong in physics, education and a variety of other fields), we're very proud here of both our land-grant tradition and our strength in agricultural fields. (Note to snobs: Cornell University is another land-grant university.)

CANR is not hurting for majors, and I have not heard of any problems with placement of those majors, so I was rather shocked to see that the first, fourth and fifth "most useless" majors (agriculture, animal science and horticulture) all came from their domain. As a sidebar, we also offer the other two listed majors, apparel design and theater, albeit in different colleges. The article cites the "National Association of Colleges and Employers' (NACE) 2012 Job Outlook study", which is free to members (whoever they may be), and which apparently "surveyed almost 1,000 employers on their future hiring plans". Our library system does not have it, so I can comment on neither their methods of data acquisition and analysis nor the accuracy with which their findings were reported in the article. Naturally, that won't stop me from commenting on the article itself.

First, as a colleague pointed out to me, the article states that 24,988 agriculture degrees (baccalaureate? all levels?) were awarded (in the United States?) in 2008-2009. Amazingly, again according to the article, 24,988 horticulture degrees were awarded that same year.  (I should have gone to commencement exercises. Do you suppose that the two majors paraded together in pairs, as if boarding the ark?) The article reports 89,140 degrees awarded in fashion design that year, which in another coincidence is exactly the number of theater degrees awarded.  Two cosmic coincidences in the same article ... I wonder what the probability of that is?

For what it's worth, the article cites the source of the degree counts as The Daily Beast's list of "20 Most Useless Degrees". The first "useless degree" cited on that list, in what I consider to be a multilayered bit of irony (and with an apology to yet more of my colleagues), is journalism.

Second, referring to the NACE study, the article states that "[m]any areas of study, such as fashion design and the performing arts, didn't even make the list". Does this mean that two of the five "useless" majors were designated that way because there was little or no data in the study on them?  The article does quote job growth or decline projections for all five majors, including fashion design and theater, obtained from the U.S. Department of Labor.

Third, the criterion of "uselessness" of a major is not clearly spelled out in the article. From the focus on numbers of jobs and projected trends in those numbers, I infer that "uselessness" relates in some way to job prospects.  Operations researchers know that if you are going to develop a normative model, you need to define your criterion or criteria carefully.  This is what drove me to blog about the article: not just that the criterion is at best implicitly specified, but that it is not tied to the data in any logical way that I can see.

Is a major "useless" if the number of related jobs is declining?  That is suggested in the discussion of agriculture, the first (and therefore most?) "useless" major on the list. "... That means less [sic] jobs. In fact, the U.S. Department of Labor projects 64,000 fewer jobs in this field over the next seven years."  Okay, then why is theater (with projected job growth of 11% in the same time frame) third on the list of "useless" majors.

Is "uselessness" based on a glut of applicants?  You might speculate that from the inclusion of fashion design, where the government says there were 22,700 jobs in 2008 (with a projected 1% growth over the next seven years) and the article claims that 89,140 students (all with a dual major in theater?) graduated with degrees.  That would be rather scary if the only relevant job for someone with a fashion or apparel design degree were as a fashion designer (and assuming that fashion designers had a projected career span of more than three months).  My impression, though, is that retail chains like to hire fashion/apparel design majors as buyers, because they bring an understanding of the product to their work.  Similarly, agriculture majors are in demand for more than managing farms; food safety inspectors, sales representatives and marketers for firms selling agricultural equipment or products, buyers for grocery chains etc. may all benefit from that degree.  In any case, if the ratio of jobs to graduates is the concern (and I assume that jobs here include occupied positions, not just open positions), then agriculture (25,000 degrees in '08-'09 versus 1,234,000 "agricultural managers" in 2008) would seem to be a pretty appealing choice.  That's roughly one graduate for every 49 positions, which would be about replacement rate if you assumed 2% turnover per year.  For comparison purposes, if you ran a company with a fixed number of positions, and your employees stayed for life and retired after an average of 40 years on the job, that would be 2.5% turnover.  (By the way, in an article full of statistical "coincidences", I have to look at the first four digits of "1,234,000" and wonder if that's another one.)

I've ranted long enough, so let's just conclude this with two thoughts.  The first is that I am, shall we say, unpersuaded by the article.  The second, referring back to the title of this post, and tying into recent posts by Mike Trick and others, is that if I were trying to devise a new college major today, based on need, it would be titled something like "journalistic analytics", and it would focus not on parsing server logs at a site like the Daily Beast but rather on how to draw and present meaningful conclusions from the analysis of data.

Donating a Computer? Wipe the Drive!

Months ago I replaced my old single-core PC  with a new quad-core machine. Being a champion procrastinator, I'm only now getting around to donating the old box to charity. The easy part is assembling all the documentation, peripherals, etc. (I'm also a bit anal-retentive about storing documents.) The hard part turns out to be wiping the drive.

It should be common knowledge that you never give away a computer without first wiping its hard drive. Over the years, your various user IDs and passwords are stored on the computer in all sorts of places, some of which (at least with Windows) are a bit arcane. Stories have been written on the subject (see, for instance, "The Dangers of Donating or Discarding Your Old Computer", or "Hard Drives Exposed"), although I was unable to find any statistics on actual instances of identity theft from discarded drives. (I found lots of general discussion of the threat, much of it shockingly coming from companies that sell disk wiping software or services.) The same caution also applies to smart phones and USB (thumb) drives, and I suspect people are even less cautious about cleaning out their phones before recycling them. Anything that still works and has ever held a password is a candidate for scrubbing before you recycle or donate it, or before you hand it off to someone that you think is going to toss it in a landfill.

There is quite a variety of software, both free and commercial, designed to delete files and wipe drives "securely" from PC disks.  I put "securely" in quotes because security is a matter of degree. The only 100% secure way to eliminate sensitive information is to physically destroy the drive (break the platters into pieces, bathe them in acid, launch the remnants into the core of the sun, ...). Runner up is to run a shredder program that overwrites each disk block with various random patterns. The least secure approach is reformatting the drive, which typically does not wipe out old contents.

I'm not worried about an identity thief going over my donated hard drive with forensic equipment, so I'm satisfied with shredding all the files. For reasons unclear to me, though, that turned out to be problematic on the old machine. In fact, just booting the bugger turned out to be problematic. In my years of fighting with PCs, thermal expansion has usually been a problem when the machine was turned on and off, not when it was serving as an unplugged doorstop. Nonetheless, it took three tries reseating memory and PC cards before the old machine would boot, and a fourth try to get it to recognize the keyboard and mouse. Whether that relates to the subsequent adventures, I'm not sure.

My plan was to wipe the lone hard drive entirely and then reinstall Windows XP. To do so, I downloaded Darik's Boot And Nuke, which seems to be a highly regarded solution. Burn it to a CD or DVD, boot from the disk, follow a few simple instructions and watch your disk get wiped. Unfortunately, it consistently failed with a sequence of error messages that did not tell me what was going on. The old computer has a bunch of media readers (which I explicitly did not select for wiping); maybe they were causing problems. Maybe not.

As at least an interim measure, I installed Linux Mint Katya, using the entire hard drive and overwriting the Windows installation. That does not wipe all the data, although I feel moderately confident that the portion of the disk containing actual Linux files is sufficiently overwritten to defeat the casual data thief. The problem is all the unused space on the disk, which still contains whatever it held before I loaded Katya. After a bit of searching, I found the Linux shred command. The suggestion was to boot from a CD or DVD (I used the Katya installation CD) and run shred -vzf /dev/sda (replacing /dev/sda with the name of the actual hard drive partition). Small problem: the hard drive was not showing up in /dev. The Katya installation disk lets you mount the existing hard drive, so I did that.  It mounted as /media/<long number>.  Okay, fine, I would just shred /media/<long number> ... except I couldn't: the shred command said it was a directory and not writable (even with the -f flag, which should force things to be writable). Running shred with administrator privileges via sudo did not help.

After more searching, I found a helpful answer by David Spillett. Booting the clunker from the hard drive (Mint Katya), I opened a terminal in /tmp and entered the following commands:

dd if=/dev/zero of=zero.small.file bs=1024 count=102400
cat /dev/zero > zero.file
rm zero.small.file
rm zero.file

The drive capacity is 165 GB, and Katya's footprint is not all that large, so the second line was quite time consuming. The second line eventually ended in an abort due to lack of free memory. I'm not sure that was an intended result, but it does not seem like a bad thing.

Overwriting with one layer of zeros is not a very secure shred, but (again) I'm not that worried about someone using forensic hardware to recover my drive. If they do, they'll find their investment of time not well rewarded.

Max/Min Bounds

Motivated by a recent question on OR-Exchange, this post expands on a previous post about constraints that set a variable equal to the maximum or minimum of other variables in a mathematical program. Here I'll deal with inequality bounds (and with more than two variables involved in the maximum/minimum).

The setting is a mathematical programming model containing variables \(x_1,\dots,x_n\) and \(y\), where you want to bound \(y\) either above or below by either \(\max_{i=1,\dots,n} x_i\) or \(\min_{i=1,\dots,n}x_i\). Let's dispense with the easy cases first. Since \begin{eqnarray*} y\ge\max_{i=1,\dots,n}x_{i} & \iff & y\ge x_{i}\forall i=1,\dots,n\\ y\le\min_{i=1,\dots,n}x_{i} & \iff & y\le x_{i}\forall i=1,\dots,n \end{eqnarray*} those two cases are handled by expanding one nonlinear inequality into \(n\) linear inequalities, with no requirement that the variables be bound and no introduction of integer variables.

Now let's consider the case \(y\le\max_{i=1,\dots,n}x_i\). (The case \(y\ge\min_{i=1,\dots,n}x_i\) is symmetric and left to the reader as an exercise.) The key to our approach is that \[y\le\max_{i=1,\dots,n}x_i\iff \exists i \ni y\le x_i.\]To handle this case, we need a priori bounds on the \(x\) variables, say \(L_i\le x_i\le U_i\ \ \forall i\). Let \(\bar{U}=\max_{i=1,\dots,n}U_i\), and note that if the constraint \(y\le\max_{i=1,\dots,n}x_i\) is to hold, then clearly \(y\le\bar{U}\).

We introduce binary variables \(\delta_1,\dots,\delta_n\) and the constraint \[\delta_1+\cdots+\delta_n=1.\]Depending on the solver being used, it may be beneficial to specify to the solver that the \(\delta\) variables form a type 1 special ordered set (SOS1). Now add the following \(n\) constraints:\[y\le x_i + (\bar{U}-L_i)(1-\delta_i)\ \ \forall i=1,\dots,n.\]If \(\delta_i=0\), the right hand side becomes \(x_i+\bar{U}-L_i\ge\bar{U}\), and the constraint is vacuous. For the one index where \(\delta_i=1\), the constraint reduces to \(y\le x_i\), which is all we need.

Addendum 1: It belatedly occurred to me that it would be equally valid to replace \(\delta_1+\cdots+\delta_n=1\) with \(\delta_1+\cdots+\delta_n\ge 1\) (in which case it is no longer an SOS1 constraint). Requiring \(y\le \max_{i=1,\dots,n} x_i\) is equivalent to saying \(y\le x_1\) OR \(y\le x_2\) OR ... OR \(y\le x_n\), with the ors being inclusive. I have no idea whether this second version is more or less efficient computationally than using the SOS1 constraint.

Addendum 2: Erwin Kalvelagen posted some alternative, possibly tighter, formulations on his blog.

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