Annnouncements:
the page will be regularly updated. Check it out regularly for announcements of required/recommended reading material, homework, etc.
General Information
Prereq: Instructor's permission
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 goal of this course is to prepare students to conduct research in this area. The course will be intensive and will require thorough study of the theory and the algorithms, and a significant implementation effort. Students are expected to be self motivated, and demonstrate intellectual independence and collegial collaboration.
Lectures: Monday, Wednesday, Friday, 3:30 p.m. to 4:20 p.m.
Location: AvH 110.
Make-up Class/Recitation: Wednesday, from 4:30--5:20 p.m.
Location: AvH 110.
Instructor: Prof. Berthe Y. Choueiry
Office
hours: Monday/Friday 4:30-5:30 p.m. or by
appointment
Zoom meeting room
Undergrad TA's:
- Khang Nhat Phan. Office hour: Fridays 12:00 p.m.--1:00 p.m., Zoom meeting room
- Denis Komissarov. Office hour: Tuesdays 3:30 p.m.--4:30 p.m., Zoom meeting room
Textbook:
"Constraint Processing" by Rina Dechter,
1st edition. The textbook will not be followed
sequentially, but should be used for reference.
We keep a wiki page for errata and typos in the book.
For a quick response, send your questions to Piazza. Your message will be read by the TA and the instructor and they will respond to you ASAP.
Communications:
- Course WebPage: You can access all information about the course from the course WebPage. Check the course "Schedule" to prepare for each class.
- Canvas: Grades are posted on Canvas. Check them regularly and alert us about grading errors within 7 calendar days.
- Piazza: For a quick response, send your questions to Piazza. Your message will be read by the GTAs and the instructor and they will respond to you ASAP.
- Handin: All homework, projects, reports, etc. must be submitted via the handin system of CSE.
- Wiki: You can upload the Excel file of the results of your homework on the wiki and check the results of others so that you can debug your code.
- Anonymous Suggestion Box: You may also choose to drop us a note in the Anonymous Suggestion Box to express any opinion about the course. (You can do it also via Piazza.)
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.
- Lecoutre's e-textbook on Constraint Networks (available from UNL's libaries)
- Edward Tsang, Foundations of Constraint Satisfaction. Also, available from instructor and on reserve at the Math Library in Avery Hall.
- Technical papers given by instructor or available from the Electronic Reserve at the Love Library.