Optimal Cleaning Paths

Yesterday I twittered:

Doing too much operations research. Spent more time figuring out optimal mowing pattern than mowing lawn.

roombaToday, I came across a picture of a Roomba’s path to clean the floor of an l-shaped room (through a number of sites, but I think I am referring to the original). I think I am a little more efficient in lawnmowing, but, then again, I know the shape of my lawn: Roombas figure out the shape dynamically. Interesting OR problem to come up with the optimal Roomba algorithm.

Blogging for the INFORMS Practice Meeting

I am one of a stable of guest bloggers for the INFORMS Practice Meeting. Rather than double post, I’ll move over to that blog for a few days (unless I have something to say that isn’t appropriate for an INFORMS blog), with pointers from here.

My first entry there: Tough Choices!, where I complain about an embarrassment of riches.

I’m getting organized to head off to the INFORMS Practice Conference.  I fly out Saturday, and will meet up with some friends to go to the Diamondbacks game.  Sunday is shaping up to be a very full day.  I really enjoy the Technology Workshops, where software companies in operations research talk about their recent products and plans for the future.  This year is shaping up to be particularly interesting due to all the activity in the market.  Since last year’s meeting,

  1. Dash Optimization (makers of Xpress-MP) has been bought by FairIsaac, which is now named FICO
  2. ILOG has been bought by IBM, and is now styled “ILOG, an IBM Company”
  3. Gurobi has been founded by some of the people who used to be with ILOG
  4. Microsoft Solver Foundation has started
  5. Dynadec has been formed to market Comet, a hybrid optimization, constraint programming, local search solver

and undoubtedly much more that I missed along the way, but will find out at the conference.  All of these companies and many others and more will be presenting “half day” workshops on Sunday:  they are really three hour workshops so you can get in three of them during a very long day.  The hard part is trying to figure out which three of the twelve workshops to attend!

Back at the IMA

I am at the Institute for Mathematics and its Applications at the University of Minnesota.  This brings back very fond memories.  I was a postdoc here 21 years ago at the start of my career when they had a Special Year on Applied Combinatorics.  As I recall there were 10 postdocs that year:  nine combinatorialists and me who was trained in operations research.  The combinatorialists were all scary smart and many (including Bernd Sturmfels) went on to sparkling careers.   Doing my two postdocs (in addition to the IMA, I spent a year in Bonn, Germany at Prof. Korte’s Institute) was the best thing I have done in my career.  The postdoctoral time gave me the opportunity to move past my doctoral work and to start new research directions even before I took a permanent position.  And, given I met my wife during my postdoc in Bonn, the social aspects were also wonderful.

I am speaking tonight in the IMA’s Math Matters series.  My topic is “Sports Scheduling and the Practice of Operations Research”.   The talk is open to everyone,  so if you are in the Minneapolis area, feel free to come on by!  There has already been some press on this.

Have you Registered for INFORMS Practice?

The INFORMS Practice Conference is one of my favorite conferences. It is here that I get most of my stories for my classes and get inspired about the areas I work in. I also get inspired about Operations Research in general: it is a great field, and this conference shows the wonderful things we do.

If you haven’t been to a Practice Conference, it is nothing like the big fall conferences.  The Practice Conference is seen as a “Listener’s Conference”:  unlike the main conference where anyone can present, only invited speakers present at the Practice Conference.  The quality of talks given by invited speakers ranges from good to unbelievably amazing (in contrast with the fall conference where the lower bound is much, much, much lower).  There are very few parallel sessions (no more than 5 or 6) and there are lots of opportunities for interaction, greatly enhancing the social capital of the conference.

Unfortunately, it is not a cheap conference.  Running a conference of the quality of the Practice conference takes money.  So if you are planning to go, be sure to register by February 27 to save yourself $150 or so.

Of course, one highlight of the conference is the  Edelman Competition.

I already have my registration in!

The Edelmans are here!

The January-February 2009 issue of Interfaces is now online, which means the papers from the 2008 Edelmans have now arrived.  My only disappointment is that my “OR Techniques for Consultants” course was moved up 7 weeks, so this year’s students had to make due with last year’s papers.

