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 B5726 - 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 students will practise with CP modelling and solving using MiniZinc, and with SAT and SMT encoding using Z3, both of which are publicly available. The students are advised to download these tools and start getting familiar with them as of the beginning of the lectures.

Assessment methods

Students’ understanding of the course topics is assessed through a single in-person, paper-based written exam. If deemed necessary, the lecturers may require an additional oral exam.

During the exam, the use of books, written notes, phones, smartwatches, or any internet access is strictly prohibited. Academic misconduct will be handled in accordance with university policy.

There will be four exam sessions each academic year: the first two in July and September, and the last two in January and February. Exact dates will be announced during the course and published on AlmaEsami. To attend an exam session, students must register via AlmaEsami by the stated deadlines.

The written exam is evaluated based on the correctness and completeness of the answers. Higher grades are awarded to students who demonstrate a good command of the subject, clear and concise writing, and the ability to apply concepts to solve problems. A failing grade is assigned when responses show substantial gaps in key concepts, unclear or inappropriate expression, or flawed reasoning that compromises the validity of the solution.

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

• programing exercises

• 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