Portale di Ateneo - Unibs.it Portale di Ateneo - Unibs.it

Mutuazioni

OPTIMIZATION ALGORITHMS

COMMUNICATION TECHNOLOGIES AND MULTIMEDIA - TECNOLOGIE DELLE COMUNICAZIONI E MULTIMEDIA

PERCORSO COMUNE
OPTIMIZATION ALGORITHMS

INGEGNERIA INFORMATICA

comune
OPTIMIZATION ALGORITHMS

INGEGNERIA GESTIONALE

comune
OPTIMIZATION ALGORITHMS

INGEGNERIA DELL'AUTOMAZIONE INDUSTRIALE

PERCORSO COMUNE
OPTIMIZATION ALGORITHMS

INGEGNERIA GESTIONALE

comune
OPTIMIZATION ALGORITHMS

COMMUNICATION TECHNOLOGIES AND MULTIMEDIA - TECNOLOGIE DELLE COMUNICAZIONI E MULTIMEDIA

PERCORSO COMUNE

Altri insegnamenti del Corso di studio

Anno di corso: 1

ADAPTIVE CONTROL SYSTEMS - 6 crediti - Caratterizzante
ALGEBRA PER CODICI E CRITTOGRAFIA - 6 crediti - A scelta dello studente
ALGORITMI E STRUTTURE DATI - 9 crediti - Caratterizzante
AMMINISTRAZIONE DI SISTEMA - 6 crediti - Caratterizzante
ANALISI APPLICATA - 6 crediti - Raggruppamento di frequenza - A scelta dello studente
ANALISI E CONTROLLO DI PROCESSI COMPLESSI - 6 crediti - Caratterizzante
CALCOLO SCIENTIFICO - 6 crediti - Affine/Integrativa
CONTROL SYSTEMS TECHNOLOGIES - 9 crediti - A scelta dello studente
DATA-DRIVEN SYSTEM MODELLING - 6 crediti - Caratterizzante
DIGITAL AUDIO PROCESSING - 6 crediti - A scelta dello studente
DIGITAL IMAGE PROCESSING - 6 crediti - Affine/Integrativa
ELABORAZIONE NUMERICA DEI SEGNALI - 6 crediti - Affine/Integrativa
ELEMENTI DI BIOLOGIA E BIOMEDICINA - 6 crediti - Raggruppamento di frequenza - A scelta dello studente
FUNDAMENTALS OF COMPUTER GRAPHICS - 3 crediti - A scelta dello studente
GESTIONE AZIENDALE (STRATEGIA E MARKETING) - 6 crediti - Affine/Integrativa
HEALTH INFORMATION SYSTEMS - 6 crediti - Caratterizzante
INFORMATICA GIURIDICA - 6 crediti - A scelta dello studente
MACHINE LEARNING E DATA MINING - 6 crediti - Caratterizzante
MODELLI DI DIFFUSIONE - 3 crediti - A scelta dello studente
MODELLI DI SUPPORTO ALLE DECISIONI - 6 crediti - A scelta dello studente
MODELLISTICA E SIMULAZIONE - 6 crediti - Caratterizzante
NETWORK SECURITY - 6 crediti - Affine/Integrativa
ONDE DI SHOCK - 3 crediti - A scelta dello studente
OPTIMIZATION ALGORITHMS - 6 crediti - Affine/Integrativa
ORGANIZZAZIONE E GESTIONE DELL'INNOVAZIONE - 9 crediti - A scelta dello studente
PLC E SCADA - 3 crediti - A scelta dello studente
SENSORI INTELLIGENTI E BUS DI CAMPO - 6 crediti - A scelta dello studente
SISTEMI DI VISIONE 3D - 6 crediti - A scelta dello studente
SISTEMI INFORMATIVI, PROGRAMMAZIONE WEB E SERVIZI DIGITALI - 12 crediti - Raggruppamento di frequenza
TECNOLOGIE DEI LINGUAGGI ARTIFICIALI - 6 crediti - A scelta dello studente
TRAFFIC MODELLING AND STREAMING - 3 crediti - A scelta dello studente
WIRELESS SYSTEMS LABORATORY - 3 crediti - A scelta dello studente

