- Docente: Daniele Vigo
- Credits: 6
- SSD: MAT/09
- Language: English
- Moduli: Daniele Vigo (Modulo 1) Michele Monaci (Modulo 2)
- Teaching Mode: Traditional lectures (Modulo 1) Traditional lectures (Modulo 2)
- Campus: Bologna
-
Corso:
Second cycle degree programme (LM) in
Telecommunications Engineering (cod. 9205)
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 Electrical Energy Engineering (cod. 8611)
Learning outcomes
Integer Programming is a very powerful tool for modeling combinatorial optimization problems arising in many branches of engineering, industry and resource allocation. The first part of this 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 discusses real-world applications. Note: This course is taken from the Second-cycle Degree in Ingegneria Gestionale.
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.
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
Lectures and modelling exercises in class
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. The students who get a positive evaluation must contact the teacher for the registration of the mark.
Teaching tools
lecture notes available in ams campus
Office hours
See the website of Daniele Vigo
See the website of Michele Monaci