CCSCE421/821, Fall 2003: Foundations of Constraint Processing                                                             Main page of the course.  

---

• Kye Halsted: Scramble Squares Puzzle as a CSP.

• Constraint Processing:
• Kai Wen Ham: Tsang's textbook online
• Nurzhan Ustemirov: De Schreye's notes  (MSword notes, Power point slides1, slides2) from his Intro to AI Course
• AI resources:
• Ryan Lim: CMU AI Repository
• Latex resources
• Joel Gompert: Getting memory-efficient, pretty-looking, robust graphics with very fancy robust labels into LaTeX
• Ryan Lim: The not so short introduction to LaTex2x
• LISP resources
• Eric Moss: Screamer
• Eric Moss' personal help with Lisp
• Eric Moss:  There is a new Common Lisp implementation on the market (beta copy at this point).  It's supposedly good for multiprocessor systems that need multi-threaded apps using real OS threads.

• Chris Hammack: a really cool Java Applet: Consistency Based CSP Solver. 

1. To be listed...

1. Syllabus and grading strategy
2. Algorithms for Constraint Satisfaction Problems: A Survey by Vipin Kumar. AI Magazine Spring 1992.
3. Constraint Satisfaction Problems, An Overview.   Pedro Meseguer
4. Constraint Programming: in Pursuit of the Holy Grail. Bartak
5. Administrative Note (powerpoint)
6. The Theory of NP-Completeness. Computers and Intractability, Garey & Johnson (1979), Chapter 2, pages 17--28.
7. Lecture Slides I: Overview (I) (powerpoint)
8. Lecture Slides 2: Overview (II) (powerpoint)
9. Reminder of Major Deadlines (powerpoint)
10. List of projects distributed (ps, pdf)
11. Lecture Slides 3: CSPs and Relational DBs (powerpoint)
12. Lecture Slides 4: Consistency Algorithms (powerpoint)
13. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems--Mackworth/Freuder
14. "A Perspective on Constraint Research in Industry," by Dr. Lisa Purvis, 2003.
15. Lecture Slides 5: Ordering Heuristics (ps, pdf)
16. Ordering heuristics in CSPs, Tsang 93
17. Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen 92
18. Lecture Slides 6: Example of triangulated graphs
19. Lecture Slides 7: Backtracking algorithms , Prosser
20. Hybrid algorithms for the constraint satisfaction problem--Prosser
21. Lecture Slides 8: A Theoretical Evaluation of Backtracking Algorithms , Prosser
22. Lecture Slides 9: Local Search (powerpoint slides)
23. Lecture Slides 10: Multi-Agent Search (ERA), Zou and Choueiry, pages 81--101, ACP 2003.
24. Characterizing the Behavior of a Multi-Agent Search by Using it to Solve a Tight, Real-World Resource Allocation Problem, Zou and Choueiry, pages 81--101, ACP 2003.
25. Lecture Slides 11: Interchangeability Relations in CSP.
26. Eliminating Interchangeable Values in Constraint Satisfaction Problems, E.C. Freuder, AAAI 1991, pages 227--233.

Glossaries:

1. Glossary 1
2. Glossary 2
3. Glossary 3
4. Glossary 4
5. Glossary 5
6. Glossary 6
7. Glossary 7
8. Glossary 8

Homework:

You can use the Web Handin System to submit your files, when handin is required.
 

Homework	Date assigned	Due Date
Homework 1 (ps, pdf)	Wednesday Sep 10, 2003	Wednesday Sep 24, 2003 Submit by pen+paper or print out right before class
Homework 2 (ps, pdf)	Friday Sep 26, 2003	Friday, Oct 10, 2003. Deadline Extension: Monday Oct 13, 2003
Homework 3 (ps, pdf)	Monday Oct 13, 2003  Important note: condition n in HWK2 should read: "The racer in the blue t-shirt placed either immediately before or immediately after the racer from Oklahoma state."	DEADLINE EXTENSION: Monday Nov 10, 2003.
Homework 4 (ps, pdf)	Friday Nov 7, 2003	Friday, Nov 21, 2003.

Schedule:
 

