69441 - OPTIMIZATION MODELS AND ALGORITHMS M

Academic Year 2019/2020

Learning outcomes

The goal of the course is to deal with Integer Programming that is a very powerful tool for modeling combinatorial optimization problems arising in many branches of engineering, industry and resource allocation. The first part of the course covers the modeling aspects of the field, providing the tools for constructing effective mathematical models, i.e., models that can be solved in practice. The second part is devoted to the algorithmic aspects: basic algorithms are reviewed and more sophisticated ones, useful for those models characterized by a large number of variables and/or constraints, are presented in detail. Finally, the third part of the course discusses real-world applications. At the end of the course students are able to formalize a combinatorial problem taken for the real life and run specific tools and algorithms for solving it in practice.

Course contents

Requirements: a good knowledge of the basics of set theory, and vectorial and matricial calculus is required.

The course is given in English: slides and exercises are in English. The exam must be taken in English.

The course focuses on optimization problems arising in decision making, with particular emphasis on Combinatorial Optimization problems. The first goal of the course is to teach the theory of Linear Programming and Integer Linear Programming, and how to formulate mathematical models for optimization problems belonging to these classes. The classical Integer Linear Programming problems are also presented. The second goal is to teach exact and heuristic algorithms to solve these problems. In addition, the basics of computational complexity of problems and algorithms are introduced, and graph theory concepts and the classical problems modelled on graphs are described. The last part of the course is dedicated to practical applications: more complex real-world optimization problems are presented and the use of optimization tools is shown.

Readings/Bibliography

Slides on IOL (Insegnamenti On Line)

Further readings:
Christos H. Papadimitriou and Ken Steiglitz, Combinatorial optimization: algorithms and complexity. Dover, 1998.

D. Bertsimas and J. Tsitsiklis, Introduction to linear programming. Dynamic Ideas and Athena Scientific, Belmont, Massachusetts, 2008.

D. Bertsimas, D. and R. Weismantel, Optimization over integers. Dynamic Ideas, Belmont, Massachusetts, 2005.

Teaching methods

The course consists of lectures and class exercises.

Assessment methods

For the online exam assessment refer to section News:

https://www.unibo.it/sitoweb/valentina.cacchiani/news/983eb8eb

The exam consists of a written test in which some exercises have to be solved and some questions on the course content have to be answered. After the written test, an oral discussion covering topics of the written test and other topics of the course completes the exam.

Teaching tools

Optimization software tools

Office hours

See the website of Valentina Cacchiani