Category: Applications

Keto Diets and Linear Programming

In today’s New York Times Magazine, there is an article on how a ketogenic (“keto”) diet can be used to control epileptic seizures in kids.  The diet is quite something.  Referring to his son’s diet, the author Fred Vogelstein writes:

His breakfast eggs are mixed with heavy cream and served with bacon. A typical lunch is full-fat Greek yogurt mixed with coconut oil. Dinner is hot dogs, bacon, macadamia nuts and cheese. We figure that in an average week, Sam consumes a quart and a third of heavy cream, nearly a stick and a half of butter, 13 teaspoons of coconut oil, 20 slices of bacon and 9 eggs. Sam’s diet is just shy of 90 percent fat.

The diet contains almost no carbs, making it reminiscent of an Atkin’s diet during a particularly anti-carb phase.  This diet has the effect of greatly reducing the number of seizures in many kids, including those who have not responded to any of the possible drugs.  In Sam’s case, the seizures went from hundreds per day to perhaps a half dozen.

While a diet of bacon and ice cream seems like heaven, it is actually very hard to do.

For Sam’s diet to be effective, he must eat a certain number of calories every day with specific ratios of fat, protein and carbohydrates. These are not back-of-the-envelope calculations, but ratios that have to be hit exactly at every meal. If Sam wants a snack after school, he gets 18 grams of bacon (about two slices), 14 grams of macadamia nuts (about seven nuts) and 18 grams of apple (less than an eighth).

You can’t just throw together everything without carbs and hope that things work:

To jump through these arithmetic hoops, Evelyn, who gave up her career to take on the now full-time job of feeding Sam, plans meals on the kitchen computer using a Web-based program called KetoCalculator. It is hard to imagine how to administer keto without it. A meal for Sam might have eight ingredients. Mathematically, there are potentially millions of combinations — a bit more of this; a bit less of that — that gets you to a 400-­calorie meal and a 3-to-1 ratio.

I don’t have access to the Calculator (you need to be referred to it by a doctor), but it would be interesting to know if the site goes beyond just being a calculator.  Putting together ingredients to meet dietary requirements is a classical problem for linear programming.   Rather than just determine if a set of ingredients meets the requirements, a linear-programming approach would put the ingredients together in an optimal way to meet the requirements while optimizing some objective (like maximizing use of ingredients you have not eaten in the last week, or maximizing use of some food you have a craving for).  No hit-or-miss calculating:  the combination would be guaranteed to meet the dietary requirements.

You can check out the NEOS server to experiment with putting together a traditional diet.  I would love to experiment with a site that creates keto diets.  Imagine being able to turn an illegal, but palatable, meal into a legal meal by adding 3 macadamia nuts (and have the linear program automatically suggest that).

In the past, I have used the diet problem for laughs, but this seems to be a real application for  operations research that could be very useful (if it is not already being used).

Bus Bunching talk at INFORMS

New post at the INFORMS site: “Avoiding Bunches of Buses”:

While the INFORMS conference is big enough to stay within a narrow research area, it is also a great place to get inspiration outside your focus.  I hopped in to see a talk given by Don Eisenstein on work he has done with John Bartholdi on “scheduling” buses.  Don and I were in graduate school together, and we each had John as our advisor, but we work in completely different areas.

Don talked about a system they have put in place to handle buses, trollies, and other transportation systems that have multiple vehicles going over the same routes.  I am sure we have all had the frustration of waiting a long time for a bus, only to have three buses (all running the same route) appear in quick succession.  This phenomenon is common enough to form the title for a popular mathematics book.  Upon reflection, this situation is not mysterious.  If buses are scheduled on a route at, say, 10 minute intervals, then any delay in one bus (a slow entering customer, a traffic jam, and so on), will cause that bus to run even later.  Once delayed by two minutes, more passengers will arrive in the now-12 minute gap, further slowing down the bus.  Meanwhile, the bus following the delayed bus will go faster than normal due to a dearth of passengers for it.  Very quickly, a small increase in the gap will turn into a large gap ahead of the delayed bus and a small gap behind it.

This bunching behavior is very common, and very difficult to schedule around.  In fact, as buses try to keep to the schedule, drivers may resort to dangerous or illegal driving, particularly if drivers are evaluated by their ability to keep to a schedule.  This situation is made worse if a bus suffers a mechanical failure, leading to a large gap in the schedule until the bus can be replaced.

