This page is not used anymore as a teaching support for the course: Please refer to the suitable team on the MS Teams platform of Università di Roma Tor Vergata.
Ultimo aggiornamento: 31/5/22
Link Microsoft Teams: https://teams.microsoft.com/l/team/19%3aeb0138ef151d40949c4dc34eb361e2a7%40thread.tacv2/conversations?groupId=95125cce-03ff-46aa-bdc8-469f170844e7&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e
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.
Docente: Andrea Pacifici. Ricevo (su appuntamento per email) se avete bisogno di chiarimenti riguardo gli argomenti del corso.
Coordinate: le lezioni si tengono in modalità mista (presenza+online) negli orari e aule sottoindicati.
Lunedì ore 11.30 (aula B9) ,
Martedì ore 9:30 (aula B14) e
Giovedì ore 11.30 (aula B9).
Le lezioni sono trasmesse su Microsoft Teams. Saranno disponibili (per gli studenti abilitati) le note sul canale lezioni del team 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: è necessario iscriversi al corso: potete farlo attraverso delphi.
NEW! Puoi scaricare AMPL qui (la licenza scade il 30/09/2022, informatemi quando/se vi serve rinnovarla). Per installarlo, segui le indicazioni che trovi in questa pagina.
Visita la pagina dell' A.A. 2018-19 (nella sezione Agenda trovate dettagli sugli argomenti che abbiamo svolto).
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. 2021-22 consisterà in
1. un esame scritto – eventualmente a distanza – (durata 90 min.) che verte sull'intero programma del corso, e in
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. Se riusciamo a fare l'esame in presenza, 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:
Questi sono alcuni dei temi dei progetti assegnati negli anni passati.
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 note/lavagne delle lezioni vengono pubblicate su MS Teams, Team AMOD, nel canale Lezioni > Files
37. mar 31/5/22 Ancora sull'algoritmo di Christofides. Algoritmi approssimanti basati sulla PL. "Doubling and Rounding Down" per il minimum vertex cover. Introduzione agli algoritmi approssimanti basati sul metodo primale-duale
36. lun 30/5/22 Algoritmi approssimanti per il problema del commesso viaggiatore TSP metrico. Algoritmo di Christofides
35. gio 26/5/22 Algoritmi di approssimazione per problemi di ottimizzazione combinatoria: scheduling (a cura della prof.ssa Nicosia)
34. mar 24/5/22 Algoritmi di approssimazione per problemi di ottimizzazione combinatoria: introduzione (a cura della prof.ssa Nicosia)
33. lun 23/5/22 Euristiche costruttive per CVRP: k-opt, Clarke & Wright, Sweep, Tabu Search
32. gio 19/5/22 Due lower bound per CVRP (a partire dalla formulazione a due indici): Spanning Arborescence LB e Assignment/Transportation LB.
31. mar 17/5/22 Formulazioni compatte (Miller, Tucker e Zemlin) per TSP e CVRP. Modello "a tre indici" per CVRP.
30. lun 16/5/22 Vehicle Routing Problem (VRP). Relazioni con il TSP. Modello MIP "a due indici" per CVRP.
29. gio 12/5/22 Due rilassamenti lagrangiani per SSCFLP.
28. mar 10/5/22 DUALOC un algoritmo di ascesa duale per UFL. Facility location capacitato e SSCFLP.
27. lun 9/5/22 Uncapacitated Facility Location (UFL): formulazioni forte e debole. Duale del rilassamento con la formulazione forte.
26. gio 5/5/22 Ancora sulla formulazione MIP di problemi di Assembly Line Balancing.
25. mar 3/5/22 Esercizi su formulazione MIP di problemi di scheduling. Esercizi d'esame.
24. lun 2/5/22 Ancora sulla formulazione MIP di problemi di scheduling: variabili posizionali. Esempi ed esercizi di modelli MIP per lo scheduling.
23. gio 28/4/22 Problemi di scheduling single-machine: casi classici "facili" e NP-difficili. Tecniche per la formulazione MIP di problemi di sequenziamento su macchina singola: vincoli disgiuntivi, variabili "tempo-indicizzate".
22. mar 26/4/22 Ancora sul Branch-and-Bound combinatorio per 1|r_j|L_max. Formulazioni MIP per il problema.
21. gio 21/4/22 Branch-and-Bound "combinatori": applicazione al problema di scheduling 1|r_j| L_max. Ottimalità della regola PEDD (Earliest Due Date) per 1|r_j, pmnt|L_max (rif. Sez. 2.3, dispensa di A. Agnetis - U. Siena).
La lezione di di mar 19/4 non si terrà
20. gio 14/4/22 Rilassamenti di un problema di ottimizzazione. Rilassamento lagrangiano (applicazione a KP-{0,1}). Soluzione del rilassamento lineare di KP-{0,1}. Schema di Branch-and-Bound per KP-{0,1}.
19. mar 12/4/22 Metodi Branch-and-Bound e Branch-and-Cut per PLI generali.
18. lun 11/4/22 Chvátal-Gomory cuts. Diseguaglianze cover per KP-{01} e problema di separazione. Procedura per problemi più generali.
17. gio 7/4/22 (recupero della lez.#12 del 28/3) Introduzione ad AMPL a cura della dott.ssa C. Salvatore
16. mar 5/4/22 Programmazione dinamica per KP-{0,1}. (Lezione in presenza cancellata: disponibile su Teams come registrazione dal 21/4. rif. dispensa).
15. lun 4/4/22 Metodi per la PLI: Algoritmi basati su "piani di taglio": Diseguaglianze di Chvátal. (rif. Fischetti Sez. 6.3; dispensa di L. Galli - U.Pisa; dispensa di G. Lancia - U. Udine)
14. gio 31/3/22 Totale unimodularità: applicazione a problemi di flusso a costo minimo (rif. dispensa De Giovanni).
13. mar 29/3/22 Recap: concetti di dualità per la PL (rif. dispensa). Ancora sul problema di cutting-stock: definizione dei costi ridotti associati a un cutting pattern e problema di "pricing" (rif. Sassano Sez. 4.2.3. --> slide di L. De Giovanni. Un interessante riferimento anche qui).
12. lun 28/3/22 cancellata
11. gio 24/3/22 (lez. a cura della Prof. G. Nicosia). Esercitazioni su modellazione PLI di problemi di decisione (rif. dispensa su problemi di ottimizzazione combinatoria).
10. mar 22/3/22 Esempio di applicazione del metodo del simplesso dinamico: Progetto di rete semplificato (rif. Sassano Sez. 4.2.3 --> slide).
9. lun 21/3/22 (lez. a cura della Prof. G. Nicosia). Tecniche di "modellazione" PLI.
8. gio 17/3/22 (lez. a cura della Prof. G. Nicosia). Formulazione PLI per il Crew Scheduling.
7. mar 15/3/22 Rappresentazione implicita di un poliedro. "Oracolo di Separazione". Metodo del simplesso dinamico (primale). (rif. Sassano, Sez. 4.2.)
6. lun 14/3/22 (lez. a cura della Prof. G. Nicosia nicosia at ing.uniroma3.it) Esempi di problemi di PLI (Knapsack, Assegnamento, Set Covering/Packing/Partitioning).
5. gio 10/3/22 Ancora su PLI e inviluppi convessi della loro regione ammissibile. Un problema su grafo n.o.: sottografo (s,t)-connesso di costo minimo.
4. mar 8/3/22 Problemi di programmazione lineare mista e intera: definizioni. Sulla geometria della PL: combinazioni lineari convesse e coniche; inviluppi; poliedri: rappresentazione per semispazi e per vertici.
3. lun 7/3/22 Ancora sulla PL: esempi illustrativi dei concetti di SBA e costi ridotti. (rif. Fischetti, Cap.1, 2 e 3).
2. gio 3/3/22 Problemi di PL (forma standard): base, dizionario, soluzioni di base ammissibili (SBA), costi ridotti. Esempio (rif. Fischetti, Cap.1, 2 e 3).
1. mar 1/3/22 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). Due esempi di modelli di PL(I) (rif. Fischetti, Cap.1 e 2).