Date: 28 Feb 2003
From: jyrki@diku.dk
Subject: Oral defence of M.Sc. thesis

Oral defence of M.Sc.thesis: Methods for Interactive Constraint Satisfaction

Defender: Jeppe Nejsum Madsen
Censor: Kirsten Hjerrild Nielsen
Supervisor: Jyrki Katajainen

Time:  Wednesday, 12 March 2003, 13.15–15.00
Place: Aud 2 at HCØ

The defence will be held in Danish.

Abstract:

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 thesis text as well the source code for the implementation is
available at: 

http://www.diku.dk/~jyrki/PE-lab/Jeppe/