Overall, trying to keep a bus system running smoothly is a very difficult problem.  Lots of people have tried to create better, more robust schedules, but such systems are often complicated and difficult to implement.

John and Don propose a very simple method for handling such a system.  The idea is to have a small number of checkpoints in the system (in the example they chose, they had a checkpoint at each end of the route, with the bus going back and forth along the route).  When a bus hits a checkpoint, the system checks how far behind the next bus is.  If the next bus is expected to hit the checkpoint in 10 minutes, say, then the current bus waits a fixed fraction of that 10 minutes (say .6 times the following time, or six minutes in this case) and then departs.   There is a variant when a bus waits at least, say, 3 minutes after the preceding bus had hit the checkpoint.  That is the entire system!  Ignore schedules, but simply wait a fixed fraction of the time before the next bus arrives.

This simple system has the amazing property that it will self-organize into a nicely spread-out arrangement of buses, and will reorganize itself in the face of bus delays (or speed-ups).  If a bus goes out of operation, nothing special needs to be done:  the system will automatically move the buses into a evenly spread-out pattern (albeit longer apart, since there are fewer buses).  Of course, it also gives up on a fixed schedule, but for systems that arrive often enough, the schedule is generally not relevant to passengers (and in the example they gave, only known to the drivers, not to the passengers).

This research follows their previous work on self-organizing manufacturing systems.  The thing I like very much about this entire research direction is how well it includes robustness.  While simple, these self-organizing systems respond extremely well to changes in the environment, much better than many optimization approaches.

The presentation was very convincing, and Don and John promise a paper “in a few weeks”.  I look forward to reading it in more detail (and perhaps correcting any errors in interpretation I have of their work).

This was just one of the thousands of talks at this conference.  I was very glad I went outside of my normal research range to see this talk.

Watch the Edelmans!

I have said numerous times that the Edelman Prize presentations and papers are my favorite part of the operations research world.   It is fantastic to see and read about such great work in operations research.  The presentations often feature a Cxx of the firm.  Watching business leaders explain the importance of operations research never gets old to me.  And some of them actually read the script with feeling and (seeming) understanding (others look like they are reading under duress, with uzi’s pointed at them from just offscreen).

The Edelman’s have all been recorded through the years, and INFORMS (the professional organization that runs the Prize)  has experimented with how best to distribute the results.  We have gone from video tapes to DVDs to YouTube snippits.  There was always an issue of monetizing the presentations.  If this is our field’s best work, surely we can make money on it!  But making money limits distribution.

At least for now, INFORMS seems to have given up the money aspect, and even any membership aspect, and offers the most recent Edelman presentations for the low, low cost of a site registration.  Once you register, you can see all sorts of neat videos.  In addition to the Edelman finalists, there are Richard O’Neill’s talk on energy markets  (he is the chief economic adviser to the Federal Energy Regulatory Commission), Chris Tang’s talk on supply chain risk management, and the Wagner Prize finalists.  For all, there is a proprietary presentation which shows both the powerpoint slides and the speaker.

I do have one big complaint about this setup, however.  The system, as currently designed, appears to fall into a trap that operations research often sets for itself.  If you know you want what the system offers, it is easy to work with:  registration is fast and relatively non-intrusive.  But the listing of the videos is “behind the wall”, so someone interested in, say, energy markets, has no idea that this site would have a great talk on the subject.   Why aren’t all the talk titles and abstracts freely available?  Better yet, why bother with registration?  Based on the privacy agreement, it does not appear that INFORMS can even market to those who register.  Why hide anything?

For those of us in the know, this is a tremendous resource!  For those of you who have not yet discovered the beauty, fun, interest and (particularly) importance of operations research, I strongly urge you to go to the site and explore.  It might change your life.

Google Maps API Enhancements

Google just announced some enhancements to their Directions in Maps API.  One addition, “avoiding tolls and highways” doesn’t really affect me much:  we have only one toll road in the area, and it is pretty well needed to go either east or west.  But the other two are exciting!

First, the API now adds bicycle routing.  I don’t know if it will let you go the wrong way down one way streets or hop on a crowded sidewalk to make a shortcut, but it does contain at least some of the long-distance bike paths.  Check out the path from my house to my buddy Barack’s place.  There is a bike path starting from about 20 miles from Pittsburgh all the way to Washington, DC.  I turn 50 this year, and have promised myself that I will do that trip.  Of course, I have broken promises before, and if I don’t start training soon, it won’t happen.  But it is nice to see Google will be by my side if I do set off.

