pat@cs.strath.ac.uk (Pat Prosser) (03/18/91)
Binary Constraint Satisfaction Problems Wanted
----------------------------------------------
I am performing comparative experiments across a range of tree search
algorithms for the binary constraint satisfaction (search) problem
(that is, find the 1st solution to a bcsp). I am looking for new
problems.
So far I have used the n-queens and the ZEBRA problem. I have not used
the "confused n-queens" as I believe it is inappropriate to the search problem.
For the ZEBRA problem I have been permuting the instantiation order to
produce different instances of the ZEBRA (potentially 25! instances).
This allows me to get measures of average performance, best, and worst case
performance. In addition, I can measure average performance against the
"width" of instantiation orderings (I am in the process of doing this).
I am looking for new problems. Ideally I would like some problem that
has the following properties:
(a) The constraint graph is not complete (such as n-queens)
(b) The problem is non-trivial (representative of a search problem)
(c) The instantiation order may be permuted to produce different
instances of that problem
(d) Constraints may be added/removed from the problem such that the
"density" of the constraint graph may be altered.
Can you suggest a problem that will meet (some of) the above
requirements?
Thanks in advance.
Patrick Prosser
Dept Comp Sci
University of Strathclyde
26 Richmond Street
Glasgow G1 1XH
Scotland