Four long (30 minute) presentations were given. The first, by Barbara Smith, was on the modelling of a permutation problem. A number of different representations were given for an abstract permutation problem (Langford's problem) and these were compared. In particular a dual model was presented with two sets of variables. One set corresponded to the decision variables, the other to the values. Between the variables were constraints peculiar to problem and more general constraints for permutation problems, i.e. the channelling and all-different constraints.
The second presentation, by Patrick Prosser, was on the stable marriage problem. This followed on logically from the first presentation, as this was yet another instance of a permutation problem, using a similar representation to that above. The behaviour of the constraint programming encoding of this problem was compared to that of the Gale Shapley algorithm.
There were two long and one short presentation after lunch. Toby Walsh presented what was essentially a research proposal for stochastic constraint programming, where some variables have domains with uncertain values. Ian Gent's talk was on symmetry breaking within search, and presented results on a problem with a high number of symmetries (more than 1000). The symmetry breaking code resulted in a 40 fold improvement in run time.
After the coffee break, Toby Walsh gave a short (10 minute) presentation on patterns within constraint programs. Just as the software engineering community has recognised the importance of the patterns that emerge in computer programs, it was proposed that the same might be true in constraint programs. However, these patterns would be to do with the encoding and representation of the problem, the search algorithms that are used, and the appropriate variable and value ordering heuristics. Again, this was a presentation of proposed work.
In summary, of the above presentations one was of completed work (Barbara Smith's), one on ongoing work (Patrick Prosser's), new results (by Ian Gent) and two proposals for new work (Toby Walsh).
There were then 7 micro-presentations. The micro-presentation is a feature introduced at the previous ScotNet meeting. People are invited to give a presentation, but are limited to a single OHP transparency and 5 minutes. The first up was Rob Irving, who presented the stable marriage problem with incomplete lists and ties. This was presented as a challenge for constraint programming. David Manlove followed on, introducing us to the concept of super stability and how we might test for this. Richard Cooper gave a presentation on a unified configurable model of data management, and how constraints are a central feature of this. Ken Brown told us of his ongoing work in dynamic constraint satisfaction and any-time algorithms for constrained optimisation problems. Josh Singer presented the main outline of his soon to be completed PhD thesis, and proposed some future work. Similarly, Ian Miguel gave us a summary of part of his PhD research on plan synthesis. Isla Ross talked about minimal unsolvable subinstance within constraint satisfaction problems.
Throughout the day we were reminded that it was Richard Cooper's and Patrick Prosser's birthday. This was considered quite appropriate as the founding meeting for ConsNet at Royal Holloway also had two birthday speakers: Peter van Beek and Bernhard Nebel.
The next meeting will be held in Strathclyde University, hopefully before or just after the Christmas break.
| 11:00 - 11:15 | Welcome & coffee |
| 11:15 - 11:45 | Barbara Smith: Modelling of a permutation problem |
| 11:45 - 12:15 | Patrick Prosser: Constraint programming and the stable marriage problem |
| 12:15 - 2:30 | Lunch: DiMaggio's, Ruthven Lane |
| 2:30 - 3:00 | Toby Walsh: Uncertainty in Constraint Satisfaction |
| 3:00 - 3:30 | Ian Gent: Symmetries in Constraint Programming |
| 3:30 - 3:45 | Coffee |
| 3:45 - 3:55 | Toby Walsh: Constraint Patterns |
| 4:00 - 4:30 | Micro presentations (all attendees) |
| 4:30 - 4:45 | Conclusion, next meeting |