The second, and more relevant to OR, enhancement adds Traveling Salesman routing capability.  From the announcement:

Route optimization. Have many places to go but no preference as to the order you visit them in? We can now reorder the waypoints of your route to minimize the distance and time you must travel. Very useful for traveling salesman I hear.

Now I would love to experiment with this!  There have been similar efforts before.  Gebweb has offered routing since 2007, and promises optimal solutions for up to 15 cities with 2-opting solutions for larger problems.  I would love to know how far Google guarantees optimality before resorting to a heuristic (the demo on the announcement page limits you to 11 points).  Unlike the other additions, this has not yet made it to Google Maps, but when it does, let’s see how Google competes with Concorde.

INFORMS Practice Tutorials

The INFORMS Practice meeting coming up in Orlando has an extremely impressive set of methodology tutorials planned.  Here is the list:

360i
M. Kevin Geraghty, MS, Vice President, Research & Analytics, on “Marketing in Online Social Spaces.”

Business Forecast Systems, Inc.
Eric A. Stellwagen, BA, CEO & Co-Founder, on “Beyond Time Series Forecasting: Improving Forecasting Accuracy by Modeling the Impact of Promotions, Business Interruptions and Other Aperiodic Events.”

Chevron Corporation
Franklyn G. Koch, MS, Decision Analysis Practice Leader, Chevron Projects Resources Company, on “How Game Theory Yields New Insights to Decision Analysis in the Energy Industry.”

Federal Energy Regulatory Commission
Richard O’Neill, PhD, Chief Economic Advisor, on “Better, Smarter Electricity Markets: How Better Optimization Software Can Save Billions.”

Forio Business Simulations
Michael Bean, MS, President, on “How to Create Web-Based Simulations and Interactive Data Visualizations.”.

Georgia Institute of Technology
Ellis L. Johnson, PhD, Professor & Coca-Cola Chair; Industrial & Systems Engineering, on “A Framework for Choosing Optimization Software.”

Hewlett-Packard Corporation
Pramod Singh, PhD, Analytics Solution Architect, on “Marketing Campaign Optimization Is Hard (Especially in the Future).”

IBM Research
Robin Lougee-Heimer, PhD, Research Staff Member; Program Manager, COIN-O.R., on “Using Open-Source Solvers in Prime-Time Applications.”

Innovative Decisions, Inc.
Donald L. Buckshaw, MS, Senior Principal Analyst, on “The Balance Beam Process for Prioritization and Weight Elicitation.”

Intechné
Sanjay Saigal, PhD, President, on “Fueled by Randomness: Practical Probability Management.”

Intel Corporation
Erik F. Hertzler, MBA, Capital Supply Chain Staff Engineer, TME Capital Planning Group, on “Using Option Contracts with Suppliers to Reduce Risk and Build Win-Win Relationships.”

SAS Institute Inc.
Michael Gilliland, MS, MSE, Product Marketing Manager, Forecasting, on “Why are Forecasts So Wrong? What Management Must Know About Forecasting.”

Schneider National, Inc. & Princeton University
Ted L. Gifford, MS, Distinguished Member of Technical Staff and Hugo Simao, PhD, Senior Operations Research Engineer, on “Approximate Dynamic Programming Captures Fleet Operations for Schneider National.”

University of Cincinnati, College of Business
Jeffrey D. Camm, PhD, Professor and Head; Quantitative Analysis & Operations Management, on “The Art of Modeling.”

Xerium Technologies, Inc. & Vanguard Software Corporation
David Bryant, Vice President, Operations and Brian Lewis, PhD, Vice President, Professional Services, on “Global Optimization for Complex Production Scheduling Decisions.”

Veritec Solutions
Warren H. Lieberman, PhD, President, on “Effective Pricing.”

A few points: it is surprising how many tutorials are being given by non-academics: it will be fantastic to get a real-world view on these issues. Second, I am very impressed with the range of topics being discussed. Third, I would really like to see about 2/3 of these, but know that I will only have time for 2 or 3 (since Monday is fully scheduled for me for the Edelman competition). This is going to be frustrating! I think I will volunteer to do the conference scheduling in order to maximize the number of tutorials I can see.

If you are interested in this conference, note that the super saver registration deadline is March 1.

OR Snow Jobs

