Off to Iceland!

Iceland GeyserI leave tomorrow for Iceland for the EURO 2006 conference. Busy time: in addition to the IFORS Administrative Committee Meeting, I am giving a semi-plenary on “The Society of Operations Research” (more on social capital and OR) and introducing Saul Gass as the IFORS Distinguished Lecturer.

They expect more than 1700 participants at this conference, almost triple their initial expectations of 600. This has been a huge issue for the organizers since it is a busy period in Reykjavik and there are only about 3000 rooms in the city. They have done an amazing job!

Since INFORMS Pittsburgh is also looking larger than expected (with more than 3200 abstracts submitted) it is clear there is quite a bit of enthusiasm for conferences. I am not sure why that is… perhaps the economy is better so people have more travel funds.

I’ll try to post some thoughts from the conference, along with some Reykjavik pictures.

Mark Cuban on Operations Research

Mark CubanMark Cuban is the owner of the Dallas Mavericks basketball team (and billionaire, having timed the dot-com boom and bust pretty well). He is certainly outspoken, amassing hundreds of thousands of dollars of fines for complaining about referees, opposition, and the league. But he also wants to bring a bit of analysis to the game. In a recent blog entry, he is practically begging for more operations research (as always, Steven Baker of BusinessWeek got to this before me in his Blogspotting blog):

The easiest thing in the world for anyone to do is Tivo a game and then break it down. What any of the 13 participants on the court did and how they did it is pretty easy to document for 99.9 pct of the time on the clock. The other .01 can be grey. It doesnt really matter. Aggregate data from a lot of games over a lot of seasons, and all of the sudden you have a database with value.

Once you have information, then you can add brainpower and try to do things better.

Once you have information, then you can start to define excellence and strive for it, measuring your progress along the way.

This certainly isnt a new concept. There are untold number of QC , Process Improvement and Optimization techniques out there. Pick one, pick them all.

Wayne Winston is one of the people working with Cuban, as I wrote in a previous entry.

Logistics in the Economist

Brian Borchers of New Mexico Tech sent me an alert that the Economist magazine of June 15, 2006 has a number of articles on the changing face of logistics. One article is on eCourier, a London based courier service. The heart of the system is operations research in the form of algorithms for courier scheduling:

The key to the service is picking the right courier, says Mr Allason[one of the founders of eCourier]. The one whom the GPS system shows to be nearest to the job may not necessarily be the most appropriate. For instance, a courier in London may be only a few hundred yards away from a collection address, but if he is on the other side of the Thames it could take him 15 minutes just to cross the river. Other information, such as traffic problems and the performance of individual couriers, also needs to be taken into account.

This is a mathematical problem, and eCourier spent some time hunting around for someone able to solve it. Eventually it found a team led by Cynthia Barnhard [sic], a logistics expert at America’s Massachusetts Institute of Technology, which devised an elaborate algorithm that is now at the heart of eCourier’s business, in much the same way that a mathematical formula drives Google’s search engine. What Mr Allason particularly likes about his internet-based courier system is that it is easily “scaleable”: more couriers and markets can be added without having to hire many more dispatchers or people to run a call-centre.

The “Cynthia Barnhard” referred to is Cynthia Barnhart of MIT who among about 40 other jobs is co-director of their Center for Transportation and Logistics. Perhaps when the magazine corrects her name, they might also mention the phrase “operations (or operational) research” to describe her field!

This is a good example of one of the growth areas in operations research: OR applied to “smaller” problems. While 10 or 20 years ago, OR needed an airline or other huge organization to justify its use, the easier accessibility to software and more routine use of models allows it to be used in smaller organizations. This is also a great example of how an entrepreneurial company can use OR to gain tremendous competitive advantage.

Update June 29, 2006

There is an interesting article from eCourier about how “Cynthia Barnhard” helped out in this project.  It does appear an “italian team” did most of the implementation. I hope some day some company tries to woo me with fruit baskets!

Emergency care at breaking point

The Institute of Medicine, one of the National Academies, has a series of reports out about the state of emergency medical care in the United States. The report is scathing in its assessment:

Despite the lifesaving feats performed every day by emergency departments and ambulance services, the nation’s emergency medical system as a whole is overburdened, underfunded, and highly fragmented, says this series of three reports from the Institute of Medicine.

As a result, ambulances are turned away from emergency departments once every minute on average and patients in many areas may wait hours or even days for a hospital bed. Moreover, the system is ill-prepared to handle surges from disasters such as hurricanes, terrorist attacks, or disease outbreaks.

The full reports are available for purchase, but there is a report brief that summarizes the main conclusions. The number one recommendation for fixing these problems? Use operations research, of course:

Tools developed from engineering and operations research have been successfully applied to a variety of businesses, from banking and airlines to manufacturing companies. These same tools have been shown to improve the flow of patients through hospitals, increasing the number of patients that can be treated while minimizing delays in their treatment and improving the quality of their care. One such tool is queuing theory, which by smoothing the peaks and valleys of patient admissions has the potential to eliminate bottlenecks, reduce crowding, improve patient care, and reduce cost. Another promising tool is the clinical decision unit, or 23-hour observation unit, which helps ED [Emergency Department] staff determine whether certain ED patients require admission. Hospitals should use these tools as a way of improving hospital efficiency and, in particular, reducing ED crowding.

This is exactly the sort of problem where a bit of OR can go a long way.

