87469 - DECISION MAKING WITH CONSTRAINT PROGRAMMING

Learning outcomes

This course covers the fundamental methods in artificial intelligence and operations research, to model and solve problems requiring to take (optimal) decisions in the presence of many complex constraints. Such problems appear often in diverse domains of science, business and industry, a few examples being DNA and protein sequence alignment in biology, routing of vehicles in a logistics company, 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 which is now widely used as a component in various intelligent systems to support decision making. For instance, the Rosetta/Philae mission launced by the European Space Agency was scheduled and controlled using CP (http://www.a4cp.org/node/1058). Many companies, including IBM, Oracle and Google, and research institutions around the world successfully apply CP technology and contribute to its advancement. Skills in this area are therefore in high demand in the job market. The course combines theoretical foundations with practical modelling and solving of realistic problems. 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.

Course contents

• Overview and successful applications of CP

• Modeling techniques

• Local consistency notions and constraint propagation

• Global constraints

• Constructive tree search algorithms and branching heuristics

• Optimization

• Constraint-based scheduling

• Heuristic search methods

• Hybrid search methods

• Hybrid operations research and CP methods

Readings/Bibliography

1. Lecture slides and bibliography of scientific articles provided by the lecturer.
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 consist of frontal lectures and programming exercises (personal laptops would be recommended).

Assessment methods

The student's level of understanding is assessed through a project work and an oral exam. The project focuses on the application of the techniques presented during the course to solve a constraint satisfaction or optimization problem. The lecturer will propose a project topic, however the students are encouraged to coordinate with the lecturer on their own project proposals. The oral exam is based on the discussion of the course topics.

Teaching tools

The lectures are given by using slides which will be made available on the IOL platform.

Links to further information

https://iol.unibo.it/?lang=en

Office hours

See the website of Zeynep Kiziltan