INFORMAZIONI SU

Modelli e algoritmi per le decisioni

Programma dell'insegnamento di Modelli e algoritmi per le decisioni - Corso di laurea magistrale in Informatica (2012/13)

Docente

Prof. Giuseppe Lancia giuseppe.lancia@uniud.it http://www.dimi.uniud.it/lancia

Crediti

6 CFU

Finalità

L'obiettivo del corso e' quello di presentare le principali metodologie modellistiche, e i corrispondenti algoritmi risolutivi, utilizzate per la soluzione di problemi computazionalmente difficili (come ad esempio la schedulazione di macchine e personale).
In particolare, si analizzeranno tre linee di attacco a tali problemi:
(i) algoritmi esatti, (ii) algoritmi approssimati e (iii) algoritmi euristici (ricerca locale).
Relativamente agli algoritmi esatti verra' data particolare enfasi ai modelli di programmazione lineare intera con un numero esponenziale di vincoli e/o variabili, descrivendo le metodologie di branch-and-cut e branch-and-price, nonche' una valida alternativa per la soluzione di tali modelli, i.e., l'ottimizzazione compatta.
Gli algoritmi approssimati verranno descritti tramite numerosi esempi su alcuni classici problemi di ottimizzazione. Infine, verranno esposte alcune fra le meta-euristiche di maggior successo, quali la tabu-search e gli algoritmi genetici.
Al termine del corso lo studente dovrebbe essere in grado di modellare un problema non troppo complesso di gestione e pianificazione, e proporre adeguati strumenti di risoluzione dello stesso.

Programma

Modelli di programmazione lineare intera esponenziali. Branch and Cut and/or Price. Modelli compatti e loro equivalenza ai modelli esponenziali. Problemi di schedulazione. Problema a una e due macchine.
Generalizzazione alle deadlines. Il problema del Job shop e la Shifting Bottleneck Procedure. Algoritmi di approssimazione. Schemi di approssimazione di tempo polinomiale (PTAS e FPTAS). Algoritmi di approssimazione randomizzati e loro de-randomizzazione. Tecniche di ricerca locale. Metaeuristiche. Algoritmi genetici e tabu search.

Bibliografia

-Dispense del docente
-Fotocopie di articoli
-"Combinatorial Optimization: Algorithms and Complexity", di C. Papadimitriou e K. Steiglitz, Dover 1982 -"Approximation Algorithms for NP-hard problems", di D. Hochbaum, 1996

Modalità d'esame

Esame orale