- Docente: Paolo Paronuzzi
- Credits: 6
- SSD: MAT/09
- Language: English
- Moduli: Paolo Paronuzzi (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 Engineering Management (cod. 0936)
-
from Feb 22, 2023 to May 05, 2023
-
from May 10, 2023 to Jun 09, 2023
Learning outcomes
The objective of the course is to present the most effective techniques for the solution of complex decisional problems arising in the optimal planning and management of large scale systems concerning both the public and the private sectors.
Mathematical models and heuristic algorithms for the practical solution of the corresponding optimization problems will be described.
Particular attention will be given to the algorithmic and implementation aspects.
Applications of the proposed techniques to real-world problems will be presented and analyzed.
Course contents
Requirements/Prior knowledge
Students are supposed to have a basic knowledge on Operations Research, as well as on the implementation of computer codes and on complexity theory.
Fluent spoken and written English is a necessary pre-requisite as all lectures and material will be in English.
Course Contents
- Basic Integer Programming Optimization: Integer Programming Models, Formulations, Relaxations.
- Basic heuristic approaches: Constructive algorithms and local search procedures. Examples for KP01 and TSP.
- Worst-case performance analysis.
- Metaheuristics: Multistart, Tabu Search, Simulated Annealing, Genetic Algorithms, Iterated Local Search, Variable Neighborhood Search, Large Neighborhood Search, Ruin and Recreate, Ant Systems.
- Optimization on graphs: shortest path, minimum spanning tree, maximum flow.
- Heuristic and metaheuristic algorithms for difficult combinatorial optimization problems.
- Real-World applications.
Readings/Bibliography
Recommended
slides available online
Useful references
S. Martello, P. Toth, Knapsack Problems: Algortihms and Computer Implementations, J. Wiley, 1990.
E.Aarts, J.K. Lenstra (editors), Local Search in Combinatorial Optimization, J.Wiley, 1997.
G. Gutin, A. Punnen (editors), The Traveling Salesman Problem and Its Variations, Kluwer, 2002.
P.Toth, D. Vigo (editors), The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, 2002.
C. Barnhart, G. Laporte (editors), Transportation, Handbooks in Operations Research and Management Science, North Holland, 2007.
Teaching methods
The course consists of class lectures that concern both the theoretical aspects and the practical application of the algorithms.
Assessment methods
The exam includes two main parts.
For each part there is a written exam (with no books/notes) and, possibly, an oral test on the same day.
Students must register for the exam on Almaesami.
Teaching tools
All teaching material used during the course will be available to the students on Virtual Learning Environment.
Lessons will not be recorded.
Office hours
See the website of Paolo Paronuzzi
See the website of Michele Monaci