Annnouncement:

We will host:

  • Professor Rina Dechter from UC-Irvine on April 1st and 2nd 2009, a CP pioneer and the author of our textbook.
  • Dr. Ben Thengvall from OptTek Systems Inc. (Omaha) who uses CP in industrial and defense projects.
Check the list of previous visitors.

Class schedule: the page will be regularly updated. Check it out regularly for announcements of required/recommended reading material, homework, etc.

General Information

Prereq: CSCE2235, Discrete Sctrucutures (exceptionally this year).

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, Friday from 12:30 p.m. to 1:20 p.m.
Location: Avery Hall, Room 118.

Make-up Class/Recitation: Wednesday from 5:00 p.m. to 5:50 p.m.
Location: Avery Hall, Room 118.

Instructor:   Prof.  Berthe Y. Choueiry
      Office location: Room 360, Avery Hall,
      choueiry AT cse.unl.edu, tel: (402)472-5444.
      Office hours: Monday/Wednesday 1:30-2:30 p.m. or by appointment.

GTA:   Mr. Shant Karakashian
      email: shantk AT cse.unl.edu
      Office location: Room 123D, Avery Hall
     Office hours: @ Student Resource Center on Tuesdays 2:00--3:00 p.m. and Thursday 11:00a.m.--12:00 p.m. or by appointment.

Textbook:
"Constraint Processing" by Rina Dechter, 1st edition. The textbook will not be followed sequentially, but should be used for reference.

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

Important note: The GTA allocated to this class does not have extensive experience in the subject matter and will mainly help with administrative matters. All questions will have to be made to the instructor during office hours, make-up class, by email, or by appointment. We will follow a `peer-correction system' by which students grade each other's (glossaries and) homework with help from the TA and under close monitoring by the instructor.

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 Math Library in Avery.
  • Technical papers given by instructor or available from the Electronic Reserve at the Love Library.

Last modified: Mon Mar 23 11:49:58 CDT 2009