87469 - Decision Making with Constraint Programming

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 Constraint Programming (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

• Lecture slides and bibliography of scientific articles provided by the teaching staff.
• Handbook of Constraint Programming. F. Rossi, P. van Beek, T. Walsh (eds), Elsevier Science, 2006.
• 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 students are advised to download the tool and start getting familiar with it as of the beginning of the lectures.

Assessment methods

Students' 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 must be completed by the end of the course. The oral exam consists of a discussion on the course topics. The final grade, ranging from 18 to 30L, is equally weighted between the programming assignments and the oral exam. 

Oral exams will be held after the course concludes, during the January–February exam period. Students who receive an insufficient evaluation or choose to reject their grade will have the opportunity to retake the exam during the June–July session. The exact dates will be announced during the course and published on the Virtuale platform and AlmaEsami.

Teaching tools

The course has an inclusive structure to facilitate distance learning, relying on the use of the Virtuale platform for the following teaching activities:

• distribution of the course material (lecture slides, lecture recordings, resources, etc)

• communication between the lecturer and the students

• discussion of course topics

• working on programing exercises interactively

• exchange of feedback

• participation to polls and informal quiz

Links to further information

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

Office hours

See the website of Zeynep Kiziltan