CSCE421/821, Fall 2003: 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.

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.

Time: Monday, Wednesday, and Friday from 10:30 a.m. to 11:30 a.m.

Place: Burnett Hall 119.

Instructor:   Berthe Y. Choueiry
                      Room 104, Ferguson Hall,
                      email: choueiry@cse.unl.edu, tel: (402)472-5444.
                      Office hours:  Monday & Wednesday from 11:30 a.m. to 12:30 p.m. (right after class)

TA:   Cate Anderson
         email: anderson@cse.unl.edu
         Office location: Bld 501, Room 6, Desk 6.13
         Office hours: Monday: 12:30-1:30 p.m. and Friday: 11:30-12:20 p.m.

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

In an effort to provide you with the best possible support, the following research assistants will be holding office hours in Building 501, Room 3:

• Ryan Lim (ugrad): Tuesday, 1:00--2:00 pm
• Joel Gompert (MS): Wednesday, 2:30--3:30 pm
• Anagh Lal (MS): Thursday, 12:00--1:00 pm

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 Love Library.
• 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.  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.  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.  Results will be compared, winner will receive a book-gift certificate.
• 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  computers.
• Optional Text Book "Constraint Processing" by Rina Dechter, 1^st edition.
• Discussions among students, instructor, and TA are encouraged.  Homeworks 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, 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 6 sessions, 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:  32%
• Assignments: 30%
• 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 two presentations per student. Presentations must be made before December 1st, 2003.
• Make a critical summary of research papers/topics discussed in class: 5% per summary. Maximum four summaries per student. Deadline for submitting summaries December 1, 2003.
• Write a chapter of a textbook: 20% per chapter. Maximum two chapters per student. Deadline for submitting chapter write-ups December 1, 2003.
• Do the weekly and final glossaries: maximum 10%. Deadline for submitting final glossary December 5, 2003.
• 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 Love Library (LL):

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

Books available at the Love Library (LL):

• Artificial Intelligence, A Modern Approach (AIMA), by Russell & Norvig. CALL number Q335 .R86 1995.

Other references:

• 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.
• AI Topics of the American Association for Artificial Intelligence
• Web search engines (Google, CiteSeer, Altavista, etc.)

Related material from the Web:

Some industrial companies and start-ups implementing advanced constraint-based systems: (listed in random order)

• COSYTEC,  I2 Technologies,  PeopleSoft/Red Pepper, J.D. Edwards/Numetrix (production scheduling),  Blue Pumpkin, Ilog, Trilogy, Parc Technologies Ltd, Carmen Systems, Firepond, On Time Systems Inc., OnTarget, 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

Groups:

• LIA@EPFL
• APES Group in the UK.
• Constraint Computation Center of Freuder in Univ. of New Hampshire.
• Cork Constraint Computation Center (4C) of Freuder in University College Cork, Ireland.

Archives and on-line systems:

• RandomCSP 1.8.0 by by J.I. van Hemert
• various models of random generators in Java by Bart Craenen
• (obsolete) Random generator in Java by Zheying Yang (zyang@cse.unl.edu)
• Links to Constratint Solvers, via the CSPLIB
• The ECLiPSe Constraint Logic Programming System
• Constraints archives at CCC.
• 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).

Conferences:

• Constraint Programming (CP), AAAI, IJCAI, ECAI, FLAIRS, etc.

Additional resources:

• Lisp resources
• Eric Moss: personal help page 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. <http://www.scieneer.com/
• 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: