OPERATIONS RESEARCH

OPERATIONS RESEARCH

_
iten
Codice
80155
ANNO ACCADEMICO
2018/2019
CFU
9 cfu al 1° anno di 8733 INGEGNERIA INFORMATICA (LM-32) GENOVA
SETTORE SCIENTIFICO DISCIPLINARE
MAT/09
SEDE
GENOVA (INGEGNERIA INFORMATICA )
periodo
1° Semestre
materiale didattico

PRESENTAZIONE

Il Corso introduce a modelli e metodi di ottimizzazione utilizzabili per la soluzione di problemi decisionali. Si articola nei temi fondamentali della modellazione di problemi, dello studio della trattabilità computazionale e della risoluzione tramite algoritmi implementabili su un calcolatore. La materia viene presentata nei suoi aspetti metodologici, teorici ed applicativi. Vengono considerati vari contesti applicativi e sono trattati in dettaglio "case-studies" in ambito informatico.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

Il Corso introduce a modelli e metodi di ottimizzazione utilizzabili per la soluzione di problemi decisionali. Si articola nei temi fondamentali della modellazione di problemi, dello studio della trattabilità computazionale e della risoluzione tramite algoritmi implementabili su un calcolatore. Vengono considerati vari contesti applicativi e sono trattati in dettaglio alcuni "case-study" in ambito informatico. Scopo del Corso è far acquisire le competenze che consentano di affrontare problemi applicativi, sviluppando modelli e metodi che operino in modo efficiente in presenza di risorse limitate. Agli studenti verrà insegnato a: interpretare e modellare un processo decisionale nei termini di un problema di ottimizzazione, individuando cioè le variabili decisionali, la funzione di costo da minimizzare (o la cifra di merito da massimizzare) e i vincoli; inquadrare il problema nella gamma dei problemi considerati “canonici” (lineari/non lineari, discreti/continui, deterministici/stocastici, statici/dinamici, ecc.); realizzare il "matching" tra l’algoritmo risolutivo (da scegliere tra quelli esistenti o da progettare) e un adeguato supporto software di elaborazione.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

Scopo del Corso è far acquisire le competenze che consentano di affrontare problemi applicativi, sviluppando modelli e metodi che operino in modo efficiente in presenza di risorse limitate. Agli studenti verrà insegnato a:

  • interpretare e modellare un processo decisionale nei termini di un problema di ottimizzazione, individuando cioè le variabili decisionali, la funzione di costo da minimizzare (o la cifra di merito da massimizzare) e i vincoli;
  • inquadrare il problema nella gamma dei problemi considerati “canonici” (lineari/non lineari, discreti/continui, deterministici/stocastici, statici/dinamici, ecc.);
  • realizzare il "matching" tra l’algoritmo risolutivo (da scegliere tra quelli esistenti o da progettare) e un adeguato supporto software di elaborazione.

PREREQUISITI

Algebra lineare. Calcolo vettoriale e matriciale. Fondamenti di Analisi Matematica e Geometria.

Modalità didattiche

Lezioni frontali ed esercitazioni.

PROGRAMMA/CONTENUTO

INTRODUZIONE ALLA RICERCA OPERATIVA (RO)

Le origini della RO

Problemi reali e modelli matematici

Obiettivi, variabili decisionali, vincoli

Esempi introduttivi e limiti dei modelli

Dimensione dei problemi

Inefficienza degli algoritmi “brute force”

La RO sul grande schermo, ovvero “Hollywood e la RO”

Classificazioni dei problemi di ottimizzazione

Il ruolo della RO nell’Informatica

PROGRAMMAZIONE LINEARE (PL)

Esempio introduttivo: un modello di PL nell’Informatica

Altri modelli di PL di importanza applicativa

Esempio grafico introduttivo

Algebra e geometria della PL

Algoritmo del simplesso: punto di vista algebrico e punto di vista geometrico

Simplesso sul tableau

Analisi di post-ottimalità

DUALITÀ

Modelli duali di importanza applicativa

Dualità debole e dualità forte

Interpretazione economica della dualità (prezzi ombra)

Slackness complementare

PROGRAMMAZIONE LINEARE A NUMERI INTERI (PLI)

Esempio introduttivo: un modello di PLI nell’Informatica

Alcuni modelli di PLI di importanza applicativa

                     Matching

                     Sequencing

                     Fixed-Charge

                     Knapsack

Algebra e geometria della PLI

Il concetto di “enumerazione implicita”

Algoritmo di tipo branch-and-bound. Criteri di esplorazione dell’albero di branch-and-bound

Algoritmo basati su piani di taglio. Tagli di Gomory

Algoritmi di tipo branch-and-cut

CENNI ALLA COMPLESSITÀ

Concetto di istanza e dimensione di un'istanza

Complessità computazionale di un algoritmo

Problemi trattabili e problemi intrattabili

Problemi in forma decisionale

Classi P, NP e co-NP

Trasformazioni polinomiali

La classe dei problemi NP-completi

Forma normale congiuntiva nella logica Booleana

ll problema della soddisfacibilità

Il Teorema di Cook

Esempi di problemi NP-completi e NP-hard

