Ultimo aggiornamento: 8/10/19
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: Facility Location e metodi di ascesa duale. Ottimizzazione su reti di flusso: problemi di flusso a costo minimo, simplesso su reti. Problemi di Vehicle Routing: metodi esatti ed euristici.
Docente: Andrea Pacifici. Email (o tel. 067259 7795) 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.
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 gennaio 2020).
I risultati fino al secondo appello della sessione autunnale li trovi qui. Nella sezione Date d'esame trovi date e risultati degli esami.
La discussione dei progetti si svolge nel mio ufficio. A questo scopo, fissiamo un appuntamento non appena mi comunicate - via email - la composizione del vostro gruppo di lavoro.
Qui una lista di riferimenti che aggiorniamo via via durante il corso:
Antonio Sassano, Modelli e Algoritmi della Ricerca Operativa, 1999, Franco Angeli, Milano.
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.
A.I.R.O - l'associazione italiana di Ricerca Operativa
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"
U.M.I. - Unione Matematica Italiana
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.
Punk Rock Operations Research (sic!) un'operazione di marketing per la Ricerca Operativa, con alcune discussioni su applicazioni interessanti dei modelli di ottimizzazione.
La prova di un appello d'esame consisterà in
1. uno scritto che verte sull'intero programma del corso più
2. una parte progettuale (vedi sezione più avanti).
La prova è articolata in 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 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: venerdì 17 maggio, aula A2, ore 9:00 (Risultati: tab. 190517)
giovedì 20 giugno 2019, aula B3, ore 14:00 (Risultati: tab. 190620)
mercoledì 17 luglio 2019, aula B3, ore 9:00 (Risultati: tab. 190717)
10 settembre 2019, aula C12, ore 09.30 (Risultati: tab. 190910)
30 settembre 2019, aula 4 ore 15.00 14:00. (Risultati: tab. 190930)
xx febbraio 2020, aula xx, ore xx
xx febbraio 2020, aula xx, ore xx
... Da definire. Seguono progetti assegnati lo scorso A.A.
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.
37. gio 30/5/19 Discussione progetti (per appuntamento presso l'ufficio del docente).
36. mar 28/5/19 Simplesso su reti per problemi di flusso a costo minimo: ottimalità e cambio di base. Esempi (dispensa prof. Agnetis).
–. lun 27/5/19 Lezione sospesa (decreto rettorale 1263/2019).
35. gio 23/5/19 Simplesso su reti per problemi di flusso a costo minimo: soluzioni di base e alberi (dispensa prof. Agnetis).
34. mar 21/5/19 SS-CFLP un rilassamento lagrangiano: bound duale e fixing delle variabili (rif. Addendum alla dispensa di Amaldi).
33. lun 20/5/19 Formulazione PLI e (soluzione dei) rilassamenti lagrangiani per Single-source capacitated Facility Location (SS-CFLP) (rif. dispensa prof. Amaldi).
32. ven 17/5/19 Prova in corso d'anno.
31. gio 16/5/19 Ancora esercizi di ricapitolazione per la prova in corso d'anno. Formulazioni per il problema del commesso viaggiatore (per un approfondimento puoi leggere qui).
30. mar 14/5/19 Esercitazione modelli di PL(I): Programmazione della produzione, scheduling. Esercizi di ricapitolazione per la prova in corso d'anno.
29. lun 13/5/19 Ancora sul rilassamento lagrangiano di UFL. 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).
28. gio 9/5/19 Ancora sui metodi di ascesa duale. Rilassamenti lagrangiani di un problema di programmazione lineare intera e relazioni con il duale del suo rilassamento continuo.
27. mar 7/5/19 Metodi di ascesa duale (rif. dispensa prof. Agnetis, dispensa prof. Amaldi) . Conseguenze primali del metodo di ascesa duale per UFL. La lezione terminerà alle ore 15:00.
26. lun 6/5/19 Algoritmi randomizzati: minimum edge-cardinality cut. Analisi (rif. dispensa del prof. L. Stougie).
25. gio 2/5/19 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. mar 30/4/19 Diseguaglianze cover per KP-{0,1} (rif. dispensa di L. De Giovanni). Branch-and-Bound e Branch-and-Cut (rif. dispensa su piani di taglio).
23. lun 29/4/19 Algoritmi basati su "piani di taglio": Diseguaglianze di Chvátal. Tagli di Gomory (rif. Fischetti Sez. 6.3; dispensa di L. Galli - U.Pisa; dispensa di G. Lancia - U. Udine)
22. mar 23/4/19 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).
21. gio 17/4/19 Ancora su problemi di scheduling su singola macchina (a cura del dr. Matteo Cosmi).
20. mar 16/4/19 Esercizi su formulazione di modelli PLI per lo scheduling: 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. lun 15/4/19 Ancora su problemi di scheduling: Branch-and-Bound "combinatoro" per 1|r_j| L_max. Schema di branching. Soluzione del rilassamento basato sul caso job "preemptive" (rif. Sez. 2.3, dispensa di A. Agnetis - U. Siena).
18. gio 11/4/19 Introduzione ai problemi di scheduling su singola macchina (a cura del dr. Matteo Cosmi).
17. mar 9/4/19 Lezione sospesa (Forum Università Lavoro).
16. lun 8/4/19 Introduzione ai problemi di scheduling su singola macchina (a cura del dr. Matteo Cosmi).
15. gio 4/4/19. 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).
14. mar 2/4/19. Algoritmi di approssimazione: ancora sul problema del Vertex Cover (un esempio che mostra che l'algoritmo Greedy2 non è approssimante). Problema del commesso viaggiatore (TSP). Risultato di inapprossimabiltà per il TSP (nel caso generale).
13. lun 1/4/19. Algoritmi di approssimazione per problemi di ottimizzazione combinatoria: introduzione (a cura della prof.ssa Gaia Nicosia). Puoi trovare un utile riferimento qui.
12. gio 28/3/19. Esercitazione modelli di PLI (a cura della dr.ssa Chiara Liti). Trova qui il materiale delle lezioni della dr.ssa Liti.
11. mar 26/3/19. Esercitazione modelli di PLI (a cura della dr.ssa Chiara Liti). Qui puoi trovare la licenza AMPL (a termine) per gli studenti del corso AMOD.
10. lun 25/3/19. Lezione sospesa.
9. gio 21/3/19. Concetti di dualità (rif. Fischetti Sez. 5.1-5.5). Metodo del simplesso dinamico duale: metodi (oracolo di) generazione colonne. Applicazione al caso del cutting stock 1-dim. (rif. Sassano Sez. 4.2.3).
8. mar 19/3/19. Ancora su un oracolo di separazione per un problema di cammino minimo su grafo non orientato. Il problema del cutting stock a una dimensione (rif. Sassano Sez. 4.2.3. Un interessante riferimento anche qui).
7. lun 18/3/19. Modelli PLI per problemi di Matching. Totale unimodularità della matrice dei vincoli nel caso di grafo bipartito. Rappresentazione esterna e implicita di un poliedro. Oracoli di separazione. Il metodo del simplesso dinamico primale. Applicazione a un problema di cammino minimo su grafo non orientato.
6. gio 14/3/19. Problemi di flusso a costo minimo: cammino minimo, problema dei trasporti, assegnamento. Relazioni e proprietà.
5. mar 12/3/19. Totale unimodularità. Condizioni sufficienti (rif. Fischetti, Sez. 6.1 e 6.2).
4. lun 11/3/19. Concetto di "formulazione" e sua qualità (rif. Sassano, Sez. 4.2). Esempi di problemi di OC: subset sum, assegnamento. Formulazioni lineari e loro qualità.
3. gio 7/3/19. Introduzione ai problemi di ottimizzazione intera (mista): Un problema di localizzazione capacitato. Problemi di ottimizzazione combinatoria (OC) (rif. dispensa su problemi di decisione e ottimizzazione combinatoria).
2. mar 5/3/19. Ancora sulla PL. Costi ridotti. Dizionari. Esempio.
1. lun 4/3/19. 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, base, soluzioni di base ammissibili) (rif. Fischetti, Cap.1, 2 e 3).