Resource Pointers

I was vexed to see that there was a bug in the software at the INFORMS Resources Page that sprung up in the transition to a new machine at INFORMS Online.  For the past two months, no submission to the system was being logged.  The worst part is that no one seemed to notice!

This system used to be “Michael Trick’s Operations Research Page”, and was, I think, a key resource on the web in OR/MS.  Now, with the advent of google, it is unclear what role these resource collections have.  If you know roughly what you are looking for, simply googling terms seems the right way to find things.  If you don’t, however, these resource collections can be useful.  But they are incredibly painful to keep up to date (about 15% of the pointers at the site are not valid, but keeping on top of them takes a lot of time).  Two-thirds of the submissions are not OR/MS related, so the editing process is pretty tedious.  So is the effort worth the usefulness, or is this just another aspect of the web that had its time?

Cutting Edge Pittsburgh

For those of you wondering whether Pittsburgh will be interesting enough for this year’s INFORMS Conference, cnn.com has a posting on Cutting-Edge Pittsburgh. Based on the number of abstracts submitted (more than 3100 to date;  the SF meeting in 2005 ended up with 2877), it certainly seems possible that this conference will be INFORMS’ largest ever. Between this and the amazing registration numbers at the EURO meeting (if you don’t already have a hotel room, be prepared to scramble: we have filled up Reykjavik), it is certainly easy to see OR as a vibrant, growing field!

Applications of Optimization with Xpress-MP

Applications of Optimization with Xpress-MP coverThere are very few books out about how to model problems in linear and integer programming. Hugh Williams book “Model Building in Mathematical Programming” is one. The documentation that comes with commercial software is another resource. Dash Optimization has made their “Applications of Optimization with Xpress-MP” available for free download. This book goes beyond the standard “3 variable 2 constraint” models found in so many textbooks.

Constraint Programming and Google Scholar

I am in Cork, Ireland for this year’s CP/AI-OR conference. This is a conference series that revolves around issues that constraint programming and operations research have in common: integration of techniques, applications, software systems and so on. I really like this conference series (disclosure: I am on the steering committee for the conference, so I would like it to be successful!). Like many computer science conferences, and unlike most OR conferences, this is a competitive conference with a rejection rate close to 80%. So the quality is high, but the number of participants is somewhat low: nothing like rejecting a submission to discourage participation! But the small size (about 60) means an opportunity to talk to lots of people.

Being in Ireland, we naturally ended the evening with a pint of beer (Murphy’s or Guinness for the cool people, lagers for the others), and we started discussing the most referenced papers in constraint programming or satisfiability (according to Google Scholar: see my OR version of this). Checking a few possibilities, here are some data, though I think this can be improved:

“A Computing Procedure for Quantification Theory” by Davis and Putnam, 1002 references (the fundamental algorithm for SAT solvers)
“Chaff: Engineering an Efficient SAT Solver” by Moskewicz, Madigan, Zhao, Zhang, and Malik: 880 references

“Partial Constraint Satisfaction” by Freuder and Wallace, 447 references

“Generalized Arc Consistency for Global Cardinality Constraint” by Regin (my favorite!), 128 references

Constraint Programming in Logic Programming, van Hentenryck 731 (book)

“Temporal Constraint Networks” by Dechter, Meiri, and Pearl, 710 references

Again, you are welcome to post other high ranking papers and books!

Update June 6, 2006

Both Pascal van Hentenryck and Diego Olivier Fernandez Pons point out that Régin’s most cited paper requires the “é” to find. I wondered where the alldiff paper went!

A filtering algorithm for constraints of difference in CSPs
JC Régin – Proceedings of the twelfth national conference on Artificial Intelligence has 285 cites in Google scholar.

It is interesting that Google Scholar seems smart enough to combine papers with slightly different spellings: there are no cites without the “é” of the above, and no cites with an “é” in the gcc paper cited earlier.

More OR and Sports

I missed this earlier article from the Wall Street Journal entitled “The NBA Tries to Make Teamwork a Science” on how teams in the National Basketball Association are trying to measure “team” effects of their plays (thanks Otis Smith for pointing this out). Basketball, more than many sports, relies on smooth teamwork for a team to be successful. This leads to an interesting data mining issue. The article link expires in 7 days, but here are a few excerpts:

In a league long dominated by high-flying superstars, more teams are focusing this season on teamwork — and turning to surprisingly scientific methods to measure it. New technology makes it easier to track the performance of every combination of five players that steps on the court, in a long list of game situations, from out-of-bounds plays to pick-and-rolls to zone defenses. As different player mixes yield different results, teams are beginning to quantify the elusive concept known as chemistry.

[Wolf Pack: Eddie Griffin (far left) and Kevin Garnett (center) click on the court.]
Wolf Pack: Eddie Griffin (far left) and Kevin Garnett (center) click on the court.

Say, for example, that after a coach inserts two particular players into a game, the opposing team has trouble scoring. Getting ready for the next opponent, the coach might flip open his laptop, punch a few keys, and see how his team did defensively in other games when the same two players were on the court together. He’s able to do this because teams are increasingly turning to software that dissects plays, follows every pass and shot and tracks each player’s part in every possession.

Not surprisingly, it is people in Operations Research that come to the rescue. Wayne Winston is best known for the textbooks he has published on a range of operations research-related topics. But he also has been working with NBA teams on the issue of teamwork: Continue reading “More OR and Sports”