Salta al contenuto principale della pagina

OPERATIONS RESEARCH

CODICE 80155
ANNO ACCADEMICO 2022/2023
CFU
  • 9 cfu al 1° anno di 11160 COMPUTER ENGINEERING (LM-32) - GENOVA
  • SETTORE SCIENTIFICO DISCIPLINARE MAT/09
    LINGUA Inglese
    SEDE
  • GENOVA
  • PERIODO 1° Semestre
    MATERIALE DIDATTICO AULAWEB

    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" ingegneristici, con particolare attenzione a quelli in ambito informatico.

    Le lezioni sono organizzate in i) metodologia e ii) "case-study" provenienti da applicazioni "real-world". Esercizi addizionali e utilizzo di strumenti software sono presentati durante ore di esercitazione. 

    OBIETTIVI E CONTENUTI

    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.

    DOCENTI E COMMISSIONI

    LEZIONI

    Orari delle lezioni

    L'orario di tutti gli insegnamenti è consultabile su EasyAcademy.

    ESAMI

    MODALITA' D'ESAME

    Scritto, se sarà possibile fare esami in presenza. Altrimenti, il Docente deciderà se l'esame su Teams sarà orale o scritto.

     

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

    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