Metodi di ottimizzazione delle reti (MOR)

Docente (teacher): Maria Grazia Scutellà

Obiettivo del corso è presentare le principali tecniche di modellazione e le principali metodologie algoritmiche che si presentano a livello di progetto e gestione di reti di comunicazione. Attraverso la descrizione di rilevanti problemi di progetto e gestione di reti di comunicazione, quali QoS routing, problemi di location, e problemi di resiliency e robustezza, vengono infatti presentate tecniche di modellazione e metodologie risolutive, sia per taluni problemi di base che per problemi “NP-Hard”.

The aim of the course is to present the main modelling techniques and the main algorithmic methodologies for managing communication networks, both at the design and at the operational level. Specifically, we describe modelling techniques and algorithmic approaches, for basic and NP-Hard problems, and we apply them to relevant design and operational problems in communication networks, such as QoS routing problems, location problems, and resiliency and robustness problems.

Flussi su rete

• Flusso di costo minimo: algoritmi di base
• Flussi di tipo “multicommodity”

Metodi di ottimizzazione (per Network Design)

• Formulazioni: ottimalità, rilassamenti e bound
• Algoritmi di Branch and Bound
• Disuguaglianze valide
• Algoritmi di Piani di Taglio (Cutting Plane)
• Dualità Lagrangiana
• Algoritmi basati su generazione di colonne

Modelli e metodi avanzati di Network Design

• Location e topological design
• Reti con shortest-path routing
• Restoration e protection di reti (resiliency)
• Applicazione di tecniche di ottimizzazione per restoration e protection

Network flows

• Minimum cost flow: basic algorithms
• Multicommodity flows

Optimization methods (for Network Design)

• Formulations: optimality, relaxations and bounds
• Branch and Bound algorithms
• Valid inequalities
• Cutting Plane algorithms
• Lagrangean Duality
• Column generation

Advanced models and methods for Network Design

• Location and topological design
• Shortest-path routing
• Restoration and protection (resiliency)
• Optimization techniques for restoration and protection

Prova orale

Oral examination

• R.K. Ahuja, T.L. Magnanti, J.B. Orlin. Network flows. Theory, algorithms and applications, Prentice Hall, New Jersey, 1993. Chapters to study: Chapters 1, 2, 3 (3.5), 9 (9.1, 9.3 (Negative cycle optimality conditions and Reduced cost optimality conditions), 9.6, 9.7), 17 (17.1, 17.3 (no Theorem 17.1), 17.4 (until page 664, rows 1-8), 17.5, 17.6, 17.7 (until page 677 included))
• L.A. Wolsey. Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, 1998. Chapters to study: Chapters 1, 2, 7 (except 7.5), 8 (except 8.7 and 8.8), 10
• M. Pioro, D. Medhi. Routing, Flow and Capacity Design in Communication and Computer Networks, Elsevier, 2004. Chapters to study: Chapters 4 (4.1, 4.2, 4.3, 4.4 (no proofs of NP-Completeness)), 6 (6.1, 6.3.2, 6.3.3, 6.3.4 (except model D/TNLLP2), 6.3.5 (just to read), 6.4.1), 7 (7.1, 7.2.1, 7.3.1), 9 (9.1, 9.2, 9.3 (except formulations at pages 370 and 375), 9.4 (9.4.1,9.4.2,9.4.3,9.4.4(until constraints (9.4.6)),9.4.5,9.4.6)), 10 (10.1.1, 10.1.4, 10.2.1)

Registro di MOR

page 59 (alg_lagr_dual): in point 2) it is lambda_j instead of lambda_k

page 26 (branch_and_bound): in the last figure, the cost of the arc (2,5) is 3 instead of 1