In my last post, I was grousing about being snowed in (Carnegie Mellon has been canceled three days and counting) and the need for more operations research in these sorts of situations.  I am pleased to see that my own university is taking up the challenge.  CMU President Jared Cohon has offered the services of the university to help the city create a state-of-the-art planning and operations system.  From an article in the Pittsburgh Post Gazette (and thanks to @bryanroutledge for pointing this out):

[Pittsburgh City Council Member] Mr. Peduto said CMU has offered to marshal faculty, staff and and students to create a “state of the art” snow removal tracking system that identifies priority areas for snow removal, maximizes the use of city equipment and follows through after emergencies with studies to guide budget decisions. It could also include geo-tracking of snow plows and treated streets, which is used in Maryland and elsewhere, he said.

The offer includes help from “the department of engineering and of computer science, the Heinz School” and other CMU departments, said Mr. Peduto, whose district includes the Oakland campus. “They’ve offered the full services of the university to create a better system.”

Snow removal has certainly been looked at by those in operations research. For instance, James Campbell of University of Missouri-St. Louis has been working on these problems for more than fifteen years. Even earlier, in 1976, Gene Woolsey wrote on snow removal in a delightful Interfaces article entitled “Three digressions on the routing of trucks” (the article is also available in the wonderful book The Woolsey Papers). In the article, Gene writes about giving a talk to city managers in Colorado:

After my speech, a city manager approached me with the following problem he had been facing for some time. It seems that the city council in his city had some years ago cleverly set the tim for council meetings at 6:00AM on alternate Tuesdays. The reason for this time should be immediately obvious, as it assures that only the citizen who is really upset will rise up to vent his spleen at that hour.

Unfortunately, when it comes to snow removal, lots of people rose early to complain. Gene’s solution?

Find out how the council members get to the council meeting from their homes, and clear those streets first. If you are not already doing this, and you do it in the future, I suspect that the complaints will go down.

That is really an OR snow job! If I had to guess, Pittsburgh discovered this plan years ago. This week’s storm suggests the need for a somewhat more all-encompassing approach.

Without Operations Research, Gridlock!

In many applications, it can be difficult to measure the effect of an operations research project.  For instance, my colleagues and I provide schedules for Major League Baseball.  What is the value added by the operations research we do?  MLB doesn’t have the time, energy or money to handle multiple schedulers in parallel:  they decided five or so years ago that they liked our schedules, and they have been using us since.  We have gotten better over time.  What is the value now?  Who knows?  The non-operations research alternatives no longer provide schedules, and the process, in any case, was not “here’s a schedule, evalute it!”:  it is much more interactive.

gridlockOnce in a while, circumstances come together to show the value of operations research.  If you have been trying to drive anywhere in Montgomery County, Maryland (northwest of Washington, D.C.), you have had a chance to see how traffic systems work without the coordinating effect of operations research systems.  A computer failure messed up the synchronization of traffic signals.  From a Washington Post article:

A computer meltdown disrupted the choreography of 750 traffic lights, turning the morning and evening commutes into endless seas of red brake lights, causing thousands of drivers to arrive at work grumpy and late, and getting them home more frustrated and even later.

The traffic signals didn’t stop working.  They continued, but they no longer changed the time spent “green” in each direction based on time, and they no longer coordinated their “green” cycles along the main corridors:

The system, which she described as “unique” in the Washington region, is based on a Jimmy Carter-era computer that sends signals to traffic lights all over the county. On weekday mornings, it tells them to stay green longer for people headed to work. And in the evenings, it tells them to stay green longer for people headed home.

It also makes them all work together — green-green-green — to promote the flow of traffic. That happens automatically, and then the engineers use data from hundreds of traffic cameras and a county airplane to tweak the system. When there is an accident, breakdown or water main break, they use the computer to adjust signal times further and ease the congestion around the problem.

It’s great when it works, a disaster when it fails.

Of course, without operations research, which determines the correct times and coordinates it across the network, it would be a disaster all the time.  Here’s hoping they get back to the “optimized world” soon (as seems to be the case).

Show Off Your Best Work in Operations Research Practice

I am a huge fan of the Franz  Edelman Award for Achievement in Operations Research and the Management Sciences (best work in operations research practice) given by INFORMS.  The applications are uniformly inspiring and the presentations go way, way beyond the norm for our field.  The full papers, published every January in Interfaces, are ones that I actually look forward to (something I don’t do for my own papers!), and form a big part of an MBA course I teach here.

