Third Scottish Constraints Meeting

Friday 2nd June
Department of Computing Science
University of Aberdeen

Organiser: Ken Brown


The third in the series of meetings in Scotland of researchers and practitioners interested in constraints was held in Aberdeen on Friday 2nd June, with 17 attendees from 7 different institutions. The meetings are funded by the UK Constraints Network (ConsNet), which in turn is funded by EPSRC. For 11 of the participants, this was their first involvement in a ConsNet meeting. The meetings are informal, and the intention is to discuss ideas, present ongoing research, examine industrial problems, and ask questions. There were a variety of talks at the meeting: 3 half-hour talks, 4 15-minute talks, and 7 micro presentations. The meeting announcement is available

30-minute talks

Josh Singer presented some recent results from his PhD research, explaining the hardness of problems in random 2+p-SAT. The "backbone" is the set of variables which are forced to take a certain value. If you remove a small number of clauses, and it results in a wide distribution of solutions, then the backbone is "fragile". In such problems, it means that there are a number of assignments which are almost satisfiable, but which are far away from proper solutions, and thus these problems are, on average, harder to solve.

Ken Brown presented his research on leaving variables unassigned in over-constrained problems, noting that this can be a more realistic solution in many resource allocation problems than violating some of the constraints. Decision problems (does there exisit a solution with less than M variables unassigned?) show the usual abrupt transitions between being satisfiable and unsatisfiable, which correspond with peaks in hardness, and the full set of hardness curves for the decision problems reproduces the otpimisation problem hardness curve.

Peter Ross presented some work on the use of GAs for solving timetabling problems, concentrating on the performance around the transition between satisfiable and unsatisfiable problems. The GA was unable to solve a certain class of underconstrained problems, but was able to solve more heavily constrained problems which included them as sub-cases.

15-minute talks

Mark Winter discussed his previous PhD work on debugging constraint problems using knowledge refinement techniques. This is useful in real world problems where the constraints have been derived through experience and judgement, but solutions do not correspond to known situations. Nick Gotts presented his earlier work on formalising a constraint language for the RCC8 spatial calculus, recently reported in the Constraints journal. Martin Swain discussed his constraint-based methods for predicting protein side-chain placements, which forms the basis of his PhD research. Alun Preece discussed his use of constraints in e-commerce, passing constraints as service requests. This led to a discussion of the proposed FIPA standard for exchanging constraints between agents. It was noted that this standard does not provide a rich language, but is a starting point, and future extensions will be possible.

Micro presentations

Following a suggestion by Patrick Prosser, all attendees not otherwise giving a presentation were invited to present one slide outlining future work. The topics discussed ranged from the use of the Choco language, through symmetry breaking and implied constraints, to optimisation, probabilistic formalisms and negotiation of constraints between agents. These presentations demonstrated that there is a wide variety of research being conducted, in both theory and practice, and gave a flavour of that research to all participants.


All participants are grateful to ConsNet and EPSRC for funding these meetings. We particularly welcome the way these meetings bring researchers together, allow research students to discuss their work, and introduce to the rest of the community both isolated researchers and those from other fields interested in the use of constraints.

Patrick Prosser volunteered to organise the next meeting, to be held in Glasgow in September. He promised to ensure that the lunch break would be long enough to allow plenty of discussion.