M.Sc. Thesis by Jeppe Nejsum Madsen
A constraint satisfaction problem involves the assignment of values to variables subject to a set of constraints. A large variety of problems in artificial intelligence and other areas of computer science can be viewed as a special case of the constraint satisfaction problem.
In many applications, one example being product configuration, user interaction is required to find a solution. The topic of this thesis is algorithmic methods for solving constraint satisfaction problems interactively.
A number of fundamental operations, which form the core of an interactive constraint solver, are identified and described formally. The decision version of the constraint satisfaction problem is NP-complete, so a method of offline compilation is proposed to circumvent this intractability and achieve short response times for these fundamental operations.
Based on existing methods for tree clustering and solution synthesis, a compilation method is devised. A new method, based on uniform acyclic constraint networks, is proposed which results in improved response time of the fundamental operations.
All methods and algorithms have been implemented and their performance evaluated
on real-life problem instances arising from the area of product configuration.
The performance study shows that the new methods presented can achieve response
times suitable for interactive processing for most of the problem instances.
The following files are available for download: