Questo insegnamento presenta contenuti di tipo sia metodologico sia applicativo. In particolare, scopo del corso è fornire agli studenti gli strumenti teorici e le metodologie proprie della ricerca operativa, mostrando quindi la loro applicazione al progetto di reti di computer La ricerca operativa mette infatti a disposizione potenti metodologie matematiche (modelli matematici, algoritmi e software) per la soluzione di problemi complessi di ottimizzazione, ovvero, di minimizzazione (o massimizzazione) di funzioni di costo (profitto), soggette a vincoli. Il corso fornisce le conoscenze degli strumenti più adatti a risolvere i problemi proposti per il progetto di reti di computers. Il corso presenta laboratori in cui gli studenti saranno chiamati a mettere in pratica le metodologie apprese a lezione.

Il corso prevede forti contenuti metodologici. Gli studenti approfondiranno la conoscenza di strumenti e metodologie per la soluzione di problemi di ottimizzazione lineare continua e di ottimizzazione combinatoria. Gli studenti impareranno a costruire modelli matematici per la rappresentazione di problemi di ottimizzazione dei tipi sopraddetti. Dopo l’analisi della complessità computazionale dei problemi di ottimizzazione, verranno studiati i metodi di soluzione di tali problemi. Particolare attenzione verrà data ai metodi euristici di ricerca locale, alle meta-euristiche ed alle più recenti math-euristiche. Inoltre, saranno studiati i problemi di flusso in grafi. Verranno, infine considerati alcuni dei problemi specifici che tipicamente si incontrano nella progettazione di una rete di computer, come ad esempio: pianificazione della capacità di infrastruttura, l'ottimizzazione dei percorsi, la definizione del massimo flusso che può essere trasportato. La modellazione e la soluzione di problemi di progetto permetterà agli studenti di affinare la loro capacità di applicare le conoscenze acquisite nel corso. Gli studenti saranno chiamati a risolvere esercitazioni pratiche in laboratorio per risolvere alcuni dei problemi visti durante le lezioni teoriche.

È richiesto una adeguata conoscenza delle basi matematiche. Gli studenti devono conoscere i principi di funzionamento delle reti di computer, e delle diverse tecnologie di rete. È richiesta anche una buona conoscenza del linguaggio C.

• Costruzione di modelli di ottimizzazione partendo da problemi reali (9h)
• Analisi della complessità computazionale dei problemi di ottimizzazione (4,5 h)
• Cenni a problemi di flusso su reti (4,5 h)
• Euristiche costruttive polinomiali e di ricerca locale per problemi di ottimizzazione (3h)
• Meta-euristiche per problemi di ottimizzazione: Simulated Annealing, Genetic Algorithms, Tabu Search ed altre (12 h)
• Math-euristiche per problemi di ottimizzazione (3h).

• Applicazioni su casi reali di progettazione di reti di computer (20 h):
o Problemi di instradamento (5 h)
o Problemi di pianificazione nel tempo (schedulazione) (5 h)
o Problemi di pianificazione della topologia e della capacità (10 h)

Sono previste esercitazioni in aula ed in laboratorio sui diversi argomenti presentati nel corso. Gli studenti dovranno implementare alcuni degli algoritmi proposti e svolgere simulazioni per vedere l'efficacia delle tecniche proposte. Gli studenti avranno a disposizione librerie software che saranno utili per l'implementazione degli algoritmi. I laboratori richiedono una buona conoscenza del linguaggio C

Sono disponibili dispense delle lezioni e delle esercitazioni, esempi di scritti di esame ed esercizi, e i manuali per le esercitazioni di laboratorio. Tutto il materiale didattico è scaricabile da un sito web attraverso il portale della didattica.
Sono anche a disposizione articoli scientifici che descrivono i problemi affrontati e propongono diverse soluzioni e metodologie per risolvere gli stessi.
Sono consigliati i seguenti libri di testo:

• R. Tadei, F. Della Croce, Elementi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2010.
• R. Tadei, F. Della Croce, A. Grosso, Fondamenti di Ottimizzazione, Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
• M. Ghirardi, A. Grosso, G. Perboli, Esercizi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2009.
• D. J. Luenberger, Linear and Nonlinear Programming, Springer, 3rd ed., 2008.
• R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows, Prentice Hall, 1993.
• L. Nemhauser, L.A. Wolsey, Integer Programming, Wiley, 1998.

L'esame prevede una prova scritta divisa in due parti


Parte 1 – theory – in cui gli studenti saranno chiamati a rispondere a 3-4 domande o esercizi sulla parte teorica del corso.

Parte 2 – application to networking – in cui gli studenti saranno chiamati a rispondere a 2-3 domande o esercizi sulla parte applicativa del corso.

Gli studenti dovranno consegnare una relazione di laboratorio in cui riporteranno i risultati ottenuti durante le esercitazioni. Queste ultime saranno svolte in gruppo. E’ richiesta una relazione per gruppo, da consegnare prima di sostenere l’esame scritto.