Algoritmi e Modelli per l'Ottimizzazione Discreta (2017-18)

Corso magistrale per Ingegneria Informatica (9 crediti).

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. Dal 19/3/18 le lezioni avranno 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) "RO-Info [Nome] [Cognome]" dall'indirizzo al quale desiderate ricevere eventuali mie comunicazioni riguardanti questo corso.

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.

Testi consigliati e da consultare

Qui una lista di riferimenti che aggiorniamo via via durante il corso:

1. Antonio Sassano, Modelli e Algoritmi della Ricerca Operativa, 1999, Franco Angeli, Milano.

2. Matteo Fischetti, Lezioni di Ricerca Operativa, 1995, Edizioni Libreria Progetto, Via Marzolo, 28, Padova.

3. Jon Lee, A first course in Linear Optimization, 2013, Reex Press. (Libro scaricabile qui. Software associato scaricabile qui).

4. Sara Mattia, Metodo del Simplesso Dinamico, slides

5. Paolo Serafini, Ottimizzazione, Zanichelli

Link

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.

Modalità d'esame

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.

Date d'esame

Sessione estiva

• 8 giugno, aula 3, ore 13.30 7 giugno, aula 4, ore 13.15 (i risultati sono disponibili qui -- tab 18068).

• 3 luglio, aula 4, ore 14.00 (i risultati sono disponibili qui -- tab 180703).

Sessione autunnale

• 30 agosto, aula C6, ore 9.30 (i risultati sono disponibili qui -- tab 180830).

• 21 settembre, aula C6, ore 9.30(i risultati sono disponibili qui -- tab 180921).

Sessione invernale

• 6 febbraio 2019, ufficio docente (st. D2 - 05), ore 11:00 (risultati).

• 22 febbraio 2019, aula B11, ore 9:30.

Progetti

• 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. E, in ques'altra, una tabella con gli appuntamenti proposti ai vari gruppi per la definizione dei progetti assegnati.

Agenda del corso

35. lunedì 28/5/2018 Discussione dei progetti: gruppi 8 e 9. Fine del corso.

34. giovedì 24/5/18 Discussione dei progetti: gruppi 4, 5, 10 e 12.

33. martedì 22/5/18 Discussione dei progetti: gruppi 1, 6 e 7.

32. lunedì 21/5/18 SS-CFLP un rilassamento lagrangiano: bound duale e fixing delle variabili (rif. Addendum alla dispensa di Amaldi). Discussione dei progetti: gruppi 2 e 3.

31. giovedì 17/5/18 Conseguenze primali del metodo di ascesa duale per UFL. Formulazione PLI e (soluzione dei) rilassamenti lagrangiani per Single-source capacitated Facility Location (SS-CFLP) (rif. dispensa prof. Amaldi).

29-30. martedì 15/5/18 mattina: Metodi di ascesa duale (rif. dispensa prof. Agnetis, dispensa prof. Amaldi) pomeriggio: Discussione prova d'esame. Assegnazione dei progetti.

28. lunedì 14/5/18 Analisi dell'algoritmo randomizzato per minimum edge-cardinality cut (rif. dispensa del prof. L. Stougie). Modelli di PL(I): Programmazione della produzione e vincolo best-before date. Un problema di copertura di una scacchiera.

27. giovedì 10/5/18 Ancora sull'approssimazione per min weighted vertex cover. Algoritmi randomizzati: minimum edge-cardinality cut (rif. dispensa del prof. L. Stougie).

24-25-26. giovedì 3, lunedì 7 e martedì 8/5/18 Algoritmi approssimanti per Facility location. Tre lezioni a cura del Prof. Oriolo (rif. dispensa su Facility Location Game e lecture del prof. A. Gupta).

23. lunedì 30/4/18 Lezione sospesa.

22. giovedì 26/4/18 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).

21. martedì 24/4/18 Esercitazione modelli di PLI (a cura di C. Liti). Qui puoi trovare la licenza AMPL (a termine) per gli studenti del corso AMOD.

20. lunedì 23/4/18 Esercitazione modelli di PLI (a cura di M. Cosmi). Qui puoi trovare la licenza AMPL (a termine) per gli studenti del corso AMOD.

19. giovedì 19/4/18 Algoritmo di Christofides (rif. p.es. su questa nota o anche questa dispensa su apx. di vertex-cover e TSP).

