Ing Ind - Inf (Mag.)(ord. 270) - CR (263) MUSIC AND ACOUSTIC ENGINEERING

*

A

ZZZZ

093735 - GRAPH OPTIMIZATION

Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI

*

A

ZZZZ

093735 - GRAPH OPTIMIZATION

Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA

*

A

ZZZZ

093735 - GRAPH OPTIMIZATION

Obiettivi dell'insegnamento

The course deals with some important network and graph optimization problems arising in several fields of application such as telecommunication, transportation and logistics. The course presents the optimization models for the different classes of problems and describes the main methods that have been proposed to tackle them.

The aim of the course is to provide students with a classification of optimization problems related to networks and other applications. Further, the course aims at providing the students with the knowledge of a wide range of optimization methods. The students will learn to model optimization problems arising in real life applications, to represent them as particular case of well known optimization problems, and to deal with them applying both exact and heuristic approaches. Beside theoretical knowledge, the course will provide practical experience in developing and applying the optimization techniques. During lab sessions, the students will be asked to apply their knowledge to deal with problems.

Risultati di apprendimento attesi

The student will know

- some of the main families of optimization problems (network design and flows, location, scheduling)

- the main heuristic methods, their features and properties

- the main relaxation approaches

- the valid inequalities and some classical examples

The student will be able to use his/her knowledge to tackle an optimization problem, i.e. the student will be able to

- identify the mathematical model underlaying an application problem

- design a heuristic approach to tackle a problem, implement it and evaluate its performance

- apply relaxation techniques and implement them to obtain a bound for a problem

- derive valid inequalities based on classical examples and implement them to improve the bound

Argomenti trattati

Introduction. Brief review of mathematical programming models for graph and network optimization problems (paths, trees, minimum cost flow, maximum flow, travelling salesman problem, knapsack problem). Brief review of the Branch-and-Bound method and basic Cutting Plane method (Gomory cuts).

Flow routing and Fixed Charge Network Design problems. Classification: splittable vs unsplittable flow, single vs multiple paths, multicommodity flows, node and arc fixed costs. Arc-based and path-based ILP models.

Column generation method. Dual problem and complementary conditions, the pricing problem.

Heuristic methods. Greedy algorithm. Local Search. Metaheuristics: tabu search, simulated annealing, variable neighborhood search. Very large scale neighborhood and ILP based neighborhood. Examples of application of heuristic methods.

Location problems. Classification: set covering and set partitioning, p-center and p-median problems, uncapacitated and capacitated facility location problems, single assignment and multiple assignment.

Valid inequalities and cutting planes. Cover inequalities for knpasack problem. Valid inequalities for network design and connectivity requirements.

Relaxation. Continuous relaxation, surrogate relaxation. Lagrangian relaxation: general framework and application to facility location problems and network design problems.

Scheduling problems. Introduction to scheduling problems. Classification: single machine scheduling with different objective functions (total weighted completion time, makespan, lateness, tardiness), parallel machines scheduling problems, flow shop, job shop. Models and algorithms for scheduling problems.

Prerequisiti

Basic knowledge of linear programming and simplex method are required

Modalità di valutazione

The exam includes a written test and a lab exam.

The written test includes:

- exercises: the student is required to apply the knowledge for solving small examples and for applying the optimization methods to a given problem

- theoretical questions on course topics with open answer: the student is required to demonstrate his/her knowledge of the optimization methods

The lab part includes homeworks: the student is required to apply the methods and implement them to solve problems

Bibliografia

R. Ahuja, T. Magnanti, J. Orlin, Network flows: Theory, Algorithms, and Applications, Editore: Prentice Hall, Anno edizione: 1993
D. Bertsekas, Network Optimization: Continuous and Discrete Models, Editore: Athena Scientific, Anno edizione: 1998
F.W.Glover, G.A.Kochenberger, Handbook of Metaheuristics, Editore: Springer-Verlag, Anno edizione: 2003
H.W. Hamacher, Z. Drezner, Facility Location: Applications and Theory, Editore: Springer, Anno edizione: 2001
B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Editore: Springer Verlag, Anno edizione: 2001
L. Wolsey, Integer Programming, Editore: Wiley, Anno edizione: 1998
M.L. Pinedo, Scheduling - Theory, Algorithms, and Systems, Editore: Springer, Anno edizione: 2008
V.J. Rayward-Smith, I.H. Osman, C.R. Reeves, G.D. Smith, Modern heuristic search methods, Editore: Wiley and Sons, Anno edizione: 1996
M. Piòro, D. Medhi, Routing, Flow, and Capacity Design in Communica- tion and Computer Networls, Editore: Elsevier, Anno edizione: 2004
S.Martello, P.Toth, Knapsack problems, Editore: Wiley, Anno edizione: 1990

Software utilizzato

Nessun software richiesto

Forme didattiche

Tipo Forma Didattica

Ore di attività svolte in aula

(hh:mm)

Ore di studio autonome

(hh:mm)

Lezione

25:00

35:00

Esercitazione

12:00

20:00

Laboratorio Informatico

11:00

0:00

Laboratorio Sperimentale

0:00

0:00

Laboratorio Di Progetto

2:00

20:00

Totale

50:00

75:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione

Insegnamento erogato in lingua
Inglese

Disponibilità di materiale didattico/slides in lingua inglese

Disponibilità di libri di testo/bibliografia in lingua inglese

Possibilità di sostenere l'esame in lingua inglese