CSCE421/821, Fall 2005: Foundations of Constraint Processing

Annnouncement: we will try to have at least one researcher from the industry to talk about the market of this technology, techniques implemented in industrial products,  and commercial success stories. Check the list of previous visitors.

Prereq: CSCE310 (Data structures and algorithms) AND CSCE476/876 (Introduction to AI), or permission of instructor.

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: Tuesday and Thursday, 11:00 a.m.--12:15 p.m.
Location: AVH 111

Make-up Class/Recitation: Wednesday, 5:00 p.m.--6:00 p.m.
Location: AVH 111

Instructor: Berthe Y. Choueiry, AVH 123B,
                       email: choueiry@cse.unl.edu, tel: (402)472-5444.
                       Office hours:  Tuesday & Thursday from 12:30 p.m. to 1:30 p.m. (right after class).

Important note: No GTA is allocated to this class. 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 under close monitoring by the instructor.

Class schedule: the page will be regularly updated. Check it out regularly for reference to required and recommended reading material, homework texts, and announcements.

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:

• Lectures by instructor, three times per week.
• The workload will consist of:
• Required and recommended reading: as indicated in the Class schedule. The content of the course will be dynamically adapted to students interests and performance.
• Programming, theoretical, and library-search assignments: Programming assignments homework must be turned in using the UNIX handin program on cse.unl.edu and turned in before class on the due date. (Note that we will not use web handin.) Pen-and-paper assignments must be given to the instructor right before the lecture on the due date. Late homeworks are subject to a 20% deduction per day (including week-ends), any second after the due date counts as an entire day. Programming assignments can be done in any programming language. When code and data structures are provided, they will be mostly in Common Lisp (advice: use Allegro Common Lisp on Linux or a sun workstation).  Students are kindly requested to indicate how much time they approximately spend on each exercise; this information will be aggregated and used for planning purposes: it does not affect grading and the evaluation of individuals.
• Surprise quizzes:There will be surprise quizzes throughout the semester (with a frequency inversely proportional to students' attendance). Quizzes will address all material covered during the lectures and/or by the required reading. No books or personal notes are allowed during the quizzes, unless explicitly specified. Quizzes cannot be made up.
• Tests: There will be a pre-test only. The pre-test cannot be made up except by instructor's permission.
• Search competition: Students will receive code and data that model a real-world application, all in LISP. Students will choose some search mechanism and implement it in the language of their choice. Results will be compared, winner will receive a gift certificate for a book.
• Project research, report, and  presentation: The project can be either a literature study/survey or the implementation of algorithms.; A presentation to the class is mandatory. The grade will take into account the quality of the research, report, and presentation.
• It is the student's responsibility to ensure an account on cse.unl.edu.
• Textbook "Constraint Processing" by Rina Dechter, 1^st edition. The textbook will not be followed sequestially, but should be used for reference.
• Discussions among students, instructor, and TA are encouraged. However homeworks 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, department will be informed). Absolute rule: Always acknowledge any help received from other individuals and always fully reference material used (e.g., encyclopedia, book, paper, journal, web site).
• Absence: maximum 4 sessions including make-up class/recitation, advanced notice required. Attendance is taken. Students are responsible for the material covered and announcements made during the class.  Also, there will be surprise quizzes.

Grading policy:

• Grades will be allocated as follows
• Pretest: 3%.
• Quizzes:  37%
• Assignments: 25%
• Individual project
• Search competition: Solving a real-world optimization problem (in Lisp): 35% (Code: 25%, Report: 10%)
• Project: 35%.  (Research and report: 25%. Presentation: 10%.)

How can I imporve my grade?

• Make a presentation of a research paper in class: 10% per presentation. Maximum 2 presentations per student. One presentation must be made by November 17, 2005, and one by December 1, 2005.
• Make a critical summary of research papers/topics discussed in class: 5% per summary. Maximum 4 summaries per student. Two summaries must be submitted by November 17, 2005 and two by December 1, 2005.
• Write a chapter of a textbook: 20% per chapter. Maximum 2 chapters per student. One write-up must be submitted by November 17, 2005 and one by December 1, 2005.
• Do the weekly and final glossaries: maximum 8%. Deadline for submitting final glossary December 1, 2005.
• Bonuses will be awarded to students who attend all lectures, interact lively, and participate in discussion in class.

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.

Books on reserve at the Math Library in Avery Hall:

• Foundations of Constraint Satisfaction by Edward Tsang.
• Artificial Intelligence, A Modern Approach (AIMA), by Russell & Norvig. Second Edition.
• Artificial Intelligence, 3rd Edition.  Winston.

Books and references available at the Love Library (LL):

• Artificial Intelligence, A Modern Approach (AIMA), by Russell & Norvig. CALL number Q335 .R86 1995.
• The MIT Encyclopedia of the Cognitive Sciences. CALL  number BF311 .M556 1999, LIB USE ONLY.
• Encyclopedia of artificial intelligence, 1992, SECOND EDITION, call number Q335 .E53, LIB USE ONLY.

Other references:

• CP Online.
• AI Topics of the American Association for Artificial Intelligence
• Web search engines (Google, CiteSeer, Altavista, etc.)

Industrial companies and start-ups: (listed in random order)

• COSYTEC,  I2 Technologies,  Red Pepper (PeopleSoft, Oracle), Blue Pumpkin, Ilog, Trilogy, Parc Technologies Ltd (now CISCO), Carmen Systems, Firepond, On Time Systems Inc., ConfigWorks., etc.

Courses:

• Constraint Networks by Rina Dechter
• Constraint Programming Approach to AI Applications, by Michela Milano
• Foundations of Constraint Satisfaction, ESSLI 2002, by Roman Barak
• Constraint Programming: online textbook by Roman Barták.
• Reasoning Methods in AI (CS329A, CS227): courses by Pandu Nayak.
• Constraint Satisfaction Problems (CSC2512F): course by Fahiem Bacchus
• Tutorial on Constraint Programming, by Barbara Smith.
• Lecture notes by David McAllester.
• Bacchus' Constraint Programming Bibliography

Research groups:

• Constraint Systems Laboratory at UNL
• LIA@EPFL
• APES Group in the UK.
• Cork Constraint Computation Center (4C) of Freuder in University College Cork, Ireland.

Archives and on-line systems:

• Pointers to various generators from the ConSystlab web page.
• various models of random generators in Java by Bart Craenen
• Links to Constratint Solvers, via the CSPLIB
• The ECLiPSe Constraint Logic Programming System
• CSPLib: Problem Library on the Web.
• Random generator in C at LIRMM
• Random generator in Common Lisp by Patrick Prosser
• Random generator in C courtesy of Fahiem Bacchus (and P. van Run).
• JACK: a library providing constraint programming and search for Java (high-level language, generic search engine, and a visualization tool).

Main publication venues:

• Conferences: Constraint Programming (CP), AAAI, IJCAI, ECAI, FLAIRS, etc.
• Journals: AI Journal (index at the Love Library, online access access), Constraints (index at the Love Library, online access).

Additional resources:

• Lisp resources: Eric Moss: personal help page with Lisp
• 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

Last modified: