Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MID0024	Constraints Satisfaction Programming	

Semester	Hours: C+S+L+P	Category	Status	
4	2+0+1+0	specialty	optional	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
POP Horia Florin	Ph.D.	Prof.	Programming  Languages and Methods	*			

III. Course objectives
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.	

IV. Course contents
1. Introduction 
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 
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 
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 
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 
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 
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 
8.1 Introduction 
8.2 Hill-climbing 
8.3 Connectionist Approach 
9. Solution synthesis (*)
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 (*)
10.1 Introduction 
10.2 The Constraint Satisfaction Optimization Problem 
10.3 The Partial Constraint Satisfaction Problem 	

V. Bibliography
[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
[4] Constraint programming: introduction, http://www.aiai.ed.ac.uk/links/constr.html 	

VI. Thematic of didactic activities per weeks
Schedule of lectures
Week 1: Administrivia. Introduction
Week 2: Concepts of graphs theory 
Week 3: Overview of CSP
Week 4: Fundamental concepts
Week 5, 6: Problem reduction
Week 7. 8: Basic search strategies
Week 9, 10: Search orders in CSP
Week 10, 11: Exploitation of problem specific features
Week 12: Stochastic search methods
Week 13: Solution synthesis, Optimization in CSP
Week 14: Written test (all lectures)

Schedule of labs
Weeks 1/2, 3/4: Lab theme 1: Solve typical CSP problems in C++/Java
Weeks 5/6, 7/8: Lab theme 2: Implement CSP methods from chapters 3, 4 and use them on CSP problems
Weeks 9/10, 11/12: Lab theme 3: Implement CSP methods from chapters 5, 6 and use them on CSP problems
Weeks 13/14: Lab theme 4: Use constraint libraries to solve CSP problems

Semester Project
A semester project is required, to demonstrate a good understanding of CSP techniques in modeling and solving problems from the real world or of other scientific nature.	

VII. Didactic methods used
Expositions: description, explanation, class lectures, dialog-based lectures, lectures with demonstrations, introductive lectures, current lectures, synthesis lectures. 
Conversations: debate, dialog, introductive conversations, conversations for knowledge consolidation, conversations to systematize and synthesize knowledge 
Use of problems: use of problem questions, problems and problem situations. 
Discovery: directed and independent rediscovery, creative discovery, inductive discovery, deductive discovery, discovery by documenting, experimental discovery. 
Other methods: case study; cooperation, simulation, brainstorming, individual study, exercise, homework study.		

VIII. 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 penalized. 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	

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

	Dean,							Chair head,

	Date,							Course responsible,
	October 1, 2010					Prof. POP Horia Florin, Ph.D.