Strumenti Utente

Strumenti Sito


magistraleinformaticanetworking:mor:start

Metodi di ottimizzazione delle reti (MOR)

Docente (teacher): Maria Grazia Scutellà

Informazioni generali (info)

Obiettivi

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”.

Objectives

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.

Orario delle lezioni
Giorno Orario Aula
Lunedì 14–16 L1
Giovedì 16–18 C
Lesson timetable
Day Time Room
Monday 14–16 L1
Thursday 16–18 C
Orario di ricevimento
Giorno Orario Aula
Mercoledì 14:30–17:30 Studio docente
su appuntamento via e-mail
Question time
Day Time Room
Wednesday 14:30–17:30 Teacher office
by appointment via e-mail
Programma

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
Programme

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
Modalità di esame

Prova orale

Examination

Oral examination

Testi di riferimento (textbooks)

  • 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 delle lezioni (2014/2015)

Appunti (notes)

Typos

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

magistraleinformaticanetworking/mor/start.txt · Ultima modifica: 19/02/2016 alle 09:10 (15 mesi fa) da Maria Grazia Scutellà