Ottimizzazione Combinatoria

Crediti: 6.

Obiettivi formativi: Questo insegnamento si prefigge quale obiettivo principale l'introduzione degli studenti all'uso dei modelli di programmazione matematica con particolare attenzione rivolta ai modelli di ottimizzazione a variabili intere corrispondenti a problemi di decisione computazionalmente intrattabili ed alle loro applicazioni nei campi della logistica, dei servizi e della produzione industriale.

Contenuti: Introduzione ai problemi di ottimizzazione combinatoria e ai problemi in forma di riconoscimento. Classi di complessità P, NP, NP-hard e NP-completi. Classificazione dei metodi risolutivi (metodi esatti, metodi di approssimazione e metodi euristici). Algoritmi euristici e meta-euristici: Simulated Annealing; Tabù Search; Algoritmi Genetici; GRASP; Algoritmi di Ricerca Locale. Il problema del Commesso Viaggiatore (TSP). Problemi di distribuzione (Vehicle Routing).

Propedeuticità: Nessuna.

Modalità dell'esame: Colloquio finale.