CSCE990-05, Fall 2000: Foundations of Constraint Satisfaction

Constraint course challenge: the best student (ties broken by lottery) will be
awarded attendance of a major international conference in the field. Details in class.

Special announcement: we are working on inviting two important researchers
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 systems).

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.

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

Place: Room 111, Ferguson Hall

Instructor:   Berthe Y. Choueiry
                      Room 104, Ferguson Hall,
                      choueiry@cse.unl.edu, tel: (402)472-5444.
                      Office hours: Mon/Wed from 11:30 a.m. to 12:30 p.m., or by appointment.

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.
Theoretical and empirical classification of backtracking algorithms.
Theoretical and empirical of classification of static and dynamic ordering heuristics.
Phase transition.
Global and local consistency: algorithms, properties, and computational complexity.
Islands of tractability for minimality and global consistency.
Modeling and reduction methods between representations.
Decomposition.
Symmetries and their approximations.
Reformulation and abstraction.
Extension: Dynamic/conditional constraint satisfaction, constraint optimization.

Support:

Edward Tsang, Foundations of Constraint Satisfaction. Available from instructor.
Rina Dechter, Constraint Processing. In preparation, check with instructor.
Technical papers given by instructor or available from the Electronic Reserve at the Love Library.

Grading policy:

Grades will be allocated as follows

Quizzes: 20%
Assignments: 30%
Paper presentation: 20%
Project: 30%

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).

Rules:

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).

Grade conversion:

>94%	A+
90--94	A
85--89	B+
80--84	B
70--79	C+
60--69	C
55--59	D+
50--54	D
<=50	F

Books on reserve at the Love Library (LL):

Foundations of Constraint Satisfaction by Edward Tsang.

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.
Section on "General AI Information" in "AI Resources."
Web search engines (Altavista, etc.)

Related material from the Web:

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

I2 Technologies, PeopleSoft/Red Pepper, J.D. Edwards/Numetrix, Blue Pumpkin, Calico, Ilog, Trilogy, COSYTEC, Parc Technologies Ltd, Carmen Systems, Firepond, On Time Systems Inc., etc.

Courses:

Constraint Programming: online textbook by Roman Barták.
Reasoning Methods in AI (CS329A): course by Pandu Nayak.
Tutorial on Constraint Programming, by Barbara Smith.
Lecture notes by David McAllester.

Groups:

LIA@EPFL
APES Group in the UK.
Constraint Computation Center of Freuder in Univ. of New Hampshire.

Archives:

Constraints archives at CCC.
CSPLib: Problem Library on the Web.
Random generator at LIRMM
Random generator by Patrick Prosser

Conferences:

Constraint Programming (CP), The Practical Application of Constraint Technology Conferences (PACT), AAAI, IJCAI, ECAI, FLAIRS,

Berthe Y. Choueiry

Last modified: