Instructor's slides

1. Course Syllabus, our 'contract.'
2. Instructor's slides: Administrative Note (PPT)
3. Instructor's slides: Guidelines for reports (PPT)
4. Instructor's slides:Constraint Processing 101 (PPT)
5. Slides by Shant and Rahul: Quick review of NP-Completeness.
6. Instructor's slides: Arc Consistency
7. Instructor's slides: Backtracking mechanims (PPT)
8. Instructor's slides: Evaluating & Comparing (Deterministic) BT Search Algorithms (PPT).
9. Instructor's slides: Theoretical Evaluation of BT Algorithms
10. Instructor's slides: Search Orders in CSPs (PPT)
11. Instructor's slides: A Consistency Algorithm for AllDifferent Constraint (PDF).
12. Instructor's slides: CSP & Relational DB
13. Instructor's slides: Path Consistency & Global Consistency Properties
14. Instructor's slides: More on Consistency Properties (PPT).
15. Instructor's slides: Local Search (PPT).
16. Instructor's slides: Advanced BT Search (PPT).
17. Instructor's slides: Least Commitement: Rationale and Strategy (PPT).
18. Instructor's slides: Lookahead Schemas (PPT)
19. Instructor's slides: Graphical Representations and Graphical Models (PPT)
20. Instructor's slides: Structure-Based Methods (PPT)
21. Instructor's slides: More on Consistecy Properties (PPT)
22. Instructor's slides: Modeling Examples (PPT)

Reading materials

Background, Overview

• Quick review of NP-Completeness (by Shant and Rahul).
• Constraint Programming: in Pursuit of the Holy Grail (PDF) Bartak
• Bartak's on-line guide: Introduction to CSPs
• Constraint Satisfaction (PDF) Rina Dechter. MIT Encyclopedia of the Cognitive Sciences 
• Constraint Satisfaction Problems, An Overview (PDF), Pedro Meseguer 
• Systematic Search Algorithms (Bartak's online notes)
• Heuristics and Stochastic Algorithms (Bartak's online notes)

Arc Consistency

• The complexity of some polynomial network consistency algorithms for constraint satisfaction problems Mackworth & Freuder, AIJ 1985 (only AC algorithms)
• Dechter Section 2.3
• Dechter Section 3.1--3.4, 3.5.1, 3.5.3 (and Chapter 3, entirely)
• Consistency Techniques (Bartak's online notes)
• Paper on AC4: Arc and Path Consistency Revisited (PDF) Mohr and Henderson, AIJ 1986
• Paper on AC3.1/2001: An Optimal Coarse-Grained Arc Consistency Algorithm (PDF) Bessiere et al., AIJ 2005
• A chapter about Consistency and Propagation: Constraint Propagation, Bessiere, Chapter 3, Handbook of Constraint Programming, 2006.

Search

• Hybrid algorithms for the constraint satisfaction problem (PDF) Prosser
• Chapter 5, Tsang

Phase transition

• Peter Cheeseman et al.: Where the Really Hard Problems Are (IJCAI 1991).

BT Search: Theory

• A Theorectical Evaluation of Selected Backtracking Algorithms, by Kondrak and van Beek (IJCAI 1995)
• Dechter, Chapters 5 and 6

Search Orders in CSPs

• Search Orders in CSPs, Chapter 6, Tsang 93
• Dechter: Sections: 5.1.1
• Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen ECAI 92

Evaluating & Comparing (Deterministic) BT Search Algorithms

• Dechter, Section 6.6
• Evaluating Constraint Processing Algorithms Dechter and Frost (AIPS 98 Workshop?)

An Efficient Propagator for the All-Diff Constraint

• Régin (AAAI 94): A Filtering Algorithm for Constraints of Differences in CSPs.
• Dechter, Section 3.5.1.
• An N^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs, Hopcroft and Karp, SIAM Journal on Computing, Vol 2, No 4, December 1973.
• Check the literature for recent developments on All-Diff constraint and other global constraints.

Path Consistency

• Dechter: Sections 3.1, 3.2, 3.3. (Read the entire Chapter 3.)
• The complexity of some polynomial network consistency algorithms for constraint satisfaction problems Mackworth & Freuder, AIJ 1985 (only AC algorithms)
• Consistency Techniques (Bartak's online notes)
• Path Consistency on Triangulated Constraint Graphs , Bliek and Haroud
• Networks of Constraints: Fundamental Properties and Application to Picture Processing, Montanari, Information Sciences, 1974
• Consistency in Networks of Relations, Mackworth, AIJ 1977.
• Constraint propagation with interval labels, Davis, AIJ 1987.

DB & CSP

• Section 1.3 of Dechter

Local Search

• Dechter, Chapter 7
• Heuristics and Stochastic Algorithms (Bartak's online notes)
• Section 4.3, Chapter 4, AI a Modern Approach (textbook), Russell & Norvig
• Stochastic Local Search (book), but Hoos and Stuelze
• The Breakout Method for Escaping From Local Minima Paul Morris, AAAI 1993.

Advanced BT-Search

• ECLiPSe: Chapter 12 on Search (Credit-Based Search)
• Limited Discrepancy Search, Harvey and Ginsberg, copyright IJCAI 1995
• Boosting Combinatorial Search Through Randomization, Gomes et al, AAAI 1998.
• Search in a Small World, Walsh, IJCAI 1999.

Structure-Based Techniques

• Dechter Sections: 2.1.3, 5.1.2, 10.1.1, 9.2, 4.4, 9.2.2.
• Tree Clustering Schemes for Constraint Processing, Dechter and Pearl, AIJ 1989
• Enhancement Schemes for Constraint Processing: Backjumping, Learning, and Cutset Decomposition (PDF not available yet), Dechter, AIJ 1990.
• Synthesizing constraint expressions, Freuder, JACM 1978
• A Sufficient Condition for Backtrack-Free Search, Freuder, JACM 1982
• A Sufficient Condition for Backtrack-Bounded Search, Freuder, JACM 1985

More Consistency Properties

• Neighborhood Inverse Consistency Preprocessing, Freuder and Elfe AAAI 96
• Optimal and Suboptimal Singleton Arc Consistency Algorithms, Bessière, Debruyne, IJCAI 2005