Constraint Programming – Mike Trick's Operations Research Blog

Constraint Programming Makes the Big Time

The current PhD (Piled Higher and Deeper) comic (a comic written around the lives of doctoral and postdoc students: I fear I see too much of Dr. Smith in me!) revolves around Constraint Programming as applied to wedding planning. Karin Petrie, a well known constraint programmer, had lunch with the author of PhD, and I expect this is not a coincidence.

Netherlands Railway Edelman summary

I just got out of the “reprise” of the winning Edelman prize work by Netherlands Railways, and it was very, very good.

If you have been to the Netherlands, they have a very nice way of handling their trains: every route repeats every hour. So if you want to go from Utrecht to Amsterdam, there are trains at 13, 25, 43 and 55 minutes after the hour, every hour. Of course, the size of the train changes depending on the expected demand.

The Dutch have had the same schedule since 1970, but it was time for a change. Demand has doubled in that period, and there was little opportunity to increase the infrastructure. So could a better schedule reduce costs and improve service? Of course, or it wouldn’t be an Edelman Prize winner!

There were three pieces to the system: the timetabler, the crew assignment system, and the rolling stock assignment system. The timetabler was very interesting. You can formulate the problem as a mixed-integer program, but the cyclic nature of the hourly schedule requires the use of “mod” constraints. They tried MIP for a while (and even called in the big gun Lex Schrijver to look at it: I saw a talk by Lex a decade or more ago on work he did with Netherlands Railway on purchasing rail cars that is still one of the nicest applications talks I have ever seen), but eventually went over to constraint programming. From the talk, it appears they used constraint programming primarily to find a feasible solution, and then did some local improvements, but I will have to wait for the paper to be sure what is being done.

The other problems were solved with specialized integer programming methods.

The best part of the talk was their discussion of the implementation, which is where the models really came through. The plan was to have an important length of track doubled to coincide with the new schedule. That doubling didn’t happen, so they had to reschedule the crew essentially at the last minute.

The results have been really impressive. Crew costs are down 4% and rolling stock usage is down 6%, combining for an annual benefit of $75 million. As is not uncommon in OR projects, the system is both cheaper and works better. Punctuality is at an all-time high, and customer satisfaction is similarly improved. The increase in punctuality allowed them to increase fares by an additional 2%, for further profits of $30 million. Other than the fare increase, this looks like win-win: better service, more convenient times, cheaper operating costs.

At the end there was a nice video clip of the Minister of Transport saying how important OR is.

A worthy Edelman winner!

Call for Short Papers, CP-AI-OR 2008

I am co-program chair for CP-AI-OR 2008 to be held in May in Paris. This year, we decided to allow “short papers” primarily to encourage presentation of preliminary work or work that might have appeared in another outlet but would still be of interest to the CP-AI/OR community. If you aren’t familiar with CP-AI/OR, it is a small (roughly 100 person) conference that brings together people in constraint programming and operations research to discuss issues in common in the two field (I actually put constraint programming as part of operations research, but most constraint programmers don’t agree with me).

The deadline for short papers is February 15. You can check out more details at the conference web site.

ISI and Conferences

ISI from Thompson Scientific might be seen as just another scientific article indexing service, just like Google Scholar, Citeseer and many others. But it has a much stronger effect: many universities only “count” ISI-indexed publications. In mainstream operations research, this doesn’t have a very strong effect. Most well-known OR journals are ISI-indexed, and those that are not strive greatly for such indexing. But in some of our newer fields, particularly those related to computer science, this is much more of an issue. In constraint programming, conferences are key outlets for research, particularly such conferences as CP and CP/AI-OR. Both of these conference publish their papers in Springer’s Lecture Notes in Computer Science, which up until recently was ISI-indexed.

The ISI people have recently dropped LNCS and other series from their main ISI-indexing, and created a “conference” version of ISI-indexing. For some, this can have a very strong effect on promotion and tenure.

I have somewhat mixed feelings about this. At one level, I am worried that the ISI-“page count” available for some of our fields has decreased greatly. This will make it harder for some of our subfields to grow and expand. On the other hand, conference volumes are just part of the proliferation of research outlets, and not ISI-indexing them seems appropriate given the sometimes quick level of review that some conferences provide. It is certainly true that the conferences provide reasonably thorough reviews and the rejection rate is high (70% or more rejected), but this still seems different than journals. Perhaps it is just me: as a member of a conference committee, I feel it is my responsibility to review papers somewhat farther from my core interests than I would for journal reviews. As such, I can’t provide the same insights for conferences that I do for journals.

