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 Module 1 of 91248 - Fundamentals of Artificial Intelligence and Knowledge Representation), logic for computer science (covered by Module 1 of 91251 - Languages and Algorithms for Artificial Intelligence), basic notions of algorithms and programming preferably in Python (covered by 91256 - Introduction to Algorithms and Programming), basic algebra and analysis.

Course topics

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

• Introduction to CP
• 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
• SAT encodings
• Basic solving techniques (resolution, unit propagation, DPLL)
• Conflict-driven clause learning algorithms

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

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

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

Readings/Bibliography

1. Lecture slides and bibliography of scientific articles provided by the lecturers.
2. Handbook of Constraint Programming. F. Rossi, P. van Beek, T. Walsh (eds), Elsevier Science, 2006.
3. Handbook of Satisfiability. A. Biere, M. Heule, H. van Maaren, T. Walsh (eds), IOS Press, 2009.
4. Linear Programming: Foundations and Extensions. Robert J. Vanderbe, Kluwer, 1998. 
   

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 lecturers will propose project topics, however the student is encouraged to coordinate with the lecturers on his/her own project proposals. Working as a group of 2-3 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