MSc by Research in Computer Science

Constraints Strand

Aims

Constraint satisfaction is a major discipline in modern artificial intelligence. However, it is too advanced or specialised to be included in an undergraduate programme.

Clearly it is necessary for those attempting a project in constraint satisfaction to have a strong background in both the theoretical and practical aspects of the subject. This course aims to give the student sufficient understanding of, and practice with, constraint problems, and to successfully choose and deliver a good research project in the area.

Objectives

At the end of this course the student will have an understanding of constraint satisfaction as a paradigm for general problem solving and will be able to formulate a problem as a Constraint Satisfaction Problem.

Students will understand some of the standard algorithms for pre-processing and solving constraint problems.

Students will understand the essential mathematical theory underpinning the subject - both as it relates to the underlying graphs of problems, and how it relates to the constraint structure.

Students will have an overview of the key current research areas.

The course structure

The course will consist of four parts.

1. What are constraints? This will begin with basic definitions and introduce the student to the problems associated with constraint formulation. Through practical examples the student will see alternative models and why they are important. The section will include a short introduction to the area of complexity of constraint problems.

Topics: Problems seen as assignments to constrained variables. A general framework. An alternative formulation. The problem of modelling. Different models for the same problems. Complexity. Model equivalence.

2. Consistency Techniques. In this section students will be shown how pre-processing can lead to simplified but equivalent problems. Different kinds of problem reduction will be covered. The section will end with an in depth look at some of the best consistency algorithms in use today.

   Topics: Pre-processing to reduce problems. Arc consistency. Path consistency. Strong k-consistency. Some consistency algorithms.

3. Basic Algorithms. In this section all basic types of constraint solving algorithms will be covered. This will include traditional methods as well as recent research developments.

   Topics: General search strategies. Chronological backtracking. Forward checking (lookahead). Dependency directed backtracking. Backjumping/backmarking. Dynamic search ordering. Incomplete search techniques.

4. Underlying theory. Here students will cover essential mathematical theory that underpins constraint satisfaction. This will begin with notions from graph theory and relational algebra. Students will apply this knowledge to constraint problem decomposition, complexity bounding, and solution techniques.

   Topics: Acyclic graphs - trees. Tree width. Minimal cut-sets. Local to global consistency. The relational/graph separation. Problem decomposition. Some tractable constraint classes.

Supervisor

Dave Cohen

References

Mostly students will be referring to the book:
Foundations of Constraint Satisfaction, Edward Tsang, Academic Press 1993

However, research papers will be covered as and when they are appropriate.
Back to MSc by Research in Computer Science Home Page