91762 - Combinatorial Decision Making and Optimization

Academic Year 2024/2025

  • Moduli: Zeynep Kiziltan (Modulo 1) Roberto Amadini (Modulo 2)
  • Teaching Mode: Traditional lectures (Modulo 1) Traditional lectures (Modulo 2)
  • Campus: Bologna
  • Corso: Second cycle degree programme (LM) in Artificial Intelligence (cod. 9063)

Learning outcomes

At the end of the course, the student has an understanding of the most popular methods in operations research and artificial intelligence for modeling and solving complex combinatorial optimization problems such as constraint programming, integer linear programming, SAT and SMT.

Course contents

Prerequisites

Problem solving in artificial intelligence (covered by 91248 - Fundamentals of Artificial Intelligence and Knowledge Representation), logic for computer science and basic notions of algorithms and programming preferably in Python (covered by 91251 - Languages and Algorithms for Artificial Intelligence), basic algebra and analysis.

Course topics

The first half of the course (Module 1) will introduce the fundamental concepts in Constraint Programming (CP) and Boolean Satisfiability (SAT), which are two general-purpose approaches in Artificial Intelligence (AI) to combinatorial decision making and optimization. The topics include:

  • Introduction to combinatorial decision making and optimization
  • Modelling in CP
  • Constraint propagation and global constraints
  • Constructive tree search and propagation, branching heuristics, randomization and search restarts, Large Neighbourhood Search (LNS)
  • The SAT problem and encoding in SAT
  • Basic solving techniques (resolution, unit propagation, DPLL algorithm)
  • Conflict-driven clause learning algorithms
  • SAT encodings

The second half of the course (Module 2) will introduce the fundamentals of Satisfiability Modulo Theory (SMT), which is a generalization of SAT. The last part of the module will be about essential Operations Research results from Linear Programming (LP) and in particular Integer Linear Programming (ILP), by prioritizing the width of the covered area over the depth of the introduction. The topics include:

  • Satisfiability Modulo Theories (SMT)
  • Eager vs lazy SMT encoding, the DPLL(T) algorithm
  • SMT theory solvers and combinations of theories
  • Linear Programming (LP)
  • Simplex algorithm and duality
  • Integer Linear Programming (ILP)
  • Extensions and hybrid methods

The course will also host invited lectures by pioneer researchers in the field in order to provide a broader perspective on the AI-based approaches to combinatorial decision making and optimization.

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.
  • Handbook of Satisfiability. A. Biere, M. Heule, H. van Maaren, T. Walsh (eds), IOS Press, second edition, 2021.

Teaching methods

The course combines theoretical foundations with practical modeling and solving of realistic problems. The main teaching methods are frontal lectures, including practical exercises, and hands-on experience using personal laptops.

The student will practise with CP modelling and solving using MiniZinc, and with SAT and SMT encoding using Z3, both of which are publicly available. The student is advised to download these tools and start getting familiar with them as of the beginning of the lectures.

Assessment methods

The student’s level of understanding is assessed through a project work and possibly a written/oral exam. The project and the exam will cover the topics of both modules. The lecturers will propose a project topic, however the student is encouraged to coordinate with the lecturers on their own project proposal. Working as a group of 2-4 students is a possibility, depending on the complexity of the projects.

Teaching tools

The course has an inclusive structure to facilitate distance learning. The teaching activity heavily relies on the use of the Virtuale platform for the following purposes:

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

  • communication between the students and the teaching staff

  • discussion of course topics

  • discussions on the project work

  • working on programing exercises interactively

  • exchange of feedback

  • participation to polls and informal quiz

Links to further information

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

Office hours

See the website of Zeynep Kiziltan

See the website of Roberto Amadini

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.