- Docente: Daniele Vigo
- Credits: 6
- SSD: MAT/09
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
- Corso: Second cycle degree programme (LM) in Mathematics (cod. 8208)
Learning outcomes
At the end of the course the student knows the main theoretical and algorithmic methods of mathematical programming; is able to develop different mathematical models for a real problem; knows how to implement a mathematical programming algorithm to solve a real problem.
Course contents
The course includes a first part in which the main 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. elements and problems of graph 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. 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.
Finally, the definition of heuristic approaches for NP-complete problems is also discussed.
Readings/Bibliography
Slides and lecture notes of the teacher available online.
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 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 a scale 0-30.Teaching tools
lecture notes, slides and exercises available online
Office hours
See the website of Daniele Vigo
SDGs
This teaching activity contributes to the achievement of the Sustainable Development Goals of the UN 2030 Agenda.