CSCE 421/821

Foundations of Constraint Processing

Detailed Course Schedule

Announcement: None
  • Glossary 3 due.
  • Glossary 4 assigned.
    • Week 1
    Mon, Jan 8 Topic: Rules of the game
  • Course syllabus (distributed)
  • Administrative rules including deadlines
  • Guidelines for reports

    • Topic: CSP 101, Overview
  • Instructor's slides: Constraint Processing 101 (PPT)
  • Quick review of NP-Completeness (by Shant and Rahul).

    • Required reading:
  • Dechter: Section 1.1, 1.3.3, 1.3.4, 2.1 and 2.2.
  • Constraint Programming: in Pursuit of the Holy Grail (PDF) Bartak

    • Recommended reading:
  • Bartak's on-line guide: Introduction to CSPs
  • Constraint Satisfaction (PDF) Rina Dechter. MIT Encyclopedia of the Cognitive Sciences 
  • Systematic Search Algorithms, Bartak's online notes
  • Heuristics and Stochastic Algorithms, Bartak's online notes
    • Wed, Jan 10 Topic, required reading, recommended reading: Same as above
    Wed, Jan 10 Recitation:
  • Short tutorial on Piazza
  • Refresher on Handin
  • About using Grader
    		•
    Fri, Jan 12
    Pretest
  • In-class: closed book, handwritten crib sheet allowed, must be turned in with test
  • Take-home: collaboration, discussion strictly forbidden. To be returned on Wednesday, Jan 17
  • CSP 101
    		•
    Week 2
    Mon, Jan 15
    Martin Luther King Jr Day (no class)
    Wed, Jan 17 Topic, required reading, recommended reading: Same as above.
    Announcements:
  • Take home pretest due
  • Glossary 1 assigned
  • Homework 1 assigned
  • Homework 1 Tutorial
    		•
    Wed, Jan 17 Recitation:
    Fri, Jan 19
    Week 3
    Mon, Jan 22 Class cancelled for inclement weather. Announcement:
  • Glossary 1 due.
    		•
    Wed, Jan 24 Topic: Same as above.
    Announcement:
  • Glossary 1 due.
  • Glossary 2 assigned.
    • Announcement:
    Wed, Jan 24 Recitation:
    Fri, Jan 26 Topic: Arc Consistency: AC-1, AC-3, AC-4.

    Required reading:
  • Section 3.1 and 3.2 in Chapter 3 of Dechter
  • The complexity of some polynomial network consistency algorithms for constraint satisfaction problems Mackworth & Freuder, AIJ 1985 (only AC algorithms)

    • Recommended reading:
  • 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 Optial Coarse-Grained Arc Consistency Algorithm (PDF) Bessiere et al., AIJ 2005

    • Announcement:
  • Homework 1 due
  • Homework 2 assigned
    		•
    Week 4
    Mon, Jan 29 Announcement:
  • Glossary 2 due.
  • Glossary 3 assigned.
    		•
    Wed, Jan 31
    Wed, Jan 31 Recitation:
  • Quiz 1
    • Fri, Feb 2 Topic: Finish AC; Start Backtracking Search.

    Required reading:
  • Hybrid algorithms for the constraint satisfaction problem (PDF) Prosser

    • Recommended reading:
  • Chapters 5 and 6, Dechter
  • Chapter 5, Tsang
    		•
    Week 5
    Mon, Feb 5
    Wed, Feb 7 Topic: Evaluation of Deterministic Algorithms for CSPs.

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

    • Additional handout: Protocal for conducting experiments (.jpg)
    Wed, Feb 7 Recitation:
  • Quiz 2
    • Fri, Feb 9 Announcement:
  • Homework 2 due
    		•
    Week 6
    Mon, Feb 12 Announcement:
  • Glossary 4 due.
  • Glossary 5 assigned.
    		•
    Wed, Feb 14 Topic: Forward Checking. Start theoretical evaluation.

    Required reading:
  • A Theorectical Evaluation of Selected Backtracking Algorithms, by Kondrak and van Beek (IJCAI 1995)

    • Recommended reading:
  • Dechter, Chapters 5 and 6

    • Wed, Feb 14 Recitation:
    Fri, Feb 16 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement:
  • Quiz 3
  • Homework 3 Progress Report due
    		•
    Week 7
    Mon, Feb 19 Topic: Search Orders in CSPs. Required reading:
  • Chapter 6, Tsang 93
    • Recommended reading:
  • Dechter: Sections: 5.1.1
  • Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen ECAI 92
    • Announcement:
  • Glossary 5 due
  • Glossary 5B assigned
    		•
    Wed, Feb 21 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None
    Wed, Feb 21 Recitation: A presentation by Mr. Philip Walton from Workday on integrating CP and mathematical programming
    Fri, Feb 23 Announcement:
  • Homework 3 due
  • Homework 4 assigned
    		•
    Week 8
    Mon, Feb 26 Topic: GAC on AllDiff Constraint.
    Required reading:
  • Régin (AAAI 94): A Filtering Algorithm for Constraints of Differences in CSPs.
  • Dechter, Section 3.5.1.
    • Recommended reading:
  • 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.
    • Announcement:
  • Glossary 5B due
  • Glossary 6 assigned
    		•
    Wed, Feb 28 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Wed, Feb 28 Recitation:
  • Quiz 4
    		•
    Fri, Mar 2 Announcements:
  • Homework 4 Progress Report due
    		•
    Week 9
    Mon, Mar 5 Announcement:
  • Glossary 6 due
  • Glossary 7 assigned
    		•
    Wed, Mar 7 Topic: Path Consistency.
    Required reading:
  • The complexity of some polynomial network consistency algorithms for constraint satisfaction problems Mackworth & Freuder, AIJ 1985 (only AC algorithms)
  • Dechter: Sections 3.1, 3.2, 3.3.
    • Recommended reading:
  • Consistency Techniques (Bartak's online notes)
  • Chapter 3 entirely
  • Path Consistency on Triangulated Constraint Graphs , Bliek and Haroud

    		•
    Wed, Mar 7 Recitation:
  • Quiz 6 (ops, Quiz 5 next time!)
    • Fri, Mar 9 Announcement:
  • Homework 4 due
  • Homework 5 assigned
    		•
    Week 10
    Mon, Mar 12 Announcement:
  • Glossary 8 assigned
    		•
    Wed, Mar 14
    Wed, Mar 14 Recitation:
    Fri, Mar 16 Topic: Local Search
    Required reading:
  • Dechter, Chapter 7
  • Heuristics and Stochastic Algorithms (Bartak's online notes)
    • Recommended reading: < li> 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.
    Announcement:
  • Project must be chosen. Submit via handin
  • Homework 5 Progress Report due
  • Glossary 8 due
    		•
    Week 11
    Mon, Mar 19
    Spring Break (no class)
    Wed, Mar 21
    Spring Break (no class)
    Wed, Mar 21
    Spring Break (no class)
    Fri, Mar 23
    Spring Break (no class)
    Week 12
    Mon, Mar 26
    Announcement:
  • Homework 5 due
  • Glossary 9 assigned
    		•
    Wed, Mar 28 Topic:Finish Local Search. Start Structure-Based Techniques

    Required reading:
  • Dechter Sections: 2.1.3, 5.1.2, 10.1.1, 4.2.2, 9.2, 4.4, 9.2.2.

    • Recommended reading:
  • 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
    		•
    Wed, Mar 28 Recitation:
  • Quiz
    • Fri, Mar 30 Topic: Same as above
    Required reading: Same as above
    Week 13
    Mon, Apr 2 Topic: Same as above
    Required reading: Same as above
    Announcement:
  • Glossary 9 due
    		•
    Wed, Apr 4 Topic: Same as above
    Required reading: Same as above
    Announcement:
  • Deadline: Progress reports of projects are due. (Use handin)
    		•
    Wed, Apr 4 Recitation:
    Fri, Apr 6 Topic: Same as above
    Required reading: Same as above
    Announcement:
  • Deadline: First deadline for extra-credit work. At most 1 paper presentation, 2 summaries, 1 chapter write-up after this date.
    • Week 14
    Mon, Apr 9 Topic: Same as above
    Required reading: Same as above
    Wed, Apr 11 Topic:Finish: Structure-Based Techniques
    Required reading: Same as above.
    Wed, Apr 11 Recitation:Quiz
    Fri, Apr 13 Topic: More on Consistency Properties and Algorithms.
    Required reading: Refer to slides and Index of textbook.
    Week 15
    Mon, Apr 16 Topic: Same as above
    Required reading: Same as above
    Wed, Apr 18 Topic: Same as above
    Required reading: Same as above
    Wed, Apr 18 Recitation:
    Fri, Apr 20 Topic: Advanced Backtrack Search
    Required reading: Refer to slides. Announcements:
  • Quiz may be given
  • Deadline: Final glossary due, in print and using handin.
  • Deadline: Project report due, in print and using handin.
  • Deadline: Second deadline for extra-credit work: No paper presentation, summaries, write-ups, on or after this date.
    		•
    Week 16 (dead week)
    Mon, Apr 23 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
    		•
    Wed, Apr 25 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
    		•
    Wed, Apr 25 Recitation:
  • PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
    		•
    Fri, Apr 27 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
  • Deadline: Project code and slides due, submit using handin.
  • Deadline: Final revisions to Project reports are due in print and using handin.
    		•
    Week 17
    Mon, Apr 30
    No Final Examination
    8:30—10:30 AM PROJECT DEFENSE
    Attendance is mandatory