Saarland University
Computer Science
Programming Systems
Teaching
Constraint Programming


Main page

Constraint Programming

Seminar, 9 credit points
(may also be credited as Proseminar)

Winter term 2004/2005

Prof. Gert Smolka, Marco Kuhlmann, Lutz Straßburger, Guido Tack
Programming Systems Lab, Department of Computer Science, Saarland University

Abstract

Constraints are everywhere: most computational problems can be described in terms of restrictions imposed on the set of possible solutions, and constraint programming is a problem-solving technique that works by incorporating those restrictions in a programming environment. It draws on methods from artificial intelligence, logic programming and operations research, and has been successfully applied in a number of fields such as scheduling, computational linguistics and computational biology.

The seminar will mainly be based on material from the following books and additional research papers:

• Krysztof R. Apt. Principles of Constraint Programming. Cambridge University Press, 2003.
• Rina Dechter. Constraint Processing. Morgan Kaufmann, 2003.
• Kim Marriott, Peter Stuckey. Programming with Constraints: An Introduction. MIT Press, 1998.

Organisation

The seminar will be split into two parts: a reading group, which will be held on four occasions during lecture time (October–February), and a series of talks, which will be held at the end of the term (April).

Participants, Talks, and Schedule

Assessment

To obtain the credit points assigned to this course, you have to meet the following requirements:

• presence in the reading group and at all talks
• talk (25 minutes, plus discussion)
• extended abstract (10–15 pages, electronically submitted)

For your grade, we will weigh your talk (50%), your paper (30%) and your participation in the discussion (20%).

Reading and Discussion Group

All meetings take place in building 45, room 528.

• Meeting 1 (Wednesday, November 24, 2004, 17:15): Apt, chapters 1 and 2
• Meeting 2 (Thursday, December 16, 2004, 18:00): Finite Domain Constraint Programming in Oz. A Tutorial.
• Meeting 3 (Monday, January 17, 2005, 18:00): Apt, chapter 3

Important Dates and Deadlines

• (before) March 8: first meeting with your supervisor
• (before) March 18: discuss first complete version of your slides with your supervisor
• (before) April 4: send us a complete version of your "extended abstract" (paper)
• April 5-6: talk sessions
  • Tuesday: 9:30-12:00 (3 talks), 13:30-16:00 (3 talks)
  • Wednesday: 9:30-12:00 (3 talks), 13:30-15:15 (2 talks)
  Talks will be in the same order as on the list of topics.
• April 15: final version of the paper

Style Guidelines for the Paper

Please use the Springer LNCS style for your paper. The final version should be no longer than 15 pages (including abstract and references). You find the style templates and formatting instructions for both Microsoft Word and LaTeX on the Springer web site.