☰ Declarative Programming in Machine Learning (2024-2025)

Constraints Satisfaction Programming

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

Week	Lectures	Seminars
1	Administrivia
2	Logic Programming in Problems Solving Recap on Graph Theory
3	Introduction (ch 1) Overview of CSP (ch 2) Fundamental concepts (ch 3)
4	Problem reduction (ch 4)
5	Basic search strategies (ch 5) Search orders in CSP (ch 6)
6	Exploitation of problem specific features (ch 7) Stochastic search methods (ch 8) Optimization in CSP (ch 10)
7	Report 1	Report 1
8
9
10
11	Report 2	Report 2
12
13
14

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

Administrivia (1 hour)
Graphs related concepts (2 hours)
Logic Programming in Problems Solving (2 hours)
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
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
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
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
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
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
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
Stochastic search methods for CSPs (2 hours) [1, Ch. 8]
1. Hill-climbing
2. Connectionist Approach
Optimization in CSPs (2 hours) [1, Ch. 10]
1. The Constraint Satisfaction Optimization Problem
2. The Partial Constraint Satisfaction Problem

7. Bibliography

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

Optional bibliography

Some challenges for constraint programming, Website (ACM Computing Surveys)
Visual constraint programming tool: Oz explorer, Website
Algorithms for constraint satisfaction problems: A survey AI magazine, 1992, 13/1
Constraint satisfaction algorithms, BA Nadel, Computational Intelligence, Vol 5, 1989, pp 188-224.
Constraint satisfaction, AK Mackworth, Encyclopaedia of AI, Volume I, Stuart C Shapiro (ed), John Wiley and Sons, 1987, pp205-211.
Partial constraint satisfaction, EC Freuder and RJ Wallace, AI, vol 58, 1992, pp 21-70. (special issue on constraint based reasoning).