87469 - Decision Making with Constraint Programming

Academic Year 2021/2022

  • 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 in artificial intelligence to model and solve combinatorial 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. The inherent difficulty in solving such practically crucial problems has lead to the development of Constraint Programming (CP), an intelligent decision-support technology. A growing number of companies and research institutions worldwide 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 possesses the necessary skills for modelling in a CP language and solving with a CP solver.

Course contents

Prerequisites: Basic computer science courses such as discrete mathematics, logic, algorithms and data structures, programming. Prior knowledge on artificial intelligence is not necessary.

Course topics

  • Overview and successful applications of CP
  • Modeling techniques

  • Local consistency notions and constraint propagation

  • Global constraints

  • Constructive tree search algorithms, search and propagation, branching heuristics, randomization and search restarts

  • Optimization problems

  • Constraint-based scheduling

  • Heuristic search methods

  • Hybrid CP and heuristic search methods

  • Advanced topics and hot research topics in CP

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 classical problems. The teaching method consists of frontal lectures, as well as programming exercises (using personal laptops)during which we will use MiniZinc. The student is advised to download the tool and start getting familiar with it as of the beginning of the lectures. 

Assessment methods

The student's level of understanding is assessed through programming assignments and an oral exam. The programming assignments will be given during the course as part of the exercise sessions and the student is expected to finish them by the end of the course. The oral exam is based on the discussion of the course topics and will take place after the end of the course. The final grade of the course is determined in equal parts by the grades obtained from the programming assignments and the oral exam.


Teaching tools

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

Links to further information

https://virtuale.unibo.it/my/index.php?lang=en

Office hours

See the website of Zeynep Kiziltan

SDGs

Quality education Industry, innovation and infrastructure Sustainable cities

This teaching activity contributes to the achievement of the Sustainable Development Goals of the UN 2030 Agenda.