
Risorsa bibliografica obbligatoria 

Risorsa bibliografica facoltativa 

Anno Accademico

2014/2015

Scuola

Scuola di Ingegneria Industriale e dell'Informazione 
Insegnamento

093735  GRAPH OPTIMIZATION

Docente 
Carello Giuliana

Cfu 
5.00

Tipo insegnamento

Monodisciplinare

Corso di Studi 
Codice Piano di Studio preventivamente approvato 
Da (compreso) 
A (escluso) 
Insegnamento 
Ing Ind  Inf (Mag.)(ord. 270)  MI (434) INGEGNERIA INFORMATICA  *  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 
Programma dettagliato e risultati di apprendimento attesi 
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.
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 BranchandBound method and basic Cutting Plane method (Gomory cuts).
Arborescence, matching and transportation problems. Models and algorithms for arborescence, matching and transportation problems.
Flow routing and Fixed Charge Network Design problems. Classification: splittable vs unsplittable flow, single vs multiple paths, multicommodity flows, node and arc fixed costs. Connectivity. Arcbased and pathbased ILP models.
Column generation method. Dual problem and complementary conditions, pricing problem. Basic idea of Branchandprice method.
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, pcenter and pmedian problems, uncapacitated and capacitated facility location problems, single source and multiple source; location and flows: hub location. Comparison of different formulations. Valid inequalities for location problems (cover inequalities). Valid inequalities for network design and connectivity requirements. Basic idea of Branchandcut method.
Lagrangian relaxation. General framework and its application to facility location problems. Application of Lagrangian relaxation to 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.
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.

Note Sulla Modalità di valutazione 
The exam is a written test. Homeworks will be proposed during the course on the practical part (lab).

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: SpringerVerlag, 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

Nessun software richiesto 
Tipo Forma Didattica

Ore didattiche 
lezione

30.0

esercitazione

16.0

laboratorio informatico

15.0

laboratorio sperimentale

0.0

progetto

0.0

laboratorio di progetto

0.0

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

