Course Information

Announcements:
Feb 14th. First regular assignment posted.  See the Assignments link. Also relevant readings for lectures updated with a specification of the 1-UIP clause learning algorithm.

Lectures: BA2179

Instructor: Fahiem Bacchus. Room PT398B (D.L. Pratt Building). fbacchus@cs.toronto.edu, 946-7174. Home page, http://www.cs.toronto.edu/~fbacchus

Office Hours: Tuesdays 12:00-1:00 and Wednesdays 3:00-4:00 or by appointment (send e-mail).

Course Web Page: http://www.cs.toronto.edu/~fbacchus/csc2512

Outline: Reasoning about Constraints is a very active area of research within AI. One of the reasons for this is that problems involving constraints appear in many areas of AI and computer science in general, another reason is that many important practical problems involve solving constraints and thus constraint reasoning has had more of a practical impact than many other areas of AI: a number of large companies have been created that market software systems for doing constraint reasoning. Constraints and constraint reasoning has been applied to areas like computer vision, natural language processing, user interfaces, graphics, operations research, etc. In recent years SAT, which can be viewed as being a special subset of constraints has also become increasingly important in a number of application areas.

In this course you will be introduced to the basic formalism of constraints, techniques for modeling problems as constraint problems, and algorithms for solving constraint problems. By the end of the course you should be able to add constraint reasoning to the toolkit of techniques you can use to solve problems, and you should also be ready to pursue more advanced research in the area if you so choose.

Lectures and Course Evaluation: The course material will be mostly covered by lectures with some assigned readings. For those taking the course for credit your mark will be determined by (a) some homework assignments, and (c) a final project. Here is a tentative split between these components.

  1. Three to four Assignments total 40%. 
  2. Term project 60%.

Subjects to be covered (approximate)

  1. Introduction to constraints and SAT, propagation techniques including local consistency.
  2. Partial instantiation search for solving finite domain CSPs. Generic backtracking and various improvements.
  3. No-good/Clause learning learning during search and a unified view of backtracking algorithms.
  4. The relationship between resolution proofs and backtracking search.
  5. #Sat and Bayesian Inference.
  6. QBF.

Books on Constraints: Two useful textbooks on constraints are.

  1. Constraint Processing (The Morgan Kaufmann Series in Artificial Intelligence) by Rina Dechter (probably the best book currently available)
  2. Principles of Constraint Programming by Krzysztof Apt (a new book)
  3. Programming with Constraints: An Introduction by Kim Marriott and Peter Stuckey.

On the other hand this book will not tell you much about constraints as studied in this course (despite its title).

Some Interesting CSP Links:

  1. Peter van Beeks home page.
  2. Rina Dechters home page.
  3. Toby Walsh's home page.
  4. The Constraint Computation Center directed by Eugene Freuder. 
  5. The AIPS home page (an distributed constraints research group).
  6. The CSPLib page. A problem library (benchmarks) page.
  7. Ilog a originally French company also selling constraint based optimization software. (Also check out their technical papers page.)