The papers include:

A Sheriff Goes to Jail for Not Using Operations Research

An Alabama sheriff spent time in jail for not feeding his prisoners enough.  From the CNN Report:

A federal judge ordered a north Alabama sheriff jailed this week, saying the lawman intentionally served jail inmates “woefully insufficient” meals in order to pocket more than $200,000.

At issue is an Alabama law that attorneys for the inmates claim provides sheriffs with an incentive to skimp on feeding inmates. Under the law, sheriffs are permitted to keep — as personal income — money left over after purchasing food for inmates.

The state provides sheriffs with $1.75 per day per inmate for food, according to the Alabama Attorney General’s Office. However, in a March 2008 opinion, the office affirmed that sheriffs may legally keep what is left over.

A typical dinner was two hot dogs or meat patties; a slice of bread; and mixed vegetables or baked beans, the judge wrote.

Of course, if Sheriff Bartlett had studied operations research, he would have immediately recognized his issue as the well-known “diet problem” in linear programming.  A quick google search would have led him to the NEOS page on the subject.  Some clicks, and the magic of linear programming gives an optimal diet of cost just 96 cents:

The Optimized Menu

The cost of this optimal diet is $0.96 per day.

The Solution and Cost Breakdown by Food

Food Servings Cost ($)
Carrots,Raw 0.24 0.02
Peanut Butter 3.60 0.25
Popcorn,Air-Popped 4.82 0.19
Potatoes, Baked 3.54 0.21
Skim Milk 2.17 0.28

2000 calories, and it meets all the nutritional requirements. I bet the Sheriff wasn’t making 79 cents off each prisoner per day with his plan! I would love to see the lawyers get a hold of this: “But judge: potatoes with peanut butter are the perfect food! Carrots on the side, and milk to wash it down. We even give them popcorn for movie night! What’s not to like?”

Happy Birthday CPLEX

More than 20 years ago, Bob Bixby decided the world needed a better linear programming code. This wasn’t a particularly obvious decision. First, there were already existing linear programming codes. Second, linear programming implementation was not exactly a hot research topic. Third, Bixby was not particularly known in this area. A typical paper for Bixby would be “On Reid’s Characterization of the Ternary Matroids” (Abstract: In this paper the author proves a stronger version of a result of Ralph Reid characterizing the ternary matroids (i.e., the matroids representable over the field of 3 elements, GF(3))…). Hardly the sign of someone about to write a great linear programming solution code!

Fortunately, Bixby is really, really smart, so in short order, Bixby got a very good code together, and began to show the research issues involved in implementing linear programming. And the code got better and better, due in part to an eagerness to collect hard linear programming problems and to continuously improve the code based on them. You can read more about this history in the article Bob wrote for the 50th anniversary edition of Operations Research in 2002 in an article entitled “Solving Real-World Linear Programs: A Decade and More of Progress“.

CPLEX is now owned by ILOG, and ILOG is celebrating the 20th anniversary of CPLEX. They just put out a press release on the birthday. Yours truly has a part in the release, providing a quote, and, less obviously, an application:

United States Postal Service (USPS) has realized more than $10 million in savings to date by leveraging ILOG CPLEX for a strategic transportation management initiative. Developed by USPS and IBM, the Highway Corridor Analytic Program (HCAP) uses advanced technology to analyze USPS highway transportation scenarios and identify cost saving opportunities. HCAP model uses ILOG CPLEX to identify the best allocation of mail among transportation resources.

That is work I did with USPS, IBM Global Business Services, and Luis Zuluaga, now at the University of New Brunswick.

The Price of Anarchy

Most days, I go out for coffee two or three times with a gang of economists and finance professors.  As “the OR guy”, my role is generally to ask a few dumb questions, so they can patiently explain some economic effect, at which point one of them will disagree with the other, and they will go around in circles until it is time to go back to work.  Great fun!