Ricadute applicative e computazionali della Teoria della Complessità

GRAFI E RETI

Grafi e loro rappresentazioni

                     Grafi orientati e non orientati

                     Sottografi e sottografi indotti

                     Grado, stella, grafi completi, densità, grafi densi e grafi sparsi

                     Clique massime e massimali

                     Matrice di incidenza e matrice di adiacenza

                     Grafi connessi e componenti connesse

                     Cammini, cammini semplici, cicli

                     Percorsi e cicli hamiltoniani

                     Percorsi e cicli euleriani

                     Alberi, foreste, alberi ricoprenti

Esempi di problemi di Informatica modellabili su grafi

Shortest Path (SP)

                     Modello su grafo

                     Modello di PLI

                     Studio della complessità

                     Algoritmo di Dijkstra

                     Algoritmo di Bellman-Ford

                     Algoritmo di Floyd-Warshall

Shortest Spanning Tree (SST)

                     Modello su grafi

                     Modello di PLI

                     Studio della complessità

                     Algoritmo di Kruskal. Il concetto di “algoritmo greedy”

                     Algoritmo di Prim-Dijkstra

Cenni al Travelling Salesman Problem (TSP)

                     Modello su grafo

                     Modello di PLI

                     Studio della complessità

                     Aspetti computazionali: i “TSP test data” disponibili in rete e il “TSP challange”

PROGRAMMAZIONE NON-LINEARE (PNL)

Esempio introduttivo: un modello di PLI nell’Informatica

PNL libera

                     Esistenza e caratterizzazione dei minimi

                     Ottimalità: condizioni necessarie e condizioni sufficienti

                     Velocità di convergenza degli algoritmi di PNL

                     Algoritmo del gradiente e algoritmi “gradient-based”

                     Algoritmo di Newton-Raphson

                     “Test functions” per la valutazione delle prestazioni degli algoritmi di PNL

                     Benchmark computazionali disponibili in rete              

PNL vincolata

                     Esistenza e caratterizzazione dei minimi

                     Ottimalità: condizioni necessarie e condizioni sufficienti

                     Gradiente proiettato

                     Moltiplicatori di Lagrange

                     Metodi basati sui Moltiplicatori di Lagrange

                     Metodi basati su funzioni di penalità

                     Metodi barriera o a punto interno

PROGRAMMAZIONE DINAMICA (PD)

Esempio introduttivo

Problemi di ottimizzazione a stadi. Contesto deterministico

Fase backward e fase forward

Principio di ottimalità

Le equazioni di Bellman

Cenni all’estensione al contesto stocastico

La “maledizione della dimensionalità”

Risoluzione del problema del Shortest Path (SP) mediante la PD

Risoluzione del Travelling Salesman Problem (TSP) mediante la PD

 

ALCUNI CASE-STUDY IN AMBITO INFORMATICO

Il problema dell’Index Selection Problem (ISP) nei database relazionali

                     Modello di PLI per ISP

                     Complessità di ISP

                     Risoluzione di ISP mediante algoritmo branch-and-cut

                     Considerazioni computazionali

                     Confronto fra branch-and-bound e branch-and-cut per ISP

Un problema di ottimizzazione su reti di computer

                    Formulazione come modello di PL

                    Risoluzione mediante l’algoritmo del simplesso

Stima di worst-case execution time di un programma

                     Modello su grafo: control flow graph

                     Modello di PLI

Modelli di PNL per l’apprendimento da dati

 

INTRODUZIONE AGLI STRUMENTI SOFTWARE PER LA RICERCA OPERATIVA

LINGO

CPLEX Optimization Studio

MATLAB Optimization Toolbox

EXCEL

ESERCITAZIONI

Svolte in modo distribuito durante il Corso

TESTI/BIBLIOGRAFIA

Dispense fornite dal Docente e disponibili in formato elettronico.

DOCENTI E COMMISSIONI

Ricevimento: Su appuntamento

LEZIONI

Modalità didattiche

Lezioni frontali ed esercitazioni.

INIZIO LEZIONI

17 settembre 2018

ESAMI

Modalità d'esame

Scritto.

Modalità di accertamento

Comprensione dei concetti esposti durante il Corso.

Capacità di:

- interpretare e modellare un processo decisionale nei termini di un problema di ottimizzazione, individuando cioè le variabili decisionali, la funzione di costo da minimizzare (o la cifra di merito da massimizzare) e i vincoli;

- inquadrare il problema nella gamma dei problemi considerati “canonici” (lineari/non lineari, discreti/continui, deterministici/stocastici, statici/dinamici, ecc.);

- scegliere e/o sviluppare un algoritmo risolutivo e utilizzarlo per risolvere il problema.

 

 

Calendario appelli

Data Ora Luogo Tipologia Note
05/09/2019 14:00 GENOVA Scritto

ALTRE INFORMAZIONI

Per il Corso di Laurea im Matematica, che mutua solo 7 cfu, sono esclusi dal programma i "capitoli"  

PROGRAMMAZIONE DINAMICA (PD)

ALCUNI CASE-STUDY IN AMBITO INFORMATICO