Handouts

Electronic Reserves

(UNL access only) Some papers are available from the Electronic Reserve of the Love Library. In particular, you can find three chapters of the book by Edward Tsang: Chapter 1, Chapter 6, Chapter 5 Part 1 and Part 2.

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: Backtracking mechanims (PPT)
  7. Instructor's slides: Lookahead Schemas (PPT)
  8. Instructor's slides: Overview: advanced solving techniques and research directions (PPT)
  9. Instructor's slides: Constraints & Relational Databases (PPT)
  10. Instructor's slides: A Theorectical Evaluation of Selected Backtracking Search (PPT)
  11. List of projects for 2009
  12. Instructor's slides: Evaluating (deterministic) BT Search Algorithms (PPT)
  13. Instructor's slides: Basic Consistency Methods (PPT)
  14. Instructor's slides: Consistency Algorithm for AllDifferent Constraints (PDF).
  15. Instructor's slides: Advanced Consistency Methods (PPT).
  16. Instructor's slides: Structure-Based Methods, An Introduction (PPT).
  17. Lecture of Professor Dechter: Chapter 4 of textbook.
  18. Instructor's slides: Search Orders in CSPs (PPT)
  19. Instructor's slides: Least Commitment: Rationale and Strategy.
  20. Instructor's slides: Advanced Backtrack Search (PPT slides).
  21. Instructor's slides: Local Search (PPT slides).
  22. Elena's slides on Symmetry in CSPs (PDF slides).
  23. Instructor's slides: Temporal Networks (PPT slides).

Required & Recommended Readings

  1. Constraint Programming: in Pursuit of the Holy Grail (POSTSCRIPT,PDF). Bartak
  2. Hybrid algorithms for the constraint satisfaction problem (PDF)--Prosser
  3. A Theorectical Evaluation of Selected Backtracking Algorithms, by Kondrak and van Beek (IJCAI 1995)
  4. Ordering Heuristics in CSPs (PDF), Chapter 6, Tsang
  5. Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen (ECAI 92)
  6. Where the Really Hard Problems Are Peter Cheeseman et al. (IJCAI 1991).
  7. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems--Mackworth/Freuder
  8. Régin (AAAI 94): `A Filtering Algorithm for Constraints of Differences in CSPs.
  9. For Credit-based search: ECLiPSe: Chapter 12 on Search
  10. Limited Discrepancy Search, Harvey and Ginsberg, copyright IJCAI 1995
  11. Boosting Combinatorial Search Through Randomization, Gomes et al, AAAI 1998.
  12. Search in a Small World, Walsh, IJCAI 1999.
  13. Exploiting symmetries within constraint satisfaction search, Meseguer and Torras, AIJ 2001
  14. Eliminatring Interchangeable Values in Constraint Satisfaction Problems, Freuder, AAAI 1991.

References for Project

  1. Maintaining Arc Consistency with Multiple Residues, Christophe Lecoutre et al., Constraint Programming Letters, 2008.
  2. A Study of Residual Supports in Arc Consistency, Christophe Lecoutre and Fred Hemery. Christophe Lecoutre and Fred Hemery, IJCAI 2007.
  3. Arc Consistency during Search, Likitvivatanavong et al., IJCAI 2007.
  4. An Optimal Coarse-Grained Arc Consistency Algorithm, Christian Bessière et a, Artif. Intell. 165(2): 165-185 (2005).

Last modified: Sun Dec 6 10:58:31 CST 2009