81675 - CONSTRAINT PROGRAMMING

Academic Year 2017/2018

  • Teaching Mode: Traditional lectures
  • Campus: Bologna
  • Corso: Second cycle degree programme (LM) in Computer Science (cod. 8028)

Learning outcomes

This course covers the fundamental methods of CP technology, in the areas of artificial intelligence and operations research, to model and solve constraint optimization problems. Constraint optimization problems are about taking optimal decisions in the presence of many complex constraints. Such problems appear often in various domains of science, business and industry, a few examples being resource allocation in a data centre, product configuration in e-commerce and scheduling of an assembly line in a factory. The inherent difficulty in solving practically crucial problems such as these has lead to the development of Constraint Programming (CP) technology. Many companies, including IBM and Oracle, and research centers around the world successfully apply this technology and contribute to its advancement. For instance, the Rosetta/Philae mission launced by the European Space Agency was scheduled and contorolled using CP (http://www.a4cp.org/node/1058). Knowledge acquired in this topic is therefore a valuable asset on the job market. At the end of the course, the student has an understanding of the advanced modelling techniques and efficient solution methods, and develops skills in modelling in a CP language and solving with a CP solver. The course combines theoretical foundations with practical modelling and solving of realistic problems.

Course contents

Introduction to constraint programming.
Modeling techniques.
Local consistency notions.
Constraint propagation algorithms.
Global constraints.
Constructive tree search algorithms.
Optimization.
Constraint based scheduling.
Heuristic search methods.
Hybrid search methods.
Hybrid operations research and CP methods.

Readings/Bibliography

  1. Lecture notes and bibliography of scientific articles provided by the teacher.
  2. Handbook of Constraint Programming. F. Rossi, P. van Beek, T. Walsh (eds), Elsevier Science, 2006.
  3. Hybrid Optimization. M. Milano and P. van Hentenryck (eds), Springer, 2011.

Teaching methods

The course combines theoretical foundations with practical modeling and solving of realistic problems. The teaching methods consists of lectures and programming exercises.

Assessment methods

The student's level of understanding is assessed through a project work and an oral exam. The project focusses on the application of the techniques presented during the course to solve a constraint (optimization) problem or the presentation of a research article. The oral exam is based on the discussion of the course topics.

Teaching tools

The lectures are given by using slides which will be available in the AMS Campus website.

Office hours

See the website of Zeynep Kiziltan