Ingegneria Gestionale - Management Engineering

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à).