Ottimizzazione combinatoria
A.A. 2018/2019
Obiettivi formativi
Gli obiettivi del corso sono: 1) apprendere alcuni algoritmi di complessita' polinomiale per problemi di ottimizzazione su grafo e i fondamenti teorici sui quali tali algoritmi si basano; 2) implementare alcuni degli algoritmi presentati (una parte del corso si svolge in laboratorio informatizzato); 3) capire quando la ricerca di algoritmi polinomiali, per un nuovo problema di ottimizzazione combinatoria, e'
probabilmente destinata a fallire (mediante la teoria della complessita'
computazionale).
probabilmente destinata a fallire (mediante la teoria della complessita'
computazionale).
Risultati apprendimento attesi
Non definiti
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Linea Milano
Responsabile
Periodo
Secondo semestre
STUDENTI FREQUENTANTI
Programma
L'Ottimizzazione Combinatoria si occupa di trovare un elemento "ottimo" all'interno di un insieme di cardinalità finita. Affinché il problema di ottimizzazione abbia una qualche rilevanza, la tecnica di ricerca esaustiva deve risultare impraticabile. Questo accade quando la cardinalità dell'insieme è tale da rendere computazionalmente impraticabile l'enumerazione di tutti i suoi elementi. Il corso si focalizza sulla soluzioni di problemi di ottimizzazione su grafo. Si usano principalmente relazioni primali/duali, o di natura combinatorica, o ricavate dai modelli di programmazione matematica dei problemi affrontati (per tale ragione è utile avere delle basi di Ricerca Operativa). Si studiano principalmente problemi per i quali sono noti algoritmi con complessità di calcolo polinomiale nella dimensione delle istanze (nel nostro caso, nel numero dei nodi e dei lati dei grafi). Si passa un bel po' di tempo in laboratorio a cercare di implementarne qualcuno, in C o C++ . Si affronteranno quindi anche gli aspetti legati alle strutture dati, sottolineando quali sono più o meno computazionalmente efficienti.
Si forniscono i concetti principali della teoria della complessità computazionale, per capire come mai in certi casi non abbia molto senso cercare algoritmi polinomiali, ma sia necessario ricorre a tecniche di enumerazione implicita degli elementi del nostro insieme (Branch and Bound) o a tecniche poliedrali associate ai modelli di programmazione matematica di tali problemi (Cutting plane, Branch and Cut). L'approfondimento di tali tecniche viene dato nel corso di Complementi di Ricerca Operativa, qui cerchiamo di capire (sulla base di solide congetture) quando è indispensabile ricorrere ad esse.
Riassumendo, l'Ottimizzazione Combinatoria è un sottoinsieme dell'ottimizzazione, ha legami con la Ricerca Operativa, fornendo algoritmi e tecniche usati da quest'ultima per affrontare specifici problemi di decisione, e con la teoria dei grafi, il progetto di algoritmi, le strutture dati e la complessità computazionale.
Si forniscono i concetti principali della teoria della complessità computazionale, per capire come mai in certi casi non abbia molto senso cercare algoritmi polinomiali, ma sia necessario ricorre a tecniche di enumerazione implicita degli elementi del nostro insieme (Branch and Bound) o a tecniche poliedrali associate ai modelli di programmazione matematica di tali problemi (Cutting plane, Branch and Cut). L'approfondimento di tali tecniche viene dato nel corso di Complementi di Ricerca Operativa, qui cerchiamo di capire (sulla base di solide congetture) quando è indispensabile ricorrere ad esse.
Riassumendo, l'Ottimizzazione Combinatoria è un sottoinsieme dell'ottimizzazione, ha legami con la Ricerca Operativa, fornendo algoritmi e tecniche usati da quest'ultima per affrontare specifici problemi di decisione, e con la teoria dei grafi, il progetto di algoritmi, le strutture dati e la complessità computazionale.
Propedeuticità
Un corso di Algoritmi e strutture dati
Prerequisiti
Prerequisiti: è preferibile aver frequentato il corso di Ricerca Operativa ed un corso di programmazione. Sarebbe ideale avere anche le basi di algoritmi e strutture dati.
Modalità di accertamento: l'esame consiste in una discussione orale che verte su argomenti trattati nel corso e in una delle seguenti attività: l'approfondimento di un tema specifico su uno o più aricoli su rivista sceintifica, o l'implementazione e la relativa breve documentazione di un algoritmo che risolva uno dei problemi trattati a lezione.
Modalità di accertamento: l'esame consiste in una discussione orale che verte su argomenti trattati nel corso e in una delle seguenti attività: l'approfondimento di un tema specifico su uno o più aricoli su rivista sceintifica, o l'implementazione e la relativa breve documentazione di un algoritmo che risolva uno dei problemi trattati a lezione.
Metodi didattici
Lezioni frontali con l'ausilio di lavagna e la proiezione di lucidi. Lezioni in laboratorio informatizzato durante le quali implementare parte degli algoritmi studiati nel corso
Materiale di riferimento
STUDENTI NON FREQUENTANTI
Saranno rese disponibili attraverso il sito Ariel del corso i lucidi utilizzati a lezione.
I testi che contengono parti del corso sono:
[1] F. Maffioli, Elementi di Programmazione Matematica, vol. primo, Ed. Masson (1990)
Cap. 2, Algoritmi e Complessità, pp. 19-43.
[2] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, Ed. Wiley (1998)
Cap. 2,3,4,5
[3] D.Jungnickel, Graphs, Networks and Algorithms, Sec. Ed. Springer (2005)
Vari capitoli e sezioni.
I testi che contengono parti del corso sono:
[1] F. Maffioli, Elementi di Programmazione Matematica, vol. primo, Ed. Masson (1990)
Cap. 2, Algoritmi e Complessità, pp. 19-43.
[2] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, Ed. Wiley (1998)
Cap. 2,3,4,5
[3] D.Jungnickel, Graphs, Networks and Algorithms, Sec. Ed. Springer (2005)
Vari capitoli e sezioni.
Programma
L'Ottimizzazione Combinatoria si occupa di trovare un elemento "ottimo" all'interno di un insieme di cardinalità finita. Affinché il problema di ottimizzazione abbia una qualche rilevanza, la tecnica di ricerca esaustiva deve risultare impraticabile. Questo accade quando la cardinalità dell'insieme è tale da rendere computazionalmente impraticabile l'enumerazione di tutti i suoi elementi. Il corso si focalizza sulla soluzioni di problemi di ottimizzazione su grafo. Si usano principalmente relazioni primali/duali, o di natura combinatorica, o ricavate dai modelli di programmazione matematica dei problemi affrontati (per tale ragione è utile avere delle basi di Ricerca Operativa). Si studiano principalmente problemi per i quali sono noti algoritmi con complessità di calcolo polinomiale nella dimensione delle istanze (nel nostro caso, nel numero dei nodi e dei lati dei grafi). Si passa un bel po' di tempo in laboratorio a cercare di implementarne qualcuno, in C o C++ . Si affronteranno quindi anche gli aspetti legati alle strutture dati, sottolineando quali sono più o meno computazionalmente efficienti.
Si forniscono i concetti principali della teoria della complessità computazionale, per capire come mai in certi casi non abbia molto senso cercare algoritmi polinomiali, ma sia necessario ricorre a tecniche di enumerazione implicita degli elementi del nostro insieme (Branch and Bound) o a tecniche poliedrali associate ai modelli di programmazione matematica di tali problemi (Cutting plane, Branch and Cut). L'approfondimento di tali tecniche viene dato nel corso di Complementi di Ricerca Operativa, qui cerchiamo di capire (sulla base di solide congetture) quando è indispensabile ricorrere ad esse.
Riassumendo, l'Ottimizzazione Combinatoria è un sottoinsieme dell'ottimizzazione, ha legami con la Ricerca Operativa, fornendo algoritmi e tecniche usati da quest'ultima per affrontare specifici problemi di decisione, e con la teoria dei grafi, il progetto di algoritmi, le strutture dati e la complessità computazionale.
Si forniscono i concetti principali della teoria della complessità computazionale, per capire come mai in certi casi non abbia molto senso cercare algoritmi polinomiali, ma sia necessario ricorre a tecniche di enumerazione implicita degli elementi del nostro insieme (Branch and Bound) o a tecniche poliedrali associate ai modelli di programmazione matematica di tali problemi (Cutting plane, Branch and Cut). L'approfondimento di tali tecniche viene dato nel corso di Complementi di Ricerca Operativa, qui cerchiamo di capire (sulla base di solide congetture) quando è indispensabile ricorrere ad esse.
Riassumendo, l'Ottimizzazione Combinatoria è un sottoinsieme dell'ottimizzazione, ha legami con la Ricerca Operativa, fornendo algoritmi e tecniche usati da quest'ultima per affrontare specifici problemi di decisione, e con la teoria dei grafi, il progetto di algoritmi, le strutture dati e la complessità computazionale.
Prerequisiti
Prerequisiti: è preferibile aver frequentato il corso di Ricerca Operativa ed un corso di programmazione. Sarebbe ideale avere anche le basi di algoritmi e strutture dati.
Modalità di accertamento: l'esame consiste in una discussione orale che verte su argomenti trattati nel corso e in una delle seguenti attività: l'approfondimento di un tema specifico su uno o più aricoli su rivista sceintifica, o l'implementazione e la relativa breve documentazione di un algoritmo che risolva uno dei problemi trattati a lezione.
Modalità di accertamento: l'esame consiste in una discussione orale che verte su argomenti trattati nel corso e in una delle seguenti attività: l'approfondimento di un tema specifico su uno o più aricoli su rivista sceintifica, o l'implementazione e la relativa breve documentazione di un algoritmo che risolva uno dei problemi trattati a lezione.
Materiale di riferimento
Saranno rese disponibili attraverso il sito Ariel del corso i lucidi utilizzati a lezione.
I testi che contengono parti del corso sono:
[1] F. Maffioli, Elementi di Programmazione Matematica, vol. primo, Ed. Masson (1990)
Cap. 2, Algoritmi e Complessità, pp. 19-43.
[2] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, Ed. Wiley (1998)
Cap. 2,3,4,5
[3] D.Jungnickel, Graphs, Networks and Algorithms, Sec. Ed. Springer (2005)
Vari capitoli e sezioni.
I testi che contengono parti del corso sono:
[1] F. Maffioli, Elementi di Programmazione Matematica, vol. primo, Ed. Masson (1990)
Cap. 2, Algoritmi e Complessità, pp. 19-43.
[2] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, Ed. Wiley (1998)
Cap. 2,3,4,5
[3] D.Jungnickel, Graphs, Networks and Algorithms, Sec. Ed. Springer (2005)
Vari capitoli e sezioni.
Docente/i
Ricevimento:
su appuntamento
stanza 3012 via Celoria 18