35192 - Resources Optimization M

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

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