- Docente: Michele Monaci
- Credits: 6
- SSD: MAT/09
- Language: English
- 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 Engineering Management (cod. 0936)
Second cycle degree programme (LM) in Automation Engineering (cod. 8891)
Second cycle degree programme (LM) in Telecommunications Engineering (cod. 9205)
Learning outcomes
At the end of the course the student own the knowledge of the most effective techniques for the solution of complex decisional problems arising in the optimal planning and management of large scale systems, as well as the definition of mathematical models and heuristic algorithms for the practical solution of the corresponding optimization problems.
Course contents
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, Continuous Relaxation, Branch and Bound Algorithms
- Basic heuristic approaches: Constructive algorithms and local search procedures. Examples for KP01 and TSP. Performance analysis (experimental and worst case 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:
a) “Theory” on solution algorithms for problems;
b) “Application” to specific problems
For each part there is a written exam (with no books/notes) and an oral test on the same day.
Teaching tools
The teaching material, covering all the lessons of the course, will be available at AMS campus
Office hours
See the website of Michele Monaci