Third Scottish Constraints Meeting
Friday 2nd June
Department of Computing Science
University of Aberdeen
Organiser: Ken Brown
Report
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.
General
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.
Attendees
- Nicos Angelopolous, University of Aberdeen
- Ines Arana, Robert Gordon University
- Ken Brown, University of Aberdeen
- Stuart Chalmers, University of Aberdeen
- David Fowler, University of Aberdeen
- Ian Gent, University of St. Andrews
- Nick Gotts, Macaulay Land Use Research Institute
- Kit Hui, University of Aberdeen
- Tim Norman, University of Aberdeen
- Alun Preece, University of Aberdeen
- Patrick Prosser, University of Glasgow
- Peter Ross, University of Edinburgh
- Cristiano Saturni, University of Aberdeen
- Josh Singer, University of Edinburgh
- Martin Swain, University of Aberdeen
- Toby Walsh, University of York
- Mark Winter, Macaulay Land Use Research Institute