Much of OR doesn’t have this problem. Most OR conferences are “free-for-alls” with no veneer of reviewing. This makes for large conferences of highly-variable quality. It is great for talking about not-fully-formed ideas, or interesting but not publishable results. I wonder if some of the competitive conferences will change in flavor now that the “carrot” of an ISI-indexed paper is not offered. At the very least, people should be working harder to follow up the conference with a journal publication, which seems a good outcome.

Getting cheaper boats and ships

I am in Providence attending this year’s Constraint Programming conference. I’m on the executive and we have developed new bylaws, so instead of listening to all the talks, I am involved in discussions on the minutia of quorums and transition rules. Still, there is some time for the conference itself.

I just saw a terrific talk by Matt Ginsberg of the University of Oregon and On Time Systems, a firm specializing in scheduling optimization. One of the big things they do is shipyard optimization, and he described putting together a system for better scheduling the production of navy submarines (which are boats) and carriers (which are ships). While traditional scheduling involves trying to minimize the amount of time it takes to build something, this sort of scheduling is about minimizing costs (or so he thought). So his firm put together a nice system to minimize the cost of going through the tens of thousands of tasks that go into a boat or ship. If that was the end of the talk, it would have been a fine technical talk on an interesting topic. But he went further.

“Just because a schedule looks good doesn’t mean it is good” is a phrase I wish more people would use. Lots of schedules look good, but when you try to use them they fail for easy-to-see-in-retrospect reasons. One example of this is the highly optimized crew schedules used by airlines. Sure, they look good and they appear to save money, but they are fragile: disruptions can spread throughout the system. Matt brought up two important issues not covered by the “minimize cost” aspects of their schedules. The first is the brittleness seen in airline crew schedules: will delays in one task mess up more? The second is union buy-in. If the goal is to decrease costs, won’t unions naturally be against it?

The brittleness point is important. Indeed, a minimum cost schedule is brittle (though perhaps no more brittle than the schedule currently in place), though it saves about 10.4% on costs. But the methods Matt used can be adapted to make float (the amount any task can be delayed without affecting other tasks) into account. A task with too little float (perhaps just a few work shifts) is at risk of delaying the whole project. But you can combine these objectives: minimize cost and minimize number of tight tasks. It turns out that you can decrease the number of tight tasks by more than 90% (relative to the current schedule) and still save about 10.3% on costs (numbers approximate: I have to learn to take better notes!). So decreasing brittleness comes almost for free!

As for the unions, one fact about shipyards is that they often layoff and then rehire lots and lots of workers. The schedules Matt provides are much smoother in the way they use workers. Certainly far more workers would have consistent jobs under the schedules, and layoffs would not occur near as often.

Overall, the shipbuilders would save money, the unionized workers would have more consistent jobs, and the building process would be less susceptible to delays. What’s not to like?

Well, the firms building the ships are paid by the Navy on a cost-plus basis. The higher the cost, the higher the plus. So they have essentially no interest in saving our money. They like high costs! Next time you see your congressman or -woman, ask “What happened to the ARGOS project to improve ship-building operations? Wasn’t that supposed to save us a few billion dollars?”

While we wait for the companies to work more efficiently, On Time Systems has a scheduling game you can play.

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.

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.

Want to learn more about Constraint Programming?

Thom Frühwirth and Slim Abdennadher have a book called “Essentials of Constraint Programming”. Best of all, Thom has more than 400 powerpoint slides on his website to supplement the book.

Happenings in Cork

I have just returned from a site visit to the Cork Constraint Computation Centre (4C: it’s a pun, don’t you know) in Cork Ireland, where I am on the advisory board. Ireland is a country that seems to have its government investments set up well. A few years ago, they a identified Gene Freuder as someone they would like to attract and made him a very nice offer. Gene is one of the (or perhaps the main) founders in the area of constraint programming, and he has put together an extremely impressive lab. Lots of activity, both in fundamental research and in industrial outreach. The lab isn’t perfect (more OR!), but it is very, very good. If you are learning more about constraint programming, this lab’s site is a good place to start.