91762 - Combinatorial Decision Making and Optimization

Academic Year 2020/2021

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 (derivatives, Jacobians, dot products).

Course topics

The first half of the course (Module 2) will introduce several essential operations research results from linear, nonlinear, integer and combinatorial optimization, privileging the width of the covered area over the depth of the introduction. The topics include:

• Lagrange, Farkas and Karush–Kuhn–Tucker

• Gradient descent, Newton and Quasi-Newton methods

• Linear programming, weak and strong duality

• Simplex algorithm, basic feasible solutions, reduced problem and reduced cots

• Integer Linear Programming (ILP) and ILP heuristics

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

• Modelling in CP

• Constraint propagation and global constraints

• Constructive tree search and propagation, branching heuristics, randomization and search restarts

• The SAT problem and encoding in SAT

• Basic solving techniques (resolution, unit propagation, DPLL)

• Conflict-driven clause learning algorithms

• Satisfiability Modulo Theories (SMT)

The module will also host a seminar 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. M.S. Bazaraa, J.J. Jarvis e H.D. Sherali. Linear programming and network flows. Wiley, 2010
3. L. A. Wolsey. Integer Programming. Wiley, 1998.                  
4. C. H. Papadimitriou and K. Steiglitz. Combinatorial optimization: algorithms and complexity. Dover, 1998.
5. Handbook of Satisfiability. A. Biere, M. Heule, H. van Maaren, T. Walsh (eds), IOS Press, 2009.
6. Handbook of Constraint Programming. F. Rossi, P. van Beek, T. Walsh (eds), Elsevier Science, 2006.

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.

During Module 1, 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. During Module 2, all 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 project for each of the two modules of the course. 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 students is a possibility, depending on the complexity of the projects. The final grade of the course is determined in equal parts by the grades obtained in the two modules.

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 Vittorio Maniezzo