OBIETTIVI FORMATIVI

The Course introduces to optimization models and methods for the solution of decision problems. It is structured in the main topics of problem modelling, computational tractability, and solution by means of algorithms that can be implemented on a computer. Several applications are considered and various case studies are detailed. The target of the Course consists in making the students acquire the expertise to face decision problems by means of models and methods that can operate in the presence of limited resources. The students will be taught to: understanding and modelling a decision process in terms of an optimization problem by defining the decision variables, the cost function to be minimized (or the figure of merit to be maximized), and the constraints; framing the obtained problem within the range of the reference optimization problems (linear/nonlinear, discrete/continuous, deterministic/stochastic, static/dynamic, etc); achieving the matching between the corresponding solving algorithm and a suitable software.

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.

MODALITA' 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.