69441 - OPTIMIZATION MODELS AND ALGORITHMS M

Conoscenze e abilità da conseguire

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.

Contenuti

The course includes a first part in which the basic concepts of Linear and Integer Programming are briefly discussed.

In particular:
1. linear programming and duality theory
2. integer linear programming and branch-and-bound
3. complexity of the algorithms
4. basics of graphs theory

The second part of the course is on the modeling, starting from the integer linear programming models for basic NP-complete problems with special emphasis on the discussion of the quality of their continuous relaxation. Finally, some more complex applications involving models with an exponential number of variables and/or constraints are discussed including the presentation of branch-and-cut and column generation techniques on some specific examples

Testi/Bibliografia

Laurence A. Wolsey, Integer Programming , Wiley, 1998.

The introduction and basics of the course can be found in
Christos H. Papadimitriou and Ken Steiglitz, Combinatorial optimization: algorithms and complexity , Dover 1998.
In particular:
Chapter 2: Linear Programming and the Simplex Algorithm
Chapter 1, Appendix: Basics and notation of Graphs
Chapter 8: Computational Complexity
Chapter 18: the Branch-and-Bound algorithm for Integer Programming

Metodi didattici

Frontal lectures and class exercises

Modalità di verifica e valutazione dell'apprendimento

The exam is aimed at evaluating the understanding of the course content.

The exam is composed by a written part in which the students are asked to answer to three open questions on the course content. The questions may include the solution of simple exercises. It is not allowed to use any written source or electronic device during the exam.

The written part is integrated by an oral discussion on the topics of the written questions and on other topics of the course.

The final evaluation is in 30.

Strumenti a supporto della didattica

lecture notes, slides and exercises available online

Orario di ricevimento

Consulta il sito web di Daniele Vigo