91762 - Combinatorial Decision Making and Optimization

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. OR examples and exercises will be implemented in Python.

Assessment methods

The student’s level of understanding is assessed through a project work. The student will be asked to work on one single project that covers the topics of both modules. The teaching staff will propose project topics, however the student is encouraged to coordinate with the teaching staff 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 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

See the website of Roberto Amadini