Anno di corso: 2

ADAPTIVE CONTROL SYSTEMS - 6 crediti - A scelta dello studente
ALGEBRA PER CODICI E CRITTOGRAFIA - 6 crediti - A scelta dello studente
ANALISI E CONTROLLO DI PROCESSI COMPLESSI - 6 crediti - Caratterizzante
CONTROL SYSTEMS TECHNOLOGIES - 9 crediti - A scelta dello studente
DATA-DRIVEN SYSTEM MODELLING - 6 crediti - Caratterizzante
DEEP LEARNING - 3 crediti - A scelta dello studente
DIGITAL AUDIO PROCESSING - 6 crediti - A scelta dello studente
DIGITAL IMAGE PROCESSING - 6 crediti - Affine/Integrativa
ELABORAZIONE NUMERICA DEI SEGNALI - 6 crediti - Affine/Integrativa
ELEMENTI DI BIOLOGIA E BIOMEDICINA - 6 crediti - Raggruppamento di frequenza - A scelta dello studente
FONDAMENTI DI INTELLIGENZA ARTIFICIALE - 6 crediti - A scelta dello studente
FUNDAMENTALS OF COMPUTER GRAPHICS - 3 crediti - A scelta dello studente
GESTIONE AZIENDALE (STRATEGIA E MARKETING) - 6 crediti - Affine/Integrativa
HEALTH INFORMATION SYSTEMS - 6 crediti - Caratterizzante
INFORMATICA GIURIDICA - 6 crediti - A scelta dello studente
INFORMATION THEORY - 6 crediti - A scelta dello studente
INNOVAZIONE DIGITALE E GESTIONE DELLA CONOSCENZA - 9 crediti - Caratterizzante
INTELLIGENZA ARTIFICIALE - 9 crediti - Caratterizzante
INTERAZIONE UOMO-MACCHINA - 6 crediti - Caratterizzante
MACHINE LEARNING E DATA MINING - 6 crediti - Caratterizzante
MOBILE PROGRAMMING - 6 crediti - A scelta dello studente
MODELLI DI SUPPORTO ALLE DECISIONI - 6 crediti - A scelta dello studente
MODELLISTICA E SIMULAZIONE - 6 crediti - Caratterizzante
NETWORK SECURITY - 6 crediti - Affine/Integrativa
OPTIMIZATION ALGORITHMS - 6 crediti - Affine/Integrativa
ORGANIZZAZIONE E GESTIONE DELL'INNOVAZIONE - 9 crediti - A scelta dello studente
PLC E SCADA - 3 crediti - A scelta dello studente
PROVA FINALE - 12 crediti - Lingua/Prova Finale
ROBOT INDUSTRIALI E DI SERVIZIO - 6 crediti - A scelta dello studente
ROBOTICA - 9 crediti - Caratterizzante
SENSORI INTELLIGENTI E BUS DI CAMPO - 6 crediti - A scelta dello studente
SICUREZZA INFORMATICA - 6 crediti - Caratterizzante
SISTEMI DI VISIONE 3D - 6 crediti - A scelta dello studente
SISTEMI INFORMATIVI EVOLUTI - 6 crediti - A scelta dello studente
SISTEMI INFORMATIVI EVOLUTI E BIG DATA - 9 crediti - Caratterizzante
STAGE/PROGETTO 6 CFU - LM - 6 crediti
TECNOLOGIE DEI LINGUAGGI ARTIFICIALI - 6 crediti - A scelta dello studente
VEHICULAR NETWORKS AND COOPERATIVE DRIVING - 6 crediti - A scelta dello studente

OPTIMIZATION ALGORITHMS

Attività formativa monodisciplinare

