☰ Declarative Programming in Machine Learning (2024-2025)

Constraints Satisfaction Programming

Requirements

Grading scheme

Code of conduct

On final exam

1. Instructor

Prof.dr. Horia F. Pop, Email:

2. Preliminaries

This is a research oriented class. Your grade will be based on your own work and on your understanding of it, including your ability to explain, defend and analyse your work and your results.

3. Schedule of activities

• Lecture
  • Tuesday 16-18, C335
• Seminar
  • Tuesday, week 2/2, 18-20, C512

4. Online resources

• Lecture notes and other resources are available on the UBB Sharepoint platform.
• Please understand that the lecture notes will be posted here AFTER the class.

5. Students deliverables

First report

• deadline for setting the time slot = week 5, Monday 00:00 hours
• the time slot is scheduled via email on a first come first served basis, according to available slots
• the written report is send via this link as an archive including all necessary files
• if the upload system does not allow a ZIP archive, the file will be renamed as filename.ZIP.PDF and uploaded as such
• class presentations = week 7-10
• the reports presentation schedule is published and updated on the UBB Sharepoint platform

Second report

• deadline for setting the time slot = week 9, Monday 00:00 hours
• the time slot is scheduled via email on a first come first served basis, according to available slots
• the written report is send via this link as an archive including all necessary files
• if the upload system does not allow a ZIP archive, the file will be renamed as filename.ZIP.PDF and uploaded as such
• class presentations = weeks 11-14
• the reports presentation schedule is published and updated on the UBB Sharepoint platform

6. Detailed contents

1. Administrivia (1 hour)
2. Graphs related concepts (2 hours)
3. Logic Programming in Problems Solving (2 hours)
4. Introduction (1 hour) [1, Ch. 1]
   1. What is a constraint satisfaction problem?
   2. Formal Definition of the CSP
   3. Constraint Representation and Binary CSPs
   4. Examples and Applications of CSPs
   5. Constraint Programming
5. CSP solving - An overview (2 hours) [1, Ch. 2]
   1. Problem Reduction
   2. Searching For Solution Tuples
   3. Solution Synthesis
   4. Characteristics of Individual CSPs
6. Fundamental concepts in the CSP (3 hours) [1, Ch. 3]
   1. Concepts Concerning Satisfiability and Consistency
   2. Relating Consistency to Satisfiability
   3. (i, j)-consistency
   4. Redundancy of Constraints
7. Problem reduction (4 hours) [1, Ch. 4]
   1. Node and Arc-consistency Achieving Algorithms
   2. Path-consistency Achievement Algorithms
   3. Post-conditions of PC Algorithms
   4. Algorithm for Achieving k-consistency
   5. Adaptive-consistency
8. Basic search strategies for solving CSPs (4 hours) [1, Ch. 5]
   1. General Search Strategies
   2. Lookahead Strategies
   3. Gather-information-while-searching Strategies
   4. Hybrid Algorithms and Truth Maintenance
   5. Comparison of Algorithms
9. Search orders in CSPs (2 hours) [1, Ch. 6]
   1. Ordering of Variables in Searching
   2. Ordering of Values in Searching
   3. Ordering of Inferences in Searching
10. Exploitation of problem-specific features (2 hours) [1, Ch. 7]
    1. Problem Decomposition
    2. Recognition and Searching in k-trees
    3. Problem Reduction by Removing Redundant Constraints
    4. Cycle-cutsets, Stable Sets and Pseudo-Tree-Search
    5. CSPs with Binary Numerical Constraints
11. Stochastic search methods for CSPs (2 hours) [1, Ch. 8]
    1. Hill-climbing
    2. Connectionist Approach
12. Optimization in CSPs (2 hours) [1, Ch. 10]
    1. The Constraint Satisfaction Optimization Problem
    2. The Partial Constraint Satisfaction Problem

7. Bibliography

1. Edward P.K. Tsang, Foundations of Constraint Satisfaction, Academic Press, London and San Diego, 1993, ISBN 0-12-701610-4
2. Roman Bartak, On-line Guide to Constraint Programming, Charles University, Prague, Website
3. Grzegorz Kondrak, A Theoretical Evaluation of Selected Backtracking Algorithms, M.Sc. Thesis, University of Alberta, Edmonton, 1994, PDF file
4. Constraint programming: introduction, Website

Optional bibliography

1. Some challenges for constraint programming, Website (ACM Computing Surveys)
2. Visual constraint programming tool: Oz explorer, Website
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, pp205-211.
6. Partial constraint satisfaction, EC Freuder and RJ Wallace, AI, vol 58, 1992, pp 21-70. (special issue on constraint based reasoning).

8. Constraint libraries

• Easy CSP (Java library, free software), author Victor Cordis, UBB 2010 graduate
• Choco (Java library, free software)
• Gecode (C++ library, free software)
• Disolver (C++ library, proprietary)
• ILOG Solver (C++ library, proprietary)
• Koalog Constraint Solver (Java library, proprietary)
• Minion (C++ program, GPL)
• Comet (C style language for constraint programming, GPL)
• Mozart (Oz based, Free software)

© Prof.dr. Horia F. Pop