☰ Declarative Programming in Machine Learning

Constraints Satisfaction Programming

Requirements

Grading scheme

Code of conduct

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

The class meetings start with the lecture in week 1.

WeekLecturesSeminars
1Class Administration, Organisation, Introduction
2 Logic Prog in Problems Solving & Recap on Graph Theory
Introduction & Overview & Fundamental concepts (ch 1,2,3)
Problem reduction (ch 4)
Basic search & Search orders (ch 5,6)
Problem specific features & Stochastic search & Optimisation (ch 7,8,10)
 
3
4
5
6Report 1
7
8
9
10Report 2
11
12
14

4. Online resources

5. Students deliverables

First report

Second report

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

© Prof.dr. Horia F. Pop