Risorse bibliografiche
 Risorsa bibliografica obbligatoria Risorsa bibliografica facoltativa
 Scheda Riassuntiva
 Anno Accademico 2017/2018 Scuola Scuola di Ingegneria Industriale e dell'Informazione Insegnamento 093735 - GRAPH OPTIMIZATION Cfu 5.00 Tipo insegnamento Monodisciplinare Docenti: Titolare (Co-titolari) Carello Giuliana

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI*AZZZZ093735 - GRAPH OPTIMIZATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA*AZZZZ093735 - 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 Branch-and-Bound method and basic Cutting Plane method (Gomory cuts).  Arborescence and transportation problems. Models and algorithms for arborescence and transportation problems. Dynamic Programming for the Knapsack problem. 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. Arc-based and path-based ILP models. Column generation method. Dual problem and complementary conditions, pricing problem. Basic idea of Branch-and-price 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, p-center and p-median 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 Branch-and-cut 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).

 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

 Mix Forme Didattiche
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
 schedaincarico v. 1.10.0 / 1.10.0 Area Servizi ICT 23/07/2024