- Docente: Daniele Vigo
- Credits: 6
- SSD: MAT/09
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
-
Corso:
Second cycle degree programme (LM) in
Electrical Energy Engineering (cod. 8611)
Also valid for Second cycle degree programme (LM) in Electronic Engineering (cod. 0934)
Second cycle degree programme (LM) in Automation Engineering (cod. 8891)
Second cycle degree programme (LM) in Telecommunications Engineering (cod. 9205)
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
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
Readings/Bibliography
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
Teaching methods
Frontal lectures and class exercises
Assessment methods
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.
Teaching tools
lecture notes, slides and exercises available online
Office hours
See the website of Daniele Vigo