One of the uniting and overriding themes of economics (at least as taught in US business schools) is the overriding value of individual choice and the way markets will lead to efficiencies.  Periodically, I get into discussions on how individual’s make their choices, and how some of those choices seem computationally impractical.  For instance, most of my asset allocation problems (i.e. spending my paycheck) seem to be well modeled by mixed-integer programs, but I don’t actually set up such programs, and I likely couldn’t solve them if I did.  I just make some choices and get by.  Am I doing the best thing?  “Yes”, say my economist friends, since otherwise I would do something else.  And maybe by including the cost of setting up and solving mixed integer programs, they are right.  But once in a while we reach an understanding that frictions and information issues and all the other things that get in the way of pure rational economics are important.  And we drink a bit more coffee.

I’m reminded of this in two ways recently.  First, Hari Jagannathan Balasubramanian, author of the “Thirty letters in my name” blog (and OR person) points out an Economist article on how removing roads might reduce traffic jams.  From the article:

Hyejin Youn and Hawoong Jeong, of the Korea Advanced Institute of Science and Technology, and Michael Gastner, of the Santa Fe Institute, analysed the effects of drivers taking different routes on journeys in Boston, New York and London. Their study, to be published in a forthcoming edition of Physical Review Letters, found that when individual drivers each try to choose the quickest route it can cause delays for others and even increase hold-ups in the entire road network.

My initial impression was “How the heck could they publish something like this?”.  Haven’t they heard of Braess’s paradox?  Well, I guess they had, and that the purpose of the paper was to see how it might occur in practice in Boston.

In Boston the group looked to see if the paradox could be created by closing any of the 246 links. In 240 cases their analysis showed that a closure increased traffic problems. But closing any one of the remaining six streets reduced the POA of the new Nash equilibrium.

Still seems a funny paper for Physical Review (but I should withhold judgment until I read it).   In general, algorithms papers in Science, Nature or many of these other “non-OR, non-CS, non-Math” journals seem a little more suspect than your average Operations Research paper.

The second aspect of individual choice versus centralized choice is in the current financial crisis.   Here it seems like individual (firm) choice is great until they get a little stuck, and then they need centralized help to get out of their mess.  I do believe in individual choice, but I think somewhat better operations research models might have helped them avoid this mess in the first place.  And perhaps some OR will help out of this by pointing out how $700 billion might be allocated in order to have best, most fair, effect.

Added September 26. The paper from Physical Review Letters is now available (search on “Price of Anarchy”0.  I think (and an email from network-guru Anna Nagurney confirms:  see her Letter to the Editor of the Economist) that this is a case of physicists rediscovering what others have known for a long time.  I did find the detailed analysis of Boston quite interesting though.

More about Airlines and Operations Research

Another sign of the difficulty operations research has in getting implemented within airlines comes from the National Post in Canada:

Attention passengers: most airlines make boarding more painful than necessary by insisting on traditional back-to-front boarding even though new research shows it can be done faster.

Back-to-front boarding is only marginally more efficient than front-to-back boarding, but much slower than filling seats in alternate rows, beginning with windows seats from back to front, then middle and aisle seats.

The new research, to be published in the forthcoming edition of the Journal of Air Transport Management, found this optimal boarding method cuts down boarding time by about half, from 25 minutes to 12 or 13 minutes for an aircraft that seats 120 passengers. Back-to-front boarding is “very likely the second worst method,” concludes American physicist Jason Steffen.

There has been previous work on improved boarding.  Will airlines use it?  Probably not:

In Canada, the two major airlines say they like the status quo and have no plans to redraft boarding policies based on new research showing there are faster ways.

WestJet has tried out different boarding methods, and has landed on random boarding. The company won’t release details of its tests, but says random boarding is up to 20% faster than sequential boarding.

Air Canada conducted its own research a few years ago to test various boarding techniques, including random boarding and window-middle-aisle ordering.

Spokesman Peter Fitzpatrick conceded that while traditional back-to-front “is not necessarily the most expeditious, we concluded it is the most customer-friendly. Customers are accustomed to the system, so we do not have to provide a lengthy explanation prior to every flight.”