Ultimo aggiornamento: 9/7/20
Descrizione: AMOD è un corso magistrale sulla teoria e le applicazioni dell'ottimizzazione discreta. Dopo una prima parte dedicata alla ricapitolazione di nozioni di programmazione lineare e metodo del simplesso, trattiamo in modo più approfondito la programmazione lineare intera (PLI) e intera mista con alcuni riferimenti a problemi su reti. Metodi per la PLI: tagli di Gomory, metodi di enumerazione implicita: branch and bound e branch and bound "combinatori", Programmazione Dinamica. Concetto di formulazione di un PLI e sua qualità. Formulazioni compatte e non. Descrizioni esplicite ed implicite di un poliedro. Metodi di generazione colonne (problemi di pricing) e generazione vincoli (oracolo di separazione). Esempi: Cutting Stock, Shortest (s,t)-path. Rilassamento di un problema di ottimizzazione intera (lagrangiano, surrogato ecc.) Esempi. Algoritmi approssimati: concetti base. Esempi: Vertex-Cover, TSP euclideo. Metodi primali-duali: Esempio: Vertex-Cover. (Cenni di complessità computazionale). Algoritmi randomizzati per problemi deterministici di ottimizzazione discreta. Casi di studio: ... TBD
Docente: Andrea Pacifici. Email o tel. 067259 7795 Skype: andrea.pacifici (su appuntamento) se avete bisogno di incontrarmi per chiarimenti riguardo gli argomenti del corso. (Di solito, sono anche disponibile subito dopo le lezioni.)
Coordinate: Lunedì ore 11.30 aula B9, Martedì ore 14.00 aula B9 e Giovedì ore 9.30 aula B7. Le lezioni hanno una durata di 110 minuti. Sono disponibili (per gli studenti abilitati) le lezioni registrate sulla piattaforma d'Ateneo Microsoft Teams, gruppo AMOD. Le lezioni sono anche disponibili agli studenti che ne facciano richiesta: se non siete accreditati dal sistema ma volete seguire il corso, inviatemi un messaggio specificando un vostro indirizzo mail (da usare per essere autorizzati a visualizzare i file).
Iscrizione: Non è necessario iscriversi al corso ma è utile se mi informate della vostra intenzione di seguirlo e di sostenere l'esame in questo A.A. A questo scopo mandatemi un mail vuoto con oggetto (subject) "AMOD-Info [Nome] [Cognome]" dall'indirizzo al quale desiderate ricevere eventuali mie comunicazioni riguardanti questo corso. Se credete, potete aggiungere un recapito telefonico.
NEW Puoi scaricare AMPL qui (licenza fino a novembre 2020).
In alternativa alla erogazione frontale delle lezioni, ho prodotto delle "lavagne" con un commento audio. Trovate il link per scaricarle anche nella sezione "Agenda del corso", in fondo alla pagina. Ricordate che questo materiale è per l'uso esclusivo del corso e non deve essere diffuso. Tutti gli aggiornamenti (relativi alle modalità di erogazione delle lezioni e al materiali) sono riportati in questa pagina e sul gruppo google.
Qui una lista di riferimenti che aggiorniamo via via durante il corso:
Antonio Sassano, Modelli e Algoritmi della Ricerca Operativa, 1999, Franco Angeli, Milano. Il testo non è attualmente disponibile nelle librerie online: Nella sezione "Agenda del corso", in fondo a questa pagina, trovate i link a delle slide dello stesso autore, relative agli argomenti trattati.
Matteo Fischetti, Lezioni di Ricerca Operativa, 1995, Edizioni Libreria Progetto, Via Marzolo, 28, Padova.
Jon Lee, A first course in Linear Optimization, 2013, Reex Press. (Libro scaricabile qui. Software associato scaricabile qui).
Sara Mattia, Metodo del Simplesso Dinamico, slides
Paolo Serafini, Ottimizzazione, Zanichelli
Raccolta di esercizi d'esame qui . Ulteriori esempi di formulazioni PLI sono disponibili qui.
Questi link contengono dispense, esercizi, software freeware, curiosità relativi al mondo della ricerca operativa.
GUROBI - Software per l'ottimizzazione lineare, intera e quadratica.
IBM ILOG CPLEX - Altro software per l'ottimizzazione lineare, intera e quadratica.
La pagina didattica di Fabio Schoen - dispense, lucidi, esercizi, software e molte altre risorse per gli studenti di R.O.
La pagina didattica di Alessandro Agnetis - alcune chiare dispense ed utili esercizi su argomenti chiave di un corso di R.O.
La pagina didattica di Antonio Sassano con le slide sugli argomenti trattati nel libro Modelli e Algoritmi della Ricerca Operativa, Franco Angeli.
Una pagina didattica di Sara Mattia con altre slide sugli argomenti trattati in questo corso.
Michael Trick's Home Page - una quantità di informazioni e link orientati alla Ricerca Operativa.
INFORMS - la pagina della "International Federation of Operations Research and Management Science"
A.I.R.O - l'associazione italiana di Ricerca Operativa
U.M.I. - Unione Matematica Italiana
La prova d'esame – sicuramente per la sessione estiva e molto probabilmente anche per quella autunnale – di questo A.A. 2019-20 consisterà in
1. uno scritto un colloquio orale – attraverso la piattaforma Microsoft Teams – (durata 25-40 min.) che verterà sull'intero programma del corso più
2. una parte progettuale (vedi sezione più avanti).
La prova è articolata in 2-3 domande 4/5 quesiti di cui almeno uno richiede di scrivere un modello di programmazione matematica (tipicamente PLI) e almeno due alternativi a scelta dello studente. Oltre al modello di ottimizzazione, le Le domande possono richiedere l'illustrazione di un argomento svolto durante il corso, l'applicazione di un algoritmo su un (piccolo) esempio, ma anche la definizione (rigorosa) di un problema o di un oggetto matematico. È richiesto che lo studente sappia adoperare in modo costruttivo le nozioni apprese e dimostrare comprensione sufficientemente approfondita dei concetti: a tal fine un quesito potrebbe anche richiedere di inferire semplici proprietà a partire da ipotesi date. Si veda un esempio di problema d'esame.
Non è consentito utilizzare materiale didattico, come appunti e libri di testo. Non è consentito utilizzare dispositivi capaci di connessioni alle reti, come telefoni, PC, tablet, smartphone. È necessario dotarsi di fogli su cui produrre l'elaborato e avere con sé un documento di identità o il libretto universitario. Non è permesso sostenere prove d'esame su parti del programma allo scopo di migliorare un voto precedentemente acquisito.
Come prenotarsi per gli appelli d'esame: Utilizzare l'apposito modulo online sul sito delphi.uniroma2.it
Si ricorda che sono previste tre sessioni ufficiali d'esame (Ord. D.M. 270/2004). Sessione Estiva: Due appelli d'esame alla fine del corso (a luglio). Sessione Autunnale: Due appelli d'esame (a settembre). Sessione Invernale: Un appello d'esame (a febbraio).
Appelli d'esame straordinari. In casi di comprovata urgenza, per esempio se il mancato sostenimento dell'esame causa uno slittamento della sessione di laurea, uno studente, solo se è iscritto al secondo anno (o ripetente), può chiedere al docente di indire un appello straordinario al di fuori delle sessioni ufficiali. Si ricordi che, secondo le regole attualmente in vigore, in uno stesso A.A. uno studente può sostenere al più un esame in un appello straordinario e che la convocazione di un appello straordinario è a discrezione del docente titolare del corso e del Consiglio di Corso di Studi.
Prova in corso d'anno:
30 giugno 2020, aula , dalle ore 10:15 (il calendario degli appuntamenti sarà comunicato ai prenotati).
21 luglio 2020, aula , dalle ore 9:00 (il calendario degli appuntamenti sarà comunicato ai prenotati).
... settembre 2020, aula , ore
... settembre 2020, aula , ore
... febbraio 2021, aula , ore
... febbraio 2021, aula , ore
Confronto di formulazioni PLI per problemi di ottimizzazione intera NP-difficili (scheduling, localizzazione, flusso multicommodity, ... )
Gomory Cuts: implementazione e test
Column generation: implementazione e test
Euristiche di ascesa duale:
Branch-and-bound combinatori: disegno, implementazione e test
Algoritmi randomizzati: disegno, implementazione e test.
In questa pagina trovi ulteriori dettagli sui problemi test.
Le video-lavagne (insieme ai pdf delle note) sono disponibili tutte in questo folder.
40. giovedì 4/6/20. Ricevimento collettivo: ricapitolazione argomenti del corso.
35-39. giovedì 21/5, lun 25/6, mar 26/5, gio 28/5, lun 1/6 2020. Discussione dei temi per i progetti.
34. martedì 19/5/20. Esercitazione.
33. lunedì 18/5/20. Esercitazione.
32. giovedì 14/5/20. Esempi di problemi PLI. Presentazione AMPL (rif. Materiale AMPL a cura di Chiara Liti su Teams).
31. martedì 12/5/20. Ancora sul principio min-max di Yao per l'analisi delle performance di un RA: esempio su algoritmo di sorting (rif. "tutorial" qui).
30. lunedì 11/5/20. Algoritmi randomizzati: Principio min-max di Yao per l'analisi delle performance di un RA (rif. dispensa del prof. L. Stougie).
29. giovedì 7/5/20. Algoritmi randomizzati: Max-Sat, minimum edge-cardinality cut (rif. dispensa del prof. L. Stougie).
28. martedì 5/5/20. Ancora su algoritmo di ascesa duale per facility location non capacitato: conseguenze "primali". Single-source facility location capacitato: formulazione PLI, rilassamenti lagrangiani e fixing delle variabili (rif. dispensa prof. Agnetis, dispensa prof. Amaldi).
27. lunedì 4/5/20. Facility location non capacitato. Algoritmo di ascesa duale di Erlenkotter (rif. dispensa prof. Agnetis, dispensa prof. Amaldi).
26. giovedì 30/4/20. Facility location non capacitato. Formulazione PLI. Formulazioni "forte" e "debole". Soluzione del rilassamento lineare.
25. martedì 28/4/20 . Programmazione lineare e algoritmi approssimanti: condizioni di scarto complementare approssimate e metodo primale-duale con applicazione al problema del min weighted vertex cover (rif. dispensa in preparazione).
24. lunedì 27/4/20 . Metodi di approssimazione basati sulla PL. Applicazione al problema del vertex cover di cardinalità minima.
23. giovedì 23/4/20. Algoritmi di approssimazione: Problema del commesso viaggiatore (TSP). Risultato di inapprossimabiltà per il TSP (nel caso generale). TSP Euclideo (metrico): Relazioni del costo di un tour ottimo con il minimo costo di un albero ricoprente e con il minimo costo di un matching perfetto (rif. p.es. su questa dispensa su apx di vertex-cover e TSP).
22. martedì 21/4/20 Algoritmi di approssimazione per problemi di ottimizzazione combinatoria: introduzione. Puoi trovare un utile riferimento qui. Algoritmi di apx. per il problema del Vertex Cover (un esempio che mostra che l'algoritmo 2 non è approssimante).
21. lunedì 20/4/20 Programmazione dinamica: Principio di ottimalità. Esempio: cammino minimo su grafo orientato, equazioni di Ford-Bellman. Algoritmo di programmazione dinamica per il problema di knapsack binario (rif. dispensa).
20. giovedì 16/4/20 Formulazioni PLI per problemi di scheduling su macchina singola: variabili di tipo (i) Completion Time, (ii) Time Indexed, (iii) Linear Ordering, (iv) posizionali (rif. dispensa su programmazione intera per lo scheduling singola macchina).
19. martedì 14/4/20 Branch and Bound combinatorio: un esempio per il problema di scheduling 1 | r_j | L_max (rif.: Sez. 2.3 della dispensa di A. Agnetis).
18. giovedì 9/4/20 Metodi Branch-and-Cut per la PLI (rif. Fischetti Sez. 6.4, dispensa su piani di taglio). Scheduling single machine: formulazione PLI.
17. martedì 7/4/20 Metodi Branch-and-Bound per la PLI (rif. Fischetti Sez. 6.4, dispensa su piani di taglio).
16. lunedì 6/4/20 Diseguaglianze valide: Diseguaglianze cover per KP-{0,1} (rif. dispensa di L. De Giovanni).
15. giovedì 2/4/20 Esercitazione: esempi su tagli di Gomory. Uso di foglio elettronico Excel per la soluzione di PL(I).
14. martedì 31/3/20 Ancora su formulazioni PLI di particolari funzioni di costo. Tagli di Gomory (rif. Fischetti Sez. 6.3; dispensa di L. Galli - U.Pisa; dispensa di G. Lancia - U. Udine)
13. lunedì 30/3/20 Formulazione PLI di funzioni di costo particolari (rif. dispensa su problemi di decisione e ottimizzazione combinatoria).
12. giovedì 26/3/20 Esercizi su formulazione di modelli PLI: rappresentazione di funzioni logiche, Formulazione lineare di implicazioni, funzioni obiettivo con costi fissi. (rif. dispensa su problemi di decisione e ottimizzazione combinatoria).
11. martedì 24/3/20 Algoritmi cutting plane (dei "piani di taglio") per la PLI. Procedura di Chvátal per la generazione di diseguaglianza valide, t-ma chiusura di Chvátal di una formulazione lineare. Esempio: max matching su grafo n.o. (rif. Fischetti Sez. 6.3; dispensa di L. Galli - U.Pisa; dispensa di G. Lancia - U. Udine)
10. lunedì 23/3/20 Metodo del simplesso dinamico "duale": problema di pricing e algoritmi di generazione colonne. Applicazione al problema di cutting stock monodimensionale (rif. Sassano Sez. 4.2.3. --> slide di L. De Giovanni. Un interessante riferimento anche qui).
9. gio 19/3/20 Ancora sulla rappresentazione "implicita" di un poliedro: oracolo di separazione e sull'applicazione a un problema di cammino minimo su grafo non orientato (rif. Sassano Sez. 4.2.3 --> slide).
8. mar 17/3/20 Le matrici di incidenza di un grafo non orientato bipartito e di un grafo orientato generico sono TUM. Applicazione ai problemi di assegnamento e flusso a costo minimo (rif. dispensa De Giovanni). Rappresentazione "implicita" di un poliedro: oracolo di separazione e il metodo del simplesso "dinamico". (rif. slide Sassano). Applicazione a un problema di cammino minimo su grafo non orientato (rif. Sassano Sez. 4.2.3 --> slide).
7. lun 16/3/20 Ancora su Totale Unimodularità: condizioni sufficienti (anche su slide Sassano), interezza delle soluzioni del problema di assegnamento (rif. Fischetti, Sez. 6.1 e 6.2). Problema di flusso a costo minimo (rif. dispensa Locatelli).
6. gio 12/3/20 Esempio di PLI: subset sum e problema dei trasporti (assegnamento). Problemi di PLI e relazioni con il corrispondente rilassamento continuo. Totale unimodularità. Esempi (rif. Fischetti, Sez. 6.1 e 6.2).
5. mar 10/3/20 Introduzione ai problemi di ottimizzazione lineare intera (mista). Problemi di ottimizzazione combinatoria (OC) (rif. dispensa su problemi di decisione e ottimizzazione combinatoria). Rilassamento continuo di un PLI. Formulazioni lineari e loro qualità. Formulazione "ottima" (rif. Sassano, Sez. 4.2 --> slide).
4. lun 9/3/20 Ancora sui costi ridotti per la PL e su concetti di dualità (rif. Fischetti, Cap. 5).
3. gio 5/3/20 (Recuperata nella lezione del 12/3.)
2. mar 3/3/20 Ancora sulla PL: base, dizionario, soluzioni di base ammissibili, costi ridotti. Esempio (rif. Fischetti, Cap.1, 2 e 3).
1. lun 2/3/20. Administrivia. Introduzione al corso di AMOD. Recap di problemi di programmazione lineare (PL): Problema di ottimizzazione (variabili di decisione, regione ammissibile, funzione obiettivo, problemi vuoti, illimitatati, con ottimo finito). Problemi di PL (forma standard) (rif. Fischetti, Cap.1, 2 e 3).