General Information

Prereq: CSCE310, Data structures and algorithms.

Course description: Constraint satisfaction has emerged as a powerful approach to articulate and solve many problems in computer science, engineering, and management.  It is now the basis for new programming languages and innovative commercial systems for production scheduling, product configuration, personnel planning and timetabling, etc.  The course will review the foundations of constraint satisfaction and the basic mechanisms for constraint propagation.  It will cover aspects of modeling and representation, and will examine islands of tractability and methods for theoretical and empirical evaluation of problem `difficulty.'  If time permits, we will examine new methods for decomposition and symmetry identification, designed to overcome the complexity barrier and to support interactions with users.

Lectures: Monday and Wednesday from 3:30 p.m. to 4:45 p.m.
Location: Avery Hall, Room 111.

Make-up Class/Recitation: Monday from 5:00 p.m. to 5:50 p.m.
Location: Avery Hall, Room 28D and Room 112.

Instructor:   Prof.  Berthe Y. Choueiry
      Office location: Room 123B, Avery Hall,
      choueiry AT cse.unl.edu, tel: (402)472-5444.
      Office hours: Monday/Wednesday 12:30-1:30 p.m. or by appointment.

TA:   Mr. Jamie Schirf
      email: jschirf AT cse.unl.edu
      Office location: Room 123A, Avery Hall
      Office hours: @ Student Resource Center on Tuesday, Thursday 5:00-6:00 p.m. and Friday 10:30-11:30 p.m.

Textbook:
"Constraint Processing" by Rina Dechter, 1^st edition. The textbook will not be followed sequestially, but should be used for reference.

For quick response, email cse421@cse.unl.edu.  Your message will be forwarded to both TA and instructor.

Important note: The GTA allocated to this class does not have extensive experience in the subject matter and will mainly help with administrative matters. All questions will have to be made to the instructor during office hours, make-up class, by email, or by appointment. We will follow a `peer-correction system' by which students grade each other's (glossaries and) homework with help from the TA and under close monitoring by the instructor.

Topics include but are not restricted to:

• Properties, computational complexity, and practical importance.
• Global and local consistency: algorithms, properties and computational complexity.
• Islands of tractability for minimality and global consistency.
• Intelligent backtracking.
• Look-ahead techniques.
• Ordering heuristics.
• Theoretical and empirical comparison of hybrid search algorithms.
• Phase transition.
• Modeling and reduction methods between representations.
• If time permits: Decomposition. Symmetries and their approximations. Temporal constraint networks. Stochastic search. Reformulation and abstraction. Dynamic/conditional Constraint Satisfaction (CSP). Constrained Optimization Problem (COP).
• Other, depending on class interests.

Support:

• Rina Dechter, Constraint Processing, 2003, Morgan Kauffmann.  Available from bookstore.
• Edward Tsang, Foundations of Constraint Satisfaction. Available from instructor and on reserve at the Math Library in Avery.
• Technical papers given by instructor or available from the Electronic Reserve at the Love Library.

Protocol of the Course

The course consists of lectures by the instructor, three times per week.

Workload

Required and recommended reading:

Programming, theoretical, and library-search assignments:

Surprise quizzes:

Tests:

Search Competition:

Project research, report, and presentation:

Attendance

Alerts

It is the students responsibility to ensure an account on the department's computers.

Discussions among students, instructor, and TA are encouraged. Homework however are a strictly individual activity: no sharing is permitted (unless when specified by instructor). Unethical behavior will be heavily sanctioned (e.g., a null grade on the task).

Always acknowledge any help received from other individuals.

Always fully reference material used (e.g., encyclopedia, book, paper, journal, web site).

Grading Policy

Grade Distribution

• Pre-test: 3%
• (Surprise) quizzes: 37%
• Assignments: 25%
• Individual project
• Search competition: Solving a real-world optimization problem (in Lisp): 35% (Code and report: 25%, Presentation: 10%)
• Project: 35%.  (Research and report: 25%. Presentation: 10%.)

Grade Conversion

Reminder from the College of Arts & Sciences: a C (2.0) is the minimum passing grade in a PASS/NO PASS course (NOT a C-) as well as the lowest grade one can receive and still count the class toward a major.

How to Secure a Good Final Grade

Make a Presentation

Critical Summary

Write up

Attendance

Glossaries

• Students will be have to build an incremental and alphabetically sorted glossary of important terms.
• Terms to be included are the ones listed in the handouts distributed in class or sent my email.
• A glossary entry can be filled with: (1) its definition in Dechter's textbook, (2) its definition from another AI textbook, dictionary, or web resource, or (3) the student's own interpretation.
• All terms encountered during a week are due as a weekly glossary the following Monday, or as indicated in the schedule of the class.
• At the end of the course, the full alphabetically sorted glossary is due. The deadline for submitting final glossary is April 29, 2008 (Hint: choose a text editor that can sort entries alphabetically.)

Additional Work

Books on Reserve at the Math Library in Avery

Constraint Processing

AI

Lisp

Logic

(AI) References

Online Resources

Puzzles Built @ the ConSystLab

Benchmark Problems

Archives and On-Line Systems

Main publication venues

Conferences:

Journals:

Constraint Processing

Industrial companies and start-ups

Research Centers

Courses

Academic Research Groups

Latex Resources