Being an Edelman finalist is a tremendous commitment:  in addition to the full paper, the presentation generally requires the cooperation of a Cxx of the firm  (for suitably high xx: EO is great!).  Don’t try to get by with half-baked work here:  you won’t get past the initial phase.  But if you become a finalist (let alone a winner), the fame is worth it!  This is a great opportunity to get the attention a level or three higher than you might otherwise (and give the Cxx the opportunity to brag on your behalf).

If you are doing operations research that is truly changing how an organization works, I strongly encourage you to enter it in the competition.  The initial phase only requires a 2-3 page description.  See the full details here.  Deadline is October 21, so get typing!

Punk Rock OR Blogger Addresses Aviation Security

Laura McLay, author of Punk Rock Operations Research, has an interesting research paper out on identifying risky airline passengers in order to increase security for them. It is costly (both in money and in passenger inconvenience) to subject everyone to the highest level of screening. So who should be screened, given limited screening resources? Laura worked with Sheldon Jacobson (who is frequently seen in this blog) and Alexander G. Nikolaev on this problem, and they published their work in the June 2009 issue of IIE Transactions (IIE Transactions, Volume 41, Issue 6 June 2009 , pages 575 – 591).

From the VCU Press release:

Changes in aviation security policies and operations since the Sept. 11, 2001, terrorist attacks have resulted in every passenger being treated as a potential security risk, with uniform screening of passengers and their luggage. Screening all passengers the same way is costly and inconvenient for air travelers, according to the research, published in the June 2009 issue of “IIE Transactions.”

“We set out to find a real-time screening methodology that considers both available screening resources and the necessity of being robust in assessing threat levels,” said Laura A. McLay, Ph.D., an assistant professor in the VCU Department of Statistical Sciences & Operations Research. “This paper provides methodology to quickly determine which passengers are high-risk and who is low-risk and screen them accordingly,” McLay said.

Here is the full abstract:

Designing effective aviation security systems has become a problem of national concern. Since September 11th, 2001 passenger screening systems have become an important component in the design and operation of aviation security systems. This paper introduces the Sequential Stochastic Passenger Screening Problem (SSPSP), which allows passengers to be optimally assigned (in real-time) to aviation security resources. Passengers are classified as either selectees or non-selectees, with screening procedures in place for each such class. Passengers arrive sequentially, and a prescreening system determines each passenger’s perceived risk level, which becomes known upon check-in. The objective of SSPSP is to use the passengers’ perceived risk levels to determine the optimal policy for screening passengers that maximizes the expected number of true alarms, subject to capacity and assignment constraints. SSPSP is formulated as a Markov decision process, and an optimal policy is found using dynamic programming. Several structural properties of SSPSP are derived using its relationship to knapsack and sequential assignment problems. An illustrative example is provided, which indicates that a large proportion of high-risk passengers are classified as selectees.

As the New York Times reports, the TSA is upgrading its security by requiring things like real names (not nicknames) on tickets. Perhaps operations research can offset some of the inconvenience of these “upgrades”.

Advertising Operational Research (but maybe a few updates are in order?)

The Operational Research Society (the U.K. equivalent of INFORMS) has a website about operational research (the U.K. equivalent of operations research) aimed at students and teachers called Learn about OR. This makes a great adjunct to the INFORMS site, the Science of Better, aimed at business. Lots of good examples and good advice about getting into the field.

For portions, however, the site shows the tone-deafness that we in OR often show. Some of the examples might be a little more relevant to a 50-year-old rather than a teenager. Consider the example aimed at 11-14 year olds “OR Inside Your Holiday Snaps”:

It’s highly unlikely that, while you were snapping your holiday photos on the beach, you stopped to think, ‘Is there O.R. inside the film in this camera’? But, in fact, there is!

Photographic film is manufactured in rolls about 6km long by 1m wide, which have to be cut up into complex patterns so as to produce a wide variety of products. The problem of deciding how to cut the rolls is very complicated

What a great example: cutting photographic film is a wonderful example leading to column generation approaches and other advanced math programming methods. Too bad the average twelve year old hasn’t ever seen photographic film. I look forward to examples of fitting music onto cassette tape cartridges and optimal horse rotation for mail delivery.

Despite this cavilling, it is a good site, and the sort of site the world needs more of. There is even a introductory video that covers the range of OR (with instructions for downloading to an ipod).

Thanks Dawen, of ThinkOR, for mentioning the site in a somewhat different context.