Scheda dell'insegnamento

Codice attività didattica:

A004022

Anno accademico di immatricolazione:

2019/2020

Anno accademico di erogazione:

2019/2020

Tipologia di insegnamento:

Affine/Integrativa

Afferenza:

Corso di Laurea Magistrale in INGEGNERIA INFORMATICA

Settore disciplinare:

RICERCA OPERATIVA (MAT/09)

Lingua:

Inglese

Crediti:

Anno di corso:

Docente e Collaboratori:

MANSINI Renata Responsabile

ZANOTTI Roberto Collaboratore

Ciclo:

Primo Semestre

Ore di attivita' frontale:

Ore di studio individuale:

Prerequisiti:

Teoria e metodi risolutivi della Programmazione Lineare. Tecniche per
formulare modelli matematici di programmazione lineare e
programmazione lineare intera.

Obiettivi formativi

Costituisce scopo del corso sviluppare le nozioni di base del corso di Ricerca Operativa introducendo lo studente all'Ottimizzazione Combinatoria e alle principali tecniche per la risoluzione esatta e euristica dei problemi di ottimizzazione lineare intera. Particolare
attenzione verrà dedicata all'aspetto algoritmico e alle applicazioni.

Contenuti

Introduzione all'ottimizzazione combinatoria. Formulazioni strong e Convex Hull. Algoritmi esatti (Branch-and-Bound, Cutting Planes, Branch-and-Cut). Problemi di separazione e loro risoluzione. Problemi polinomiali su reti. Algoritmi euristici e meta-euristici (Tabu Search, Variable Neighborhood Search, Adaptive Large Neighborhood Search, Kernel Search). Applicazione delle tecniche
apprese a problemi di node routing e arc routing. Studio delle principali proprietà dei problemi di arc routing. Algoritmi approssimati ed analisi del caso peggiore (problema del commesso viaggiatore, problema di bin packing, problema del maximum independent set, problema di minimum vertex cover, problema dello zaino binario). Cenni di Ottimizzazione Bilivello con esempi applicativi.

Programma esteso

1. Introduzione ai problemi di Ottimizzazione Combinatoria (OC). Definizione di problema combinatorio. Modelli, proprietà e applicazioni dei problemi di OC. Formulazioni alternative per problemi di OC. Formulazioni strong e rilassamento continuo; Convex Hull. Esempi di formulazioni alternative (problema di albero ricoprente a costo minimo, problema di
Perfect Matching).

2. Problemi polinomiali su reti.
Reti di flusso: definizioni fondamentali. Totale unimodularità. Problema di
Massimo Flusso: modellizzazione e proprietà. Teorema di massimo
flusso-minimo taglio. Algoritmo di Ford-Fulkerson. Applicazioni.

3. Introduzione ai problemi di Arc e Node Routing. Proprietà e differenze. Condizioni necessarie e sufficienti per grafi euleriani. Problema del Chinese Postman Problem. Complessità del problema. Problema del Rural Postman Problem. Complessità e casi particolari. Algoritmi risolutivi. Capacitated Arc Routing Problem: proprietà e formulazione matematica.

4. Algoritmi euristici e meta-euristici.
Algoritmi costruttivi e di miglioramento. Algoritmi di ricerca locale. Esempi: algoritmi 2-opt e 3-opt per il problema del commesso viaggiatore. Metodi Greedy. Meta-euristiche: Tabu Search, Variable Neighborhood Search, Adaptive Large Neighborhood Search e Kernel Search. Proprietà dei metodi. Applicazione delle metodologie viste a problemi di node routing e arc routing.

5. Algoritmi esatti.
Algoritmi poliedrali. Metodo di Branch and Bound: proprietà e limiti. Disuguaglianze valide e problemi di separazione. Metodo di Cutting Planes. Taglio di Gomory e Taglio di Dantzig. Tagli generici e tagli specifici: esempi. Classi di disuguaglianze valide e algoritmi di
separazione esatti e euristici. Applicazione del metodo al problema del
commesso viaggiatore e ad un problema di selezione degli indici in un
data base relazionale.