Date	Material	Announcements
Mon, Aug 25	Topic:  Administrative rules. Required reading:  Algorithms for Constraint Satisfaction Problems: A Survey by Vipin Kumar. AI Magazine Spring 1992. Recommended reading: Bartak's on-line guide: Introduction to CSPs Constraint Satisfaction Problems, An Overview.  Pedro Meseguer  Constraint Satisfaction,  Rina Dechter.  MIT Encyclopedia of the Cognitive Sciences  Constraint Programming: in Pursuit of the Holy Grail. Bartak	Room change: class will be held in Burnett 119. Six handouts were distributed.
Wed, Aug 27	Topic:  Overview, CSP 101. Required reading:  Same as above Recommended reading:  Same as above
Fri, Aug 29	Topic: Overview, CSP 101 Required reading:  Same as above Recommended reading: Same as above	Pretest (20 minutes max). In class (closed book) and take home.
Mon, Sep 1	School Holiday - Labor Day
Wed, Sep 3	Topic:  Overview, CSP 101. Required reading:  Same as above Recommended reading:  Same as above	Pretest Take Home part is due Glossary 1 assigned
Fri, Sep 5	Topic:  Overview, CSP 101. Required reading:  Same as above Recommended reading: Same as above
Mon, Sep 8	Topic:  Overview, CSP 101. Required reading:  Same as above Recommended reading: Same as above	Glossary 1 due Glossary 2 assigned
Wed, Sep 10	Topic:  Overview, CSP 101. Systematic Search Required reading:  Same as above Recommended reading:Dechter, Section 1.1, 1.2, 2.1 (2.1.1, 2.1.2, 2.1.3)	Quiz 1 Homework 1 (ps, pdf) List of projects distributed (ps, pdf)
Fri, Sep 12	Topic:  Overview, CSP 101. Systematic Search Required reading:  Same as above Recommended reading: Same as above
Mon, Sep 15	Topic:  Overview, CSP 101. Local Search, Research directions. Required reading:  Same as above Recommended reading: Same as above	Glossary 2 due Glossary 3 assigned
Wed, Sep 17	Same as above	Quiz 2
Fri, Sep 19	Same as above
Mon, Sep 22	Topic:  Constraints & Relational Databases Required reading:  Dechter's book, Section 1.3. Notes of Rina Dechter Recommended reading: Query Algebra Database System Implementation, pages 240--247,   Garcia-Molina, Ullman, Widom. Prentice Hall.	Glossary 3 due Glossary 4 assigned
Wed, Sep 24	Topic:  Finish up `Constraints & Relational Databases'. Start `Consistency Algorithms' Required reading: Sections 3.1, 3.2, 3.3 of Dechter's book. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems--Mackworth/Freuder Recommended reading:	Quiz 3
Fri, Sep 26	Topic:  Consistency Algorithms Required reading: Sections 3.1, 3.2, 3.3 of Dechter's book. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems--Mackworth/Freuder Recommended reading:  Sections 3.4--3.10 of Dechter's book. Networks of Constraints: Fundamental Properties and Application to Picture Processing--Montanari, Information Sciences, 1974. (Retrieve from instructor.) Consistency in networks of relations--Mackworth Constraint propagation with interval labels, E. Davis Path Consistency on Triangulated Constraint Graphs, Bliek, Sam-Haroud, IJCAI 99	Glossary 5 assigned Homework2 assigned
Mon, Sep 29	Topic:  Anagh Lal will discuss interchangeability. Required reading:  Recommended reading:	Instructor out of town Deadline for submitting project proposals, by web-handin Glossary 4 due Quiz 4
Wed, Oct 1	Topic:  Zheying (Jane) Yang will discuss empirical evaluations of pre-processing and look-ahead techniques. Required reading:  Recommended reading:	Instructor out of town
Fri, Oct 3	Topic:  Consistency Algorithms and their complexity Required reading:  Same as Sep 16 Recommended reading: Same as Sep 16
Mon, Oct 6	Topic:  Consistency Algorithms and their complexity Required reading:  Same as Sep 16 Recommended reading:Same as Sep 16	Glossary 5 due Glossary 6 assigned
Wed, Oct 8	Topic:  Consistency Algorithms and their complexity Required reading:  Same as Sep 16 Recommended reading:Same as Sep 16
Fri, Oct 10	Industial visitor: Dr. Lisa Purvis, Xerox Corporation. Topic: A Perspective on Constraint Research in Industry Required reading:  Purvis L, Pu P. "Adaptation Using Constraint Satisfaction Techniques" 1995. Purvis, L., Jeavons P. "Constraint Tractability Theory and its Application to the Product Development Process for a Constraint-Based Scheduler", 1999. Purvis, L. "A Genetic Algorithm Approach to Automated Custom Document Assembly", August 2002. Recommended reading: Check Dr. Purvis' publications	Homework2 deadline extended
Mon, Oct 13	Topic:  Consistency Algorithms and their complexity Required reading: Same as Sep 16 Recommended reading: Same as Sep 16	Glossary 6 due Homework2 due Homework3 assigned
Wed, Oct 15	Topic:  Higher order consistency Required reading:  Same as Sep 16 Recommended reading: Same as Sep 16	Quiz 5
Fri, Oct 17	Topic:  Minimality and decomposability Required reading:  Same as Sep 16 Recommended reading: Same as Sep 16	Important note for HWK3: Condition (n) in HWK2 should read: "The racer in the blue t-shirt placed either immediately before or immediately after the racer from Oklahoma state." Glossary 7 assigned
Mon, Oct 20	School Holiday - Fall Break
Wed, Oct 22	Topic:  Last talk on consistency... Required reading:  same as above Recommended reading: same as above
Fri, Oct 24	Topic:  Ordering Heuristics Required reading:  Ordering heuristics in CSPs, Tsang 93 Recommended reading: Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen 92	Glossary 7 due
Mon, Oct 27	Topic:  Same as above Required reading: Same as above Recommended reading: Same as above	Quiz 6
Wed, Oct 29	Topic:  Backtracking algorithms Required reading:  Hybrid algorithms for the constraint satisfaction problem--Prosser Recommended reading: Chapter 5, Tsang Chapters 5 and 6, Dechter Lecture notes of Fahiem Bacchus: Chapter 2, Section 2.4 (available upon demand) Lecture notes of Pandu Nayad: Handouts 4 & 5	Glossary 8 assigned
Fri, Oct 31	Topic:  Backtracking algorithms: BT, BJ Required reading:  Same as above Recommended reading: Same as above	Deadline for submitting progress reports on projects, use web-handin
Mon, Nov 3	Topic:  Backtracking algorithms: CBJ, BM Required reading:  Same as above Recommended reading: Same as above	Deadline for HWK3 extended by 1 week.
Wed, Nov 5	Topic:  Backtracking algorithms: BM, FC Required reading:  Same as above Recommended reading: Same as above	Glossary 8 due
Fri, Nov 7	Topic:  A Theoretical Comparison of Backtracking Algorithms Required reading: see below Recommended reading:see below	Quiz 7 Homework4 assigned
Mon, Nov 10	Topic:  Theoretical evaluation of backtracking algorithms Required reading:  A Theoretical Evaluation of Selected Backtracking Algorithms. Kondrak and van Beek. Recommended reading: The longer and improves paper, which appeared in the AIJ	Homework 3 due
Wed, Nov 12	Topic:  same as above Required reading:  same as above Recommended reading: same as above
Fri, Nov 14	Topic:  Reduction from non-binary to binary CSPs Required reading: Binary vs. non-binary representations of constraint-- Bacchus and Van Beek, 98, F. Bacchus and P. van Beek, National Conference on Artificial Intelligence (AAAI-98),  pages 311-318, 1998.  Recommended reading:  "On forward checking for non-binary constraint satisfaction" C. Bessière and P. Meseguer and E.C. Freuder and J. Larrosa, Proceedings CP'99, Alexandria VA, pages 88-102.  Decomposable Constraints. Ian Gent, Kostas Stergiou and Toby Walsh. Artificial Intelligence, 123 (1-2), 133-156, 2000.
Mon, Nov 17	Topic:  Local Search Required reading:  Dechter: Sections 7.1 and 7.2 Recommended reading: Bartak's chapter on Stochastic Search AIMA: Section 4.4 (first edition), Section 4.3 (second edition) Bresina: "Heuristic-Baised Stochastic Sampling," AAAI 96, pages 271-278.	Quiz 8
Wed, Nov 19	Topic:  same as above Required reading:  Same as above Recommended reading:
Fri, Nov 21	Topic:  More on stochastic local search: ERA Required reading:  Characterizing the Behavior of a Multi-Agent Search by Using it to Solve a Tight, Real-World Resource Allocation Problem, Zou and Choueiry, pages 81--101, ACP 2003. Recommended reading: Multiagent Oriented Constraint Satisfaction, Jiming Liu, Han Jing and Y.Y. Tang, Artificial Intelligence, Volume 136, Issue 1, March 2002	Homework4 due
Mon, Nov 24	Topic:  Same as above Required reading:  Recommended reading:
Wed, Nov 26	School Holiday - Thanksgiving
Fri, Nov 28	School Holiday - Thanksgiving
Mon, Dec 1	Topic:  Same as above Required reading:  Recommended reading:	Deadline for submitting summaries or `book chapters.' Maximum 4 summaries per student. Maximum of 2 book chapters per student. ALL paper presentations must be made BEFORE this date.
Wed, Dec 3	Topic:  Same as above. Presentation by Colby & Eric on Local Search Required reading:  Recommended reading:
Fri, Dec 5	Topic:  Interchangeability Relations Required reading:  Eliminating Interchangeable Values in Constraint Satisfaction Problems, E.C. Freuder, AAAI 1991, pages 227--233. Recommended reading: Papers by instructor, colleagues and students on the topic (ask instructor)	Deadline for submitting project report (paper and electronic). Deadline for submitting final glossary (paper copy).
Mon, Dec 8	Topic:  PROJECT DEFENSE Attendance mandatory	Evening meetings if necessary, attendance optional
Wed, Dec 10	Topic:  PROJECT DEFENSE Attendance mandatory	Evening meetings if necessary, attendance optional
Fri, Dec 12	Topic:  PROJECT DEFENSE Attendance mandatory	Evening meetings if necessary, attendance optional Deadline for submitting code developed for projects and presentation slides (use handin).
Fri, Dec 17	NO FINAL EXAM