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

In this page:
  • Your catch
  • Benchmarks
  • List of projects
  • Homework
  • Glossaries
  • Handouts
  • Material discussed during recitation (empty)
  • More material
  • Detailed schedule
    • Your catch:  Interesting material you find on the web and that you would like to share. Every student is welcome to propose a link of interest to the class. The student's name will be included.

    Vintage Fall'2003: Vintage Fall '2002: Vintage Fall'2001:

    Benchmark problems:

    1. Coloring Australia map: in the format of HWK2 (courtesy of Dave) and in the xml format of CP Competition (courtesy of Ken).
    2. A wealth of benchmark problems.
      These problem instances are written using the new standards for representing CSP instances: an XML representation and also a table representation.
      There are made available by the organizers of the Second International Workshop on Constraint Propagation and Implementation held in conjunction with CP 2005.
      These instances were used in the First International Constraint Solver Competition.
      A related (same? overlapping? but not disjoint) set of benchmark problems can be accessed from Lecoutre's page.
    3. A (JAVA) checker for validating and converting CSP instances between the xml format and in the table format.
    4. CLib: Configuration Benchmarks Library.

    List of projects:

    1. Garhan Attebury: Finding robust solutions.
    2. Renee Augustyn: Quick Shaving.
    3. Ken Bayer: Pseudo tree decompositions.
    4. Josh Snyder: Propagation rules for Mine Sweeper.
    5. David Svatora: Dynamic Backtracking.
    6. Nick Zielinski: Solving tree-decompositions with backtrack search.

    Homework:
    You must submit your files via handin when required. Homework must be returned before class on due date.


    Homework
    Date assigned
    Due Date
    Homework1 (ps, pdf) Wednesday, August 31, 2005 Tuesday, September, 13, 2005
    Note: pen+paper or print out
    Homework2 (ps, pdf) Tuesday, Sep 13, 2005 Thursday, Sep 22, 2005
    Note: Submit with (command line) handin
    Homework3 (ps, pdf) Thursday, Sep 22, 2005 Extended until Wedsnesday, Oct 19, 2005
    Note: Submit with (command line) handin
    Homework4 (ps, pdf) Wednesday, Oct 19, 2005 Monday, Nov 1st, 2005
    Homework5 (ps, pdf) Wednesday, Nov 9, 2005 Tuesday, Nov 22, 2005

    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. This glossary is just for your record, need not be returned.

    Handouts:

    1. Syllabus and grading policy.
    2. Instructor's slides: Administrative Note (powerpoint)
    3. Instructor's slides: Guidelines for reports (powerpoint)
    4. Instructor's slides:Constraint Processing 101 (powerpoint)
    5. Instructor's slides: Backtracking mechanims (powerpoint)
    6. Instructor's slides: Overview: advanced solving techniques and research directions (powerpoint)
    7. A Theorectical Evaluation of Selected Backtracking Algorithms (gziped PostScript, Electronic Reserve), by Kondrak and van Beek
    8. Instructor's slides: A Theorectical Evaluation of Selected Backtracking Search (powerpoint)
    9. Instructor's slides: Constraints & Relational Databases (powerpoint)
    10. Instructor's slides: Consistency: Main Properties and Algorithms for Achieving them (powerpoint)
    11. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems--Mackworth/Freuder
    12. Instructor's slides: Search Orders in CSPs (powerpoint)
    13. Ordering Heuristics in CSPs, Chapter 6, Tsang
    14. Dr. Boddy's slides: Constraint-Based Scheduling in the Real World (powerpoint)
    15. Instructor's slides: Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems (ps, pdf)
    16. Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen (ECAI 92)
    17. Instructor's slides: Note on the "least commitment" strategy.
    18. Instructor's slides: Local Search (powerpoint slides).
    19. Instructor's slides: Advanced Backtrack Search (powerpoint slides).
    20. Binary vs. non-binary representations of constraint-- Bacchus and van Beek, 98.
    21. Instructor's slides: Binary vs. non-binary representations of constraint (ps, pdf).
    22. Instructor's slides: Non-Binary FC.
    23. On Forward Checking for Non-Binary Constraint Satisfaction-- Bessiere, Meseguer, Freuder, and Larossa, AIJ 2002.
    24. Instructor's slides: New(ew) Types of AC.
    25. Dr. Ruml' slides: Learning to Search Trees (pdf)
    26. Instructor's slides: Consistency algorithm for All-diff Constraints (ps, pdf).
    27. Régin (AAAI 94): `A Filtering Algorithm for Constraints of Differences in CSPs'.
    28. Instructor's slides: Interchangeability in CSPs (ps, pdf).
    29. Eliminating Interchangeable Values in Constraint Satisfaction Problems, E.C. Freuder, AAAI 1991, pages 227--233.
    (UNL access only) Most 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.

    Material discussed during recitation:

  • On the projection of non-binary constraints

    More material:

    1. Brelaz paper on variable ordering heuristic for coloring
    2. ECLiPSe: Tutorial(pdf file).
    3. Eliminating Interchangeable Value in Constraint Satisfaction Problems, Freuder, AAAI 1991.

    Schedule:
     
  • Final reports of projects due (printed form).
    • Date
    Material
    Announcements
    Tue, Aug 23 Topic: Administrative rules.
    		Handouts distributed: syllabus, administrative rules including deadlines, guidelines for reports, Constraint Processing 101.
    Wed, Aug 24 Topic: Administrative rules (if not finished on Monday). Introduction to CSPs.  
    Thu, Aug 25
  • Pretest: In class (closed book)
    • Topic: Introduction to CSPs.
    Required reading: Dechter: Section 1.1, 1.3.3, 1.3.4, 2.1 and 2.2.xo
    Recommended reading:
  • Bartak's on-line guide: Introduction to CSPs
  • Algorithms for Constraint Satisfaction Problems: A Survey by Vipin Kumar. AI Magazine Spring 1992.
  • 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 (POSTSCRIPT,PDF). Bartak
    		•
  • Pretest: Take home (individual effort, no collaboration)
    • Tue, Aug 30 Topic: CSP 101
    Required reading: same as above
    Recommended reading: same as above     		 
    Wed, Aug 31 Topic: CSP 101
    Required reading: same as above
    Recommended reading: same as above
  • Homework1 assigned
  • Glossary1 assigned
    • Thu, Sep 1 Topic: Backtrack search and hybrids
    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
    		•   
    Tue, Sep 6 Topic:Backtrack search and hybrids
    Required reading: same as above
    Recommended reading: same as above     		 
    Wed, Sep 7 Topic: Backtrack search and hybrids
    Required reading: same as above
    Recommended reading: same as above    		  
    Thu, Sep 8 Topic: Backtrack search and hybrids
    Required reading: same as above
    Recommended reading: same as above
  • Quiz 1
  • Glossary 1 due
  • Glossary2 assigned
    • Tue, Sep 13 Topic: Looking ahead
    Required reading: same as above, especially Section 5.3 in Dechter.
    Recommended reading: same as above
  • Homework1 due
  • Homework2 assigned
    •  
    Wed, Sep 14 Topic: Comparing Algorithms, especially Section 6.6.2 in Dechter.
    Required reading: same as above,
    Recommended reading: same as above
  • Quiz 2
  • Glossary 2 due
    • Thu, Sep 15 Topic: Overview: Decomposition, deep methods, distribusted CSPs
  • Glossary 3 assigned
    		•
    Tue, Sep 20 Topic: A Theoretical Approach to Backtracking (gziped PostScript, Electronic Reserve)
    Required reading:   A Theorectical Evaluation of Selected Backtracking Algorithms
    Recommended reading:   The longer and improved paper, which appeared in the AIJ     		 
    Wed, Sep 21 Topic: Same as above
  • Quiz 3
    		•
    Thu, Sep 22 Topic: Constraints & Relational Databases
    Required reading: Dechter's book, Section 1.3.
    Recommended reading: Query Algebra Database System Implementation, pages 240--247, Garcia-Molina, Ullman, Widom. Prentice Hall.
  • Glossary 3 due
  • Glossary 4 assigned
  • Homework 3 assigned
    		•
    Tue, Sep 27 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 4 due
    		•
    Wed, Sep 28 Topic: Same as above
  • Quiz 4
    		•
    Thu, Sep 29 Topic: Class cancelled Instructor out of town
    Tue, Oct 4 Topic: Class will discuss each other's implementation. One evaluator per speaker will write a report. Instructor out of town
    Wed, Oct 5 Topic: No make-up class Instructor out of town
    Thu, Oct 6 Topic: Class cancelled
  • Instructor out of town
  • Deadline for project selection (use handin)
    		•
    Tue, Oct 11 Topic: Same as above
  • Homework 3: extended until Wed, Oct 19
    		•
    Wed, Oct 12 Topic: Same as above
    Thu, Oct 13 Topic: Same as above  
    Tue, Oct 18
    Fall break
    Wed, Oct 19 Topic: Same as above
  • Homework 3 due
  • Glossary 5 assigned
  • Homework 4 assigned
    		•
    Thu, Oct 20 Topic: More discussion on consistency properties and algorithms
    		  
    Tue, Oct 25 Topic: Search orders in CSPs
    Required reading:   Ordering heuristics in CSPs, Tsang 93
    Recommended reading:  
  • Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen 92
    		•
  • Quiz 5 (rescheduled)
  • Glossary 5 due
    • Wed, Oct 26 Topic:  
    Thu, Oct 27 Topic: What Happens When Constraints Meet the Real World.
    A lecture by industrial visitor: Dr Mark Boddy (Adventium LABS)
    Check details from visit page
    Required reading: A Method for Global Optimization of Large Systems of Quadratic Constraints. N. Lamba, M. Dietz, D.P. Johnson, and M.S. Boddy. Second International Workshop on Global Constraint Optimization and Constraint Satisfaction 2003 (COCOS 03). Pages 61-70.
    Recommended reading: "Constraint-Based Attribute and Interval Planning". Jeremy Frank, Ari K. Jónsson, Journal of Constraints, Special Issue on Constraints and Planning. Pages 335-338. Vol. 8 no 4, 2003. (Available from library at Avery Hall)     		 
    Tue, Nov 1 Topic: Dual Viewpoint Heuristics for Binary Constraint Satisfaction
    Required reading: Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen (ECAI 92)
  • Homework 4 due
  • Glossary 6 assigned
    		•
    Wed, Nov 2 Topic: Local search
    Required reading: Dechter: Section 7.1, and 7.2.     		 
    Thu, Nov 3 Topic: Discussion of search results (homework 3 and 4)
  • Progress reports of projects are due (use handin)
    • Tue, Nov 8 Topic: Local search and empirical analysis
    Required reading: Dechter: Section 7.1, and 7.2.
  • Glossary 6 due
    		•
    Wed, Nov 9 Topic: New developments in Backtrack Search
    Recommended reading: ECLiPSe: Chapter 12 on Search
  • Glossary 7 assigned
  • Homework 5 assigned
    		•
    Thu, Nov 10 Topic: Learning to Search Trees.
    A lecture by industrial visitor: Dr. Wheeler Ruml (Palo Alto Research Center (PARC)). Check details from visit page
    Required reading: Heuristic Search in Bounded-depth Trees: Best-Leaf-First Search. W. Ruml. Working Notes of the AAAI-02 Workshop on Probabilistic Approaches in Search, 2002.     		 
    Tue, Nov 15 Topic: Binary vs non-Binary CSPs
    Required reading: Binary vs. non-binary representations of constraint-- Bacchus and van Beek, 98.
    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. 
    		•
  • Glossary 7 due
    		•
    Wed, Nov 16 Class does not meet. Individual meetings with instructor.  
    Thu, Nov 17 Topic:Non-binary Forward Checking
    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. 
  • At most 1 paper presentation, 2 summaries, 1 chapter write-up after this date.
    		•
    Tue, Nov 22 Topic: An Efficient Filtering for AllDiff Constraints
    Required reading: A Filtering Algorithm for Constraints of Differences in CSPs-- Regin, 1994.
  • Homework 5 due
    		•
    Wed, Nov 23
    Student holidady
    Thu, Nov 24
    Thanksgiving vacation
    Tue, Nov 29 Topic: Same as above.
  • A quiz may be given in class
    		•
    Wed, Nov 30 Topic: Same as above  
    Thu, Dec 1 Topic: Interchangeability in CSPs. 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)
  • A quiz may be given in class
  • No paper presentations, summaries, write-ups, on or after this date
  • Final Glossary due (printed form).
    		•
    Tue, Dec 6 Topic: PROJECT DEFENSE
    Attendance is mandatory
    Ken, Renee    		 Evening meetings if necessary, attendance optional
    Wed, Dec 7 Topic: PROJECT DEFENSE
    Attendance is mandatory
    Dave, Nick     		 
    Thu, Dec 8 Topic: PROJECT DEFENSE
    Attendance is mandatory
    Garhan, Josh
  • Evening meetings if necessary, attendance optional
  • Project code and slides due (use handin).
    		•
    Mon, Dec 12
    NO FINAL EXAM

    Berthe Y. Choueiry

    Last modified: