Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate

SUBJECT

Code
Subject
MID0024 Constraints Satisfaction Programming
Section
Semester
Hours: C+S+L
Category
Type
Computer Science - in English
4
2+0+1
speciality
optional
Information engineering - in English
4
2+0+1
complementary
optional
Teaching Staff in Charge
Prof. POP Horia Florin, Ph.D.,  hfpopcs.ubbcluj.ro
Aims
Many computational problems can be described in terms of restrictions imposed on possible solutions. Constraint Programming is a problem-solving technique that works by incorporating such restrictions into a programming environment. Constraint Programming draws on methods from artificial intelligence, logic programming, and operations research. It has been successfully applied in a number of fields such as scheduling, computational linguistics, and computational biology.

The aim of this course is to create an understanding of the fundamental concepts underlying constraint programming; to develop skills in modeling and solving combinatorial problems; to develop skills in taking advantage of strong algorithmic techniques. The course has both a theoretical component, oriented on the study of the domain and of the relevant issues, and a practical component, oriented on the study of different typical problems, systems, platforms and libraries for constraints programming.
Content
1. Introduction (lecture 1)
1.1 What is a constraint satisfaction problem?
1.2 Formal Definition of the CSP
1.3 Constraint Representation and Binary CSPs
1.4 Graph-related Concepts
1.5 Examples and Applications of CSPs
1.6 Constraint Programming

2. CSP solving - An overview (lecture 2)
2.1 Introduction
2.2 Problem Reduction
2.3 Searching For Solution Tuples
2.4 Solution Synthesis
2.5 Characteristics of Individual CSPs

3. Fundamental concepts in the CSP (lecture 3)
3.1 Introduction
3.2 Concepts Concerning Satisfiability and Consistency
3.3 Relating Consistency to Satisfiability
3.4 (i, j)-consistency
3.5 Redundancy of Constraints
3.6 More Graph-related Concepts

4. Problem reduction (lectures 4, 5)
4.1 Introduction
4.2 Node and Arc-consistency Achieving Algorithms
4.3 Path-consistency Achievement Algorithms
4.4 Post-conditions of PC Algorithms
4.5 Algorithm for Achieving k-consistency
4.6 Adaptive-consistency
4.7 Parallel/Distributed Consistency Achievement

5. Basic search strategies for solving CSPs (lectures 6, 7)
5.1 Introduction
5.2 General Search Strategies
5.3 Lookahead Strategies
5.4 Gather-information-while-searching Strategies
5.5 Hybrid Algorithms and Truth Maintenance
5.6 Comparison of Algorithms

6. Search orders in CSPs (lectures 8, 9)
6.1 Introduction
6.2 Ordering of Variables in Searching
6.3 Ordering of Values in Searching
6.4 Ordering of Inferences in Searching

7. Exploitation of problem-specific features (lectures 10, 11)
7.1 Introduction
7.2 Problem Decomposition
7.3 Recognition and Searching in k-trees
7.4 Problem Reduction by Removing Redundant Constraints
7.5 Cycle-cutsets, Stable Sets and Pseudo-Tree-Search
7.6 The Tree-clustering Method
7.7 j-width and Backtrack-bounded Search
7.8 CSPs with Binary Numerical Constraints

8. Stochastic search methods for CSPs (lecture 12)
8.1 Introduction
8.2 Hill-climbing
8.3 Connectionist Approach

9. Solution synthesis (lecture 13)
9.1 Introduction
9.2 Freuder@s Solution Synthesis Algorithm
9.3 Seidel@s Invasion Algorithm
9.4 The Essex Solution Synthesis Algorithms
9.5 When to Synthesize Solutions

10. Optimization in CSPs (lecture 13)
10.1 Introduction
10.2 The Constraint Satisfaction Optimization Problem
10.3 The Partial Constraint Satisfaction Problem

Graded paper (lecture 14)

Schedule of labs

1. (Theme 1) Solve some typical CSP problems in C++ or Java (lab 1-2)
2. (Theme 2) Implement and test the methods in lectures 3-5 and use these functions to approach the problems at theme 1 (lab 3-4)
3. (Theme 3) Implement and test the methods in lectures 6-9 and use these functions to approach the problems at theme 1 (lab 5-6)
4. (Theme 4) Install and test CSP libraries in C++ and Java, and solve some typical CSP problems using these libraries (lab 7)
References
[1] Edward P.K. Tsang, Foundations of Constraint Satisfaction, Academic Press, London and San Diego, 1993, ISBN 0-12-701610-4, http://cswww.essex.ac.uk/CSP/edward/FCS.html
[2] Roman Bartak, On-line Guide to Constraint Programming, http://ktiml.mff.cuni.cz/~bartak/constraints/
[3] Grzegorz Kondrak, A Theoretical Evaluation of Selected Backtracking Algorithms, University of Alberta, 1994

Optional references

[1] Constraint programming: introduction, http://www.aiai.ed.ac.uk/links/constr.html
[2] Some challenges for constraint programming http://www.clip.dia.fi.upm.es/~herme/con.html (ACM Computing Surveys)
[3] Visual constraint programming tool: Oz explorer http://citeseer.nj.nec.com/schulte97oz.html
[4] Algorithms for constraint satisfaction problems: A survey AI magazine, 1992, 13/1
[5] Constraint satisfaction algorithms, BA Nadel, Computational Intelligence, Vol 5, 1989, pp 188-224.
[6] Constraint satisfaction, AK Mackworth, Encyclopaedia of AI, Volume I, Stuart C Shapiro (ed), John Wiley and Sons, 1987, pp 205-211.
[7] Partial constraint satisfaction, EC Freuder and RJ Wallace, AI, vol 58, 1992, pp 21-70. (special issue on constraint based reasoning).
[8] Rina Dechter, Constraint Processing. Morgan Kaufmann Publishers, 2003.
[9] Kim Marriott and Peter J. Stuckey, Programming with Constraints. An Introduction. The MIT Press, 1998.
[10] Thom Frühwirth and Slim Abdennadher, Essentials of Constraint Programming. Springer-Verlag, 2003.
[11] Krzystof R. Apt, Principles of Constraint Programming. Cambridge University Press, 2003.
[12] Philippe Baptiste, Claude Le Pape and Wim Nuijten, Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Kluwer Academic Publishers, 2001.
Assessment
The final grade is determined as follows: 20% lab activity (grade A); 20% documentations, programs and projects developed; 60% the graded paper (grade F; during lecture 14).

All the official university regulations on students attendance of classes and cases of plagiarism and copied papers are valid.

Missing labs of at most 20% are accepted with no objections, but the delay in submission of the lab papers is penalised. The lab papers are submitted in written form at the end of the lab class when the submission is due.

Passing the final exam is conditioned by the grade F being at least 5.

The official webpage of the course is http://www.cs.ubbcluj.ro/~hfpop/csp
Links: Syllabus for all subjects
Romanian version for this subject
Rtf format for this subject