CSCE421/821, Fall 2004: 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. This year, we are planning on having 1
academic visitor and 2 industrial visitors. 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: Monday, Wednesday, and Friday from 10:30 a.m. to 11:20
a.m.
Location: Avery 111
Recitation: Wednesday, from 5:00 p.m. to 6:00 p.m.
Location: 
Avery 20
Instructor: Berthe Y. Choueiry
Room 123B, Avery 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: Yaling Zheng
email:
yzheng@cse.unl.edu
Office location: Avery, Room 123D
Office hours:
Tuesday & Thursday from 5:00-6:00 p.m.
RA: Joel Gompert
email:
jgompert@cse.unl.edu
Office location: Avery, Room 123D
Office hours:
Monday from 5:00-6:00 p.m.
Q&A: For quick response, email cse421@cse.unl.edu. Your
message will be forwarded to the TA, GRAs, and instructor.
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. (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. 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
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.
- Textbook "Constraint Processing" by
Rina Dechter, 1st edition. The textbook will not be
followed sequestially, but should be used for reference.
- 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 8 sessions (including 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: 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 2 presentations per
student. Presentations must be made before December 1st,
2004.
- Make a critical summary of research papers/topics discussed in
class: 5% per summary. Maximum 4
summaries per student. Deadline for submitting summaries December
1, 2004.
- Write a chapter of a textbook: 20% per chapter. Maximum 2 chapters per student. Deadline for
submitting chapter write-ups December 1, 2004.
- Do the weekly and final glossaries: maximum 10%. Deadline for submitting final glossary December 5,
2004.
- Bonuses will be awarded to students who attend all lectures,
interact lively, and participate in discussion in class.
Grade conversion:
|
97% |
A+ |
|
94-96 |
A |
|
90--93 |
A- |
|
87--89 |
B+ |
|
84--86 |
B |
|
80--83 |
B- |
|
75--79 |
C+ |
|
67--74 |
C |
|
60--66 |
C- |
|
57--59 |
D+ |
|
54--56 |
D |
|
51--53 |
D- |
|
<=50 |
F |
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:
CP On Line.
Some industrial companies and start-ups implementing advanced constraint-based systems: (listed in random order)
- COSYTEC, I2 Technologies, PeopleSoft/Red Pepper, Blue Pumpkin, Ilog, Trilogy, Parc Technologies Ltd, Carmen Systems, Firepond, On Time Systems Inc., ConfigWorks.,
etc.
Courses:
Groups:
Archives and on-line systems:
Main publication venues:
Additional resources:
- Lisp resources
- Latex resources
Berthe Y. Choueiry
Last modified: