Hide menu


Topics in Constraint Programming

Lectures:
24 h

Recommended for
Computer science and computer systems Ph.D. students

The course was last given:
New course

Goals
The aims of the course are (1) to survey some well-known search techniques and to discuss their use in constraint programming, (2) to discuss interval constraint approach to modeling and solving of global optimization problems (3) to discuss Oz system approach to combining constraint programming with other programming paradigms.

Prerequisites
The topics to be discussed are complementary to those discussed in the graduate course "Introduction to constraint programming" given in spring 1999. Familiarity with the material covered by the latter course may be helpful.

Organization
A seminar course. The credits will be given for preparation of the seminar presentations and for solving the homework assignments.

Contents
The topics to be discussed include:

  • the principles of Oz, a promising multi-paradigm programming language for distributed computing; we are happy to announce that Oz will be presented by Professor Seif Haridi, one of its founders,
  • interval constraint techniques that make it possible to solve nonlinear problems,
  • techniques for programming constraint solvers, constraint handling rules and indexicals,
  • advanced search techniques.
The students will have access to the programming systems based on the principles discussed: the Oz/Mozart system, the Prolog IV system and the SICStus Prolog version of Constraint Handling Rules and Indexicals. Prolog IV will be available during the course thanks to a temporary educational license granted by PROLOGia (valid only during the course).There is no other interval CLP system at IDA.

Literature
Articles and manuals (to be announced).

Teachers
Kris Kuchcinski, Jan Maluszynski, Ulf Nilsson.

Examiner
Kris Kuchcinski.

Schedule
October - December 1999.

Examination
Presentation of selected material and homework assignments. The homework assignment will be announced in October. It will include a number of programming problems. The solutions must include justifications and explanations in form of comments, and documentation of test runs. The objective is to give the student some practical experience with:

  1. the interval CLP in Prolog IV,
  2. the Oz/Mozart
  3. the constraint handling rules in SICStus Prolog.
The topics for presentation are listed here and for most of them the material is (or will be) posted at the home page. You may sign for presentation by sending a message to Kris Kuchcinski. The final assignment of presentations will be posted after the information meeting..

Credit
The course gives up to 4 credits. To get them it is necessary to

  1. prepare a joint presentation of a selected topic. At most two people can sign for one topic. The electronic version of the slides to be used at the presentation should be delivered in the week preceding the presentation.
  2. solve individually the only homework assignment (all problems), and to deliver the solution by December 8.
  3. participate in the closing session on December 15 where the programming assignment will be discussed, and to be ready to present his/her solution.
The number of credits obtained may be reduced if the above requirements are not fully satisfied.

Comments
The Oz system is installed at IDA and will be used for programming assignments. We investigate a possibility of installing a system using interval constraints. Unfortunately most of them seem to be expensive commercial products.


Page responsible: Anne Moe