CSCE990-05, Fall 2000: Foundations of Constraint Satisfaction
Constraint course challenge:
best student (ties broken by lottery) will be
awarded attendance of a major
international conference in the field. Details in class.
announcement: we are working on inviting two
from two prominent companies
to talk about the market of this technology,
the techniques implemented
in their products and their success stories.
Prereq: CSCE310 (Data
structures and algorithms) or permission of instructor.
Note: This course is well suited for both senior level
and graduate students. In the future, it will be offered as CSCE426/826.
CSE students should consult with instructor regarding tracks (theory/software
Course description: Constraint Satisfaction has emerged
as a successful approach to articulate and solve many industrial problems
such as design, network diagnosis, vision, scheduling, and resource management
in wireless networks. This technology is now the basis for new programming
languages and innovative commercial systems for production scheduling,
product configuration, personnel planning and time-tabling, etc.
This course reviews the foundations of constraint satisfaction and the
basic mechanisms developed in this area. It also covers issues on
modeling and representation, special types of constraints such as
temporal constraint networks, and theoretical and empirical evaluation
of problem `difficulty.' The course will examine in particular new
methods for decomposition and symmetry identification, designed to overcome
the complexity barrier and to support interactions with users.
Monday, Wednesday, Friday, from 10:30 a.m. to 11:20 a.m.
Room 111, Ferguson Hall
Instructor: Berthe Y. Choueiry
Room 104, Ferguson Hall,
firstname.lastname@example.org, tel: (402)472-5444.
Office hours: Mon/Wed from 11:30 a.m. to 12:30 p.m., or by appointment.
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.
Theoretical and empirical classification of backtracking algorithms.
Theoretical and empirical of classification of static and dynamic ordering
Global and local consistency: algorithms, properties, and computational
Islands of tractability for minimality and global consistency.
Modeling and reduction methods between representations.
Symmetries and their approximations.
Reformulation and abstraction.
Extension: Dynamic/conditional constraint satisfaction, constraint
Edward Tsang, Foundations of Constraint Satisfaction. Available
Rina Dechter, Constraint Processing. In preparation, check
Technical papers given by instructor or available from the Electronic
Reserve at the Love Library.
Grades will be allocated as follows
Paper presentation: 20%
Bonuses will be awarded to students who attend all lectures, interact lively
and participate in discussion in class.
Grades can be improved by making critical summaries of research papers
discussed in class (10% per summary).
Absence: maximum 6 sessions, advanced notice required. Quizzes
cannot be made up.
Discussions among students and with instructor 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). Always
acknowledge any help received from other individuals. Always
fully reference material used (e.g., encyclopedia, book, paper,
journal, web site).
Books on reserve at the Love Library (LL):
Books available at the Love Library (LL):
Foundations of Constraint Satisfaction by Edward Tsang.
Artificial Intelligence, A Modern Approach (AIMA), by Russell &
Norvig. CALL number Q335 .R86 1995.
Related material from the Web:
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.
Section on "General AI Information" in "AI
Web search engines (Altavista, etc.)
Some industrial companies and start-ups implementing advanced constraint-based
systems: (listed in random order)
I2 Technologies, PeopleSoft/Red
Edwards/Numetrix, Blue Pumpkin,
Carmen Systems, Firepond,
On Time Systems Inc., etc.
Berthe Y. Choueiry