Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate
SUBJECT
| MID0024 | Constraints Satisfaction Programming |
| Teaching Staff in Charge |
Prof. POP Horia Florin, Ph.D., hfpop cs.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-3) 2. (Theme 2) Implement and test the methods in lectures 3-5 and use these functions to approach the problems at theme 1 (lab 4-6) 3. (Theme 3) Implement and test the methods in lectures 6-9 and use these functions to approach the problems at theme 1 (lab 7-9) 4. (Theme 4) Install and test CSP libraries in C++ and Java (lab 10-11) 5. (Theme 5) Solve some typical CSP problems using the libraries installed at theme 4 (lab 12-14) |
| 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. |
| Links: | Syllabus for all subjects Romanian version for this subject Rtf format for this subject |