☰ Declarative Programming in Machine Learning (2023-2024)

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

WeekLecturesSeminars
1Administrivia, IntroductionNo physical classes.
Time allocated for
individual study
2Logic Programming in Problems Solving
Recap on Graph Theory
3Introduction (ch 1)
Overview of CSP (ch 2)
Fundamental concepts (ch 3)
4Problem reduction (ch 4)
5Basic search strategies (ch 5)
Search orders in CSP (ch 6)
6Using problem specific features (ch 7)
Stochastic search methods (ch 8)
Optimization in CSP (ch 10)
WeekClass presentations
7First report
8
9
10
11Second report
12
13
14

4. Online resources

Lecture notes and other resources are available on the UBB Sharepoint platform.

5. Students deliverables

First report

Second report

6. Course contents

  1. Administrivia (1 hour)
  2. Logic Programming in Problems Solving (2 hours)
  3. Graphs related concepts (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

© Prof.dr. Horia F. Pop