A Scottish Constraints Mini Workshop
Report of the Meeting

Thursday the 1st of March
Conference Room F121
17 Lilybank Gardens
Department of Computing Science
University of Glasgow

Organiser: Patrick Prosser

This was a small but significant meeting. Unfortunately Barbara Smith was unable to attend because there was a train crash that disabled the line, and bad weather just to make things worse. We were most fortunate to have Christian Bessiere (from LIRMM) present. Christian was external examiner for Kostas Stergiou's PhD the previous day, and Christian was kind enough to stay an extra day to attend our meeting.

The first presentation was by Ian Gent. Ian described how the APES group work, and in particular how footnotes are used. Essentially Ian was acting as a salesman, trying to sell on an idea that works well for the APES (the footnotes), even though it was stolen from Alan Bundy's group in Edinburgh. Muffy Calder was present for discussion, and she was so impressed ... she got Ian to set up a footnote system for her group the next day.

Ian MacDonald gave a presentation on dynamic symmetry breaking inside search and how this can exploit computer algebra. Evgeny Selensky then gave a short presentation on his investigations into vehicle routing and job shop scheduling problems, using constraint programming.

After lunch, Patrick Prosser and Ian Gent gave a presentation on constraint programming and the stable marriage problem. They presented recent results due to Rob Irving showing an optimal encoding using 0/1 variables. After a coffee break Christian then gave an overview of his current work. This covered 3 topics: compiling constraints networks; variable ordering heuristics that exploit neighbourhood information; a new arc-consistency algorithm AC2001. I particularly enjoyed the presentation of the AC2001 algorithm. The algorithm is simple and elegant.

There have been some immediate consequences as a result of the meeting. Further communications have taken place between Christian and Ian about how the encoding used for the stable marriage problem can be used as a model for encoding the AC2001 algorithm! That is, the AC2001 algorithm can be readily encoded using 0/1 variables. Expect to see some published results soon!

The meeting did not close so much as move on to the bar in the Western baths, then on to dinner at the Chandigarh restaurant.

All present would like to thank ConsNet for allowing us to hold such a productive meeting.