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.
•  

MODALITA' DIDATTICHE

Lezioni frontali ed esercitazioni.

PROGRAMMA/CONTENUTO

INTRODUZIONE ALLA RICERCA OPERATIVA

Le origini della Ricerca Operativa.

Problemi reali e modelli matematici. Limiti dei modelli.

Obiettivi, variabili decisionali, vincoli.

Classificazioni dei problemi di ottimizzazione.

Dimensione dei problemi e inefficienza degli algoritmi “brute force”.

Un esempio numerico introduttivo.

Il ruolo e l’utilità della Ricerca Operativa nell’ambito dell’ICT.

PROGRAMMAZIONE LINEARE (PL)

Modelli di PL di importanza applicativa.

Esempio grafico introduttivo.

Algebra e geometria della PL.

Algoritmo del simplesso. Interpretazioni algebrica e geometrica. Simplesso sul tableau.

Analisi di post-ottimalità.

DUALITÀ

Problemi duali: modelli di PL di importanza applicativa.

Dualità debole e dualità forte.

Interpretazione economica della dualità (prezzi ombra).

Slackness complementare.

PROGRAMMAZIONE LINEARE A NUMERI INTERI (PLI)

Modelli di PLI di importanza applicativa (Matching, Sequencing, Fixed-Charge, Knapsack, Steiner Tree, Plant Location, Scheduling). 

Algebra e geometria della PLI. Matrici totalmente unimodulari.

Algoritmo di tipo branch-and-bound.

Algoritmo basati su piani di taglio. Tagli di Gomory.

Algoritmi di tipo branch-and-cut.

GRAFI E RETI

Definizioni e generalità sui grafi.

Rappresentazione dei grafi.

Il problema di Shortest Path (SP) e il suo modello di PLI. Algoritmo di Dijkstra. Algoritmo di Bellman-Ford.

Il problema di Shortest Spanning Tree (SST) e il suo modello di PLI. Algoritmo di Kruskal. Algoritmo di Primm-Dijkstra.

Algoritmi greedy.

Cenni al Travelling Salesman Problem (TSP) e al suo modello di PLI.

“CASE-STUDIES” IN AMBITO INFORMATICO

Stima del worst-case execution time (WCETP: “Worst-Case Execution Time Problem”) di un programma

Control flow graph per WCETP

Modello di PLI per WCETP

Il problema della selezione degli indici (ISP: “Index Selection Problem”) nei database relazionali

Modello di PLI per ISP

Risoluzione di ISP con mediante branch-and-bound

Risoluzione di ISP con mediante branch-and-cut

Confronto numerico fra le due metodologie di risoluzione per ISP

CENNI ALLA TEORIA DELLA COMPLESSITÀ

Concetto di istanza e dimensione di un'istanza.

Complessità computazionale di un algoritmo.

Problemi trattabili ed intrattabili. Problemi in forma decisionale.

Classi P, NP e co-NP. Concetto di algoritmo non-deterministico.

Il teorema di Cook. La classe dei problemi NP-completi.

Esempi di problemi NP-completi e rispettivi modelli di PLI: knapsack, Steiner tree, …

Problemi NP-hard.

PROGRAMMAZIONE DINAMICA (PD) 

Esempio introduttivo.

Problemi di ottimizzazione a stadi. Contesto deterministico.

Fase backward e fase forward.

Principio di ottimalità.

Le equazioni di Bellman.

Estensione al contesto stocastico.

La “maledizione della dimensionalità”.

CENNI ALLA PROGRAMMAZIONE NON LINEARE (PNL)

PNL libera:

Esistenza e caratterizzazione dei minimi. Condizioni necessarie e sufficienti. Metodi del gradiente. Metodo di Newton-Raphson. Velocità di convergenza.

PNL vincolata:

Esistenza e caratterizzazione dei minimi. Condizioni necessarie e sufficienti. Moltiplicatori di Lagrange. Metodi con funzioni di penalità. Metodi barriera o a punto interno.

ESERCITAZIONI

• Esercizi sugli argomenti del Corso.
• Strumenti software per la Ricerca Operativa (Lingo, Matlab Optimization Toolbox, ecc.).

TESTI/BIBLIOGRAFIA

Dispense fornite dal Docente.