logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2015/2016
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 093735 - GRAPH OPTIMIZATION
Docente Grosso Andrea Cesare
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 (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, 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. 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
Risorsa bibliografica facoltativaR. Ahuja, T. Magnanti, J. Orlin, Network flows: Theory, Algorithms, and Applications, Editore: Prentice Hall, Anno edizione: 1993
Risorsa bibliografica facoltativaD. Bertsekas, Network Optimization: Continuous and Discrete Models, Editore: Athena Scientific, Anno edizione: 1998
Risorsa bibliografica facoltativaF.W.Glover, G.A.Kochenberger, Handbook of Metaheuristics, Editore: Springer-Verlag, Anno edizione: 2003
Risorsa bibliografica facoltativaH.W. Hamacher, Z. Drezner, Facility Location: Applications and Theory, Editore: Springer, Anno edizione: 2001
Risorsa bibliografica facoltativaB. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Editore: Springer Verlag, Anno edizione: 2001
Risorsa bibliografica facoltativaL. Wolsey, Integer Programming, Editore: Wiley, Anno edizione: 1998
Risorsa bibliografica facoltativaM.L. Pinedo, Scheduling - Theory, Algorithms, and Systems, Editore: Springer, Anno edizione: 2008
Risorsa bibliografica facoltativaV.J. Rayward-Smith, I.H. Osman, C.R. Reeves, G.D. Smith, Modern heuristic search methods, Editore: Wiley and Sons, Anno edizione: 1996
Risorsa bibliografica facoltativaM. Piòro, D. Medhi, Routing, Flow, and Capacity Design in Communica- tion and Computer Networls, Editore: Elsevier, Anno edizione: 2004
Risorsa bibliografica facoltativaS.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.6.9 / 1.6.9
Area Servizi ICT
04/12/2021