Month: May 2006

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”

Future of Constraint Programming

I find constraint programming to be an interesting field. A lot of the work in the area is really operations research (in my view): problems are modelled within a particular structure, and solutions are then found to the models. Most constraint programmers don’t consider themselves in OR, preferring to stay within the computer science world.

As a maturing field, it is not surprising that people in the field are now thinking about where the field is going, and what are the important questions (early in a field, I think people just do things!). There is going to be a workshop at this fall’s Constraint Programming conference. Here is the announcement

CP workshop on “the next 10 years of Constraint Programming”
==============================

We are pleased to announce that the Twelfth International Conference on Principles and Practice of Constraint Programming (CP06: http://www.sciences.univ-nantes.fr/cp06/) will include a special workshop on “the next 10 years of constraint programming”. The goal of this event will be to discuss the following questions:- What are the achievements of the field during the last 10 years?
– What is the perception of CP by users and other research communities?
– What are the research directions for CP in 2006?
– What role can CP play within computer science research and industry?
– What are the strategic research directions likely to be in 2016?
– What application domains are of interest to us in the future?

The workshop will include a panel of invited speakers from both academia and industry, and will also leave ample time for public discussions. The content of the workshop is largely to be defined and all researchers and practitioners interested in the future of Constraint Programming are invited to share their comments and propose discussion threads through the Yahoo! group of the Association for Constraint Programming: http://groups.yahoo.com/group/constraints/


Lucas Bordeaux
Barry O’Sullivan
Pascal Van Hentenryck

It will be interesting to see what they come up with.

More Operations Research in Business Week

Business Week coverOperations research is on a roll. The May 29th issue of Business Week has a cover story on the use of simulation and other methods to take the guesswork out of medical care. The key person for this article is Dr. David Eddy, described as a “heart surgeon turned mathemetician and health-care economist”, who was the 1980 recipient of the INFORMS-awarded Lanchester Prize. This prize is given for the “awarded for the best contribution to operations research and the management sciences published in English”. The award citation to Dr. Eddy included the following:

The rapidly growing cost of health care is of great concern to many citizens. Our health care system and policies in the U.S. might be described as the product of many good intentions but only modest analysis. This year’s Lanchester Prize goes to a book: Screening for Cancer: Theory, Analysis and Design by Dr. David M. Eddy, published by Prentice-Hall, Inc., Englewood Cliffs, 1980, which is a significant and welcome contribution to the quality of analysis in the health care field.

In its general form, the problem studied by Dr. Eddy is an old one in the operations research literature, namely, the monitoring and repair of a probabilistic deteriorating system. This dry sounding phrase takes on special meaning when the system is the human body and the deterioration is cancer.

The principal concerns of Dr. Eddy’s work are: which screening tests should be used and with what frequency for various classes of people. The notable feature of Dr. Eddy’s analysis is the thoroughness with which account is taken of such things as the cost of administering a test, the cost of processing false positives from a test, the fact that a test may cause the disease it is attempting to detect, the fact that more frequent testing detects disease earlier and gives the illusion of prolonged life expectancy even in the absence of a cure, and the fact that if the disease may sometimes go into remission naturally, then more frequent testing gives the illusion of a higher cure rate. Also, Dr. Eddy’s analysis was one of the first to make the useful distinction between modeling the state of a patient as his cancer screening history to date, which is observable, as opposed to the state of the disease, which is only partially observable.

The style of Dr. Eddy’s work is in the best operations research tradition of interdisciplinary analysis. The remarkable feature is that in this case the varied disciplines are all embodied in one person.

From the Business Week article, it seems that 26 years later, Dr. Eddy continues this path:

Continue reading “More Operations Research in Business Week”

Google Scholar and OR

One issue in faculty reviews is trying to determine the effect the research of a faculty member is having. For that, we do things like get outside letters, read papers, and so on. In the past, we also checked things like the Science Citation Index for counts on how often a paper is referenced. Recently, Google Scholar has taken on that role, for better or worse. It is better than SCI in the sense it lists very recent references that may not be in the published literature yet. It also is very wide ranging, catching things SCI doesn’t catch. Of course, it may also catch garbage, but that is the tradeoff. It also undercounts older papers that don’t have as strong an online presence.

One surrogate for “effect” is number of references in Google Scholar. I thought it would be interesting to see the OR work with the most references. Here are a few I found:

  • Dantzig (Linear Programming and Extensions): 1384
  • Garey and Johnson (Computers and Intractibility): 12334 plus other editions
  • Nemhauser and Wolsey (Integer Programming): 2199
  • Rockafellar (Convex Analysis): 4470
  • Schrijver (Theory of Integer and Linear Programming): 1866
  • Papadimitriou and Steiglitz (Combinatorial Optimization): 2364
  • Ahuja, Magnanti, and Orlin (Network Flows): 2037
  • Karmarkar (16th ACM Polynomial Time Linear Programming): 1329
  • Trick (hah!, Cliques, Coloring and Satisfiability): 126

So I have Papadimitriou and Steiglitz (deciding Rockafellar and Garey and Johnson are not “really” OR) as the most referenced book and Karmarkar as the most referenced paper. Anybody beat that?

Teaching Operations Research and Management Science

One of the ironies of academic life is that a large portion of it is taken over by an aspect that few of us have formal training in: teaching! The average high school teacher has a firmer foundation on pedagogic theory than almost any university professor. This is particularly problematic in operations research since the education most of us received (research oriented knowledge/teaching methods) is far removed from what we are expected to teach (undergraduate/MBA “practical” instruction). So many of us spend a year or two mimicking our previous education (“Here’s a great proof for you!”) rather than teaching students what they really should know. And given my clearly enthusiastic belief in the usefulness and relevance of operations research, that is really a shame: instead of inspiring students, we turn them against our field.

INFORMS has had its Teaching Management Science Conference over the past few years. This year’s version will be in San Francisco in July. The program looks to have a good mix of theory (how do students learn) and practice (successful examples from top faculty). You can even stay in dorms to get the full “Live life as a student” aspect.

Operations Research and Lego

Lego symbolThe blog Deviant Abstraction points out that Lego’s (you know: building blocks that can be put into lots of different shapes) new Lego Factory has an interesting OR problem to solve: how can they put together packets of pieces so as to minimize waste when customers can order from more than 500,000 different pieces? Of course, OR needs to be used here. If anyone has a technical reference, I would love to see it! As someone who has a little more Lego than any mid-40s guy should have (and my two year old is not allowed to touch it! He can get his own!), the combining of two of my passions is appealing.

Optimize magazine and Operational Excellence

Optimize is a 70,000 circulation magazine aimed at CIOs and CTOs. The topic of the May, 2006 issue is “Operational Excellence”, and it contains a host of articles about operations research, one done by yours truly. My article, entitled “CIO as Business Predictor” tries to talk about the role uncertainty plays in decision making and how OR approaches can help address these issues. The sidebars in the article describe the finalists in this year’s Edelman Competition.

A second article, entitled “Bringing Unity to Cardinal Health”, described how IT and operational excellence go hand-in-hand. There is a sidebar of an interview with Irv Lustig from ILOG on the how IT and OR interact.

The Editor’s Note to the issue also talks about OR quite a bit, and says some very nice things about me! I think I will get it framed and send to my mother.

Between this and the coverage by Stephen Baker from Business Week, OR is getting noticed quite a bit these days in the more mainstream press.

Stephen Baker on Operations Research

Stephen Baker, the author of the Business Week cover story on how Math Will Rock Your World, is rapidly becoming a highly visible writer about Operations Research. His May 4 blog entry, entitled “Why journalists don’t cover how things work” had some comments on his experience at the INFORMS Practice Conference:

At the O.R. conference (the association is called INFORMS), there were far too many interesting presentations for one person to cover them all. The people behind operations at Intel, IBM, the Army, Ford and plenty of others provided inside looks. Beat reporters of those companies could have feasted on these lectures. But they weren’t there.

Why? The press covers news, stocks, companies and personalities. But try pitching a cover story on operations. People think it’s … boring. Trouble is, if we want to know where things are going, we have to understand how they work. And when the process is transformative, as it often is in OR, there’s nothing boring about it. The winner of the annual Informs Franz Edelman award, by the way, was the Warner Robins Air Logistics Center. They overhauled the maintenance of jumbo C-5 transport aircraft, reducing repair time by 33%. This means that these monsters, which cost taxpayers $2.3 billion each, spend more time in the air and less time in the shop.

If Stephen keeps this up, we may see lots more press coverage.