6. Algoritmi approssimati.
Proprietà e caratteristiche dei metodi approssimati. Analisi del caso
peggiore. Algoritmo del Tree Algorithm per il problema del commesso viaggiatore. Algoritmo di ordinamento per il problema di maximum independent set. Algoritmo del Next Fit per il problema di bin packing.
Algoritmo basato sul rilassamento lineare per il problema di vertex cover.
Algoritmi greedy per il problema dello zaino binario.

7. Ottimizzazione Bilivello. Definizione e proprietà. Classi di problemi. Metodologie risolutive.

Bibliografia consigliata

D. BERTSIMAS, J.N. TSITSIKLIS, Introduction to Linear Optimization, Athena Scientific, Belmont, Massachusetts 1997.
G. AUSIELLO, P. CRESCENZI, G. GAMBOSI, V. KANN, A. MARCHETTISPACCAMELA, M. PROTASI, Complexity and Approximation, Springer
Verlag 1999.

C.PAPADIMITRIOU, K.STEIGLITZ, Combinatorial Optimization, Prentice
Hall, 1982.

M. GAREY, D. JOHNSON, Computers and Intractability: a Guide to the
Theory of NP-Completeness, Freeman, 1979.

Testi disponibili nel catalogo delle biblioteche

Ultimo aggiornamento 22/09/2020

Si invitano gli studenti a verificare sempre la corrispondenza tra la bibliografia consigliata e i testi disponibili

Combinatorial optimization : algorithms and complexity / Christos H. Papadimitriou, Kenneth Steiglitz. - Englewood Cliffs (NJ) : Prentice-Hall, c1982 Vedi nel catalogo
Computers and intractability : a *guide to the theory of NP-completeness / Michael R. Garey, David S. Johnson. - San Francisco : Freeman, c1979 Vedi nel catalogo
Complexity and approximation : combinatorial optimization problems and their approximability properties / Giorgio Ausiello - Berlin [etc.] : Springer. c1999. Vedi nel catalogo
Introduction to linear optimization / Dimitris Bertsimas, John N. Tsitsiklis - Belmont : Athena scientific. 1997. Vedi nel catalogo

Modalità di erogazione

Convenzionale

Metodi didattici

Lezioni di teoria affiancate da esercitazioni. Discussione e soluzione in aula di problemi applicativi e di articoli scientifici. Attività progettuale svolta in gruppi costituiti da studenti di differente formazione. La finalità è quella di favorire l’applicazione della conoscenza acquisita e lo sviluppo delle abilità di comunicazione e giudizio critico.

Metodi di valutazione

Modalita' di verifica dell'apprendimento:

L'esame prevede una prova scritta di teoria e una prova orale focalizzata sulla discussione dei risultati ottenuti nel progetto assegnato all'inizio del corso. A ciascun gruppo di studenti è inoltre assegnato un articolo tratto dalla letteratura scientifica e riguardante modelli e algoritmi di ottimizzazione di cui si richiede l’analisi e una presentazione critica in aula. Sono previsti momenti di discussione sulle difficoltà incontrate nell'affrontare la risoluzione del progetto e lo studio della letteratura scientifica. Ogni studente è tenuto a sostenere una breve presentazione della propria attività svolta nel gruppo con lo scopo di verificarne l'autonomia di giudizio e la capacità di apprendimento.

Valutazione:

Voto Finale

Calendario attività didattiche

Data di inizio del periodo didattico:

Lunedì, 16 Settembre, 2019

Data di fine del periodo didattico:

Venerdì, 20 Dicembre, 2019

Altre informazioni

Sono disponibili slide relative sia alle lezioni di teoria sia alle esercitazioni svolte in aula. Tutto il materiale didattico è disponibile sul sito di E-learning d'Ateneo (comunità didattica di ESSE3).