Ingegneria Gestionale - Management Engineering

FABIO FURINI
FABIO FURINI

Alla fine di questo corso lo studente dovrebbe essere in grado di:

Riconoscere le principali caratteristiche di in problema di ottimizzazione combinatoria con funzione obiettivo lineare e appartenente all'ampia classe dei problemi di Insieme Indipendente di Massimo Peso (MWIS) (matching, insieme stabile, knapsack, foreste ricoprenti, grafo connesso ricoprente, etc.);

Costruire efficaci formulazioni lineari (poliedri) per i problemi MWIS (Formulazione rango, Formulazione Circuito) e calcolare bound di buona qualità da utilizzare negli Algoritmi di Branch&Bound con il Metodo Dinamico del Simplesso ;

Riconoscere quando un Sistema di Indipendenza definisce una Matroide e dimostrare che il ben noto algoritmo "Greedy" trova sempre la soluzione ottima se il Sistema di Indipendenza è una Matroide;

Calcolare soluzioni euristiche con approssimazione garantita per mezzo dell'algoritmo approssimato Primale-Duale di Goemans-Williamson;

Calcolare bound di buona qualità (da inserire in un algoritmo di Branch&Bound) utilizzando il metodo del Rilassamento Lagrangiano e calcolare la soluzione ottima del Duale Lagrangiano con il metodo del "piano di taglio" o con il metodo del subgradiente;

Risolvere problemi applicativi realistici utilizzando opportune combinazioni degli strumenti descritti (Bound di buona qualità, Soluzioni approssimate, Formulazioni lineari etc.). Tra questi: Progetto dei Turni del personale Aereo, Progetto di cammini di costo minimo che rispettano un vincolo di sui tempi di percorrenza;

Avere una visione completa della soluzione di un problema realistico utilizzando tutti gli strumenti visti nel corso: In questo anno: Progetto di una Rete per mezzo di un algoritmo di Branch&Bound basato sulla Formulazione Semimetrica del problema di "Network Loading" (Dimensionamento delle Capacità).