18. martedì 17/4/18 La lezione non si è tenuta (causa FORUM Università-Lavoro).

17. lunedì 16/4/18 Algoritmi di approssimazione per il problema del commesso viaggiatore (TSP) nel caso "metrico". Risultato di inapprossimabiltà per il TSP (nel caso generale). Relazioni del costo di un tour ottimo con il minimo costo di un albero ricoprente e con il minimo costo di matching di cardinalità massima (rif. p.es. su questa dispensa su apx di vertex-cover e TSP).

16. giovedì 12/4/18 (lez. tenuta dalla prof.ssa G. Nicosia, U. Roma Tre). Algoritmi di approssimazione per problemi di ottimizzazione: definizioni, misure di qualità assolute e relative, esempi di algoritmi apx per il min. vertex cover. Tipologie di algoritmi approssimanti (rif. dispensa su algoritmi di apx primale-duale).

15. martedì 10/4/18 Esercitazione su modelli di PLI. Formulazione lineare di implicazioni, funzioni obiettivo con costi fissi (rif. dispensa su problemi di decisione e ottimizzazione combinatoria).

14. lunedì 9/4/18 Branch-and-Bound "combinatori": applicazione al problema di scheduling 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).

13. giovedì 5/4/18 Rilassamento di un problema di ottimizzazione (rif. Sez. 2 dispensa su Duale di un PL). Branch-and-Bound "combinatori": applicazione al problema di scheduling 1|r_j| L_max. Ottimalità della regola EDD (Earliest Due Date) per 1||L_max (rif. Sez. 2.3, dispensa di A. Agnetis - U. Siena). Formulazioni PLI di 1|r_j|L_max.

12. martedì 3/4/18 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). Esempi numerici su Excel Solver.

11. giovedì 29/3/18 Tagli di Gomory (rif. Fischetti Sez. 6.3; dispensa di L. Galli - U.Pisa; dispensa di G. Lancia - U. Udine)

10. martedì 27/3/18 Algoritmi basati su "piani di taglio": Diseguaglianze di Chvátal. Ancora su modelli di PLI: min di max di funzioni, min di funzione modulo (rif. Fischetti Sez. 6.3 e/o anche questa dispensa di L. Galli - U.Pisa)

9. lunedì 26/3/18 Formulazione PLI di funzioni booleane (rif. dispensa su problemi di decisione e ottimizzazione combinatoria).

8. giovedì 22/3/18 Programmazione dinamica. Principio di ottimalità. Esempio: cammino minimo su grafo orientato, equazioni di Ford-Bellman (relazioni di dualità). Algoritmo di programmazione dinamica per il problema di knapsack binario (rif. dispensa).

7. martedì 20/3/18 Ancora su concetti di dualità (rif. Fischetti Sez. 5.1-5.5) e sulla generazione colonne per un problema di cutting stock (rif. Sassano Sez. 4.2.3).

6. lunedì 19/3/18 Rappresentazione "implicita" di un poliedro: oracolo di separazione e il metodo del simplesso "dinamico". Applicazione a un problema di cammino minimo su grafo non orientato. Metodo del simplesso dinamico duale: metodi di generazione colonne. Applicazione a un problema di cutting stock (rif. Sassano Sez. 4.2.3. Un interessante riferimento anche qui).

5. giovedì 15/3/18 Totale unimodularità: condizioni sufficienti. Due esempi notevoli: la matrice di incidenza per un grafo non orientato bipartito e per un grafo orientato. Applicazione ai problemi di assegnamento e flusso a costo minimo.

4. martedì 13/3/18 Esempi di problemi di OC: subset sum, assegnamento. Formulazioni lineari e loro qualità. Totale unimodularità (rif. Fischetti, Sez. 6.1 e 6.2)

3. lunedì 12/3/18 Ancora sul modello PLI del problema di localizzazione. Introduzione ai problemi di ottimizzazione intera: concetto di "formulazione" e sua qualità (rif. Sassano, Sez. 4.2). Problemi di ottimizzazione combinatoria (OC) (rif. dispensa su problemi di decisione e ottimizzazione combinatoria).

2. giovedì 8/3/18 Ancora sulla PL. Costi ridotti e loro espressione. Esempio: problema di localizzazione: scrittura di un modello PLI.

1. martedì 6/3/18 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, costi ridotti) (rif. Fischetti, Cap.1, 2 e 3).