SILLABO

• Modulo Ottimizzazione Combinatoria

  • Prerequisiti: grafi, definizioni e proprietà fondamentali. Elementi di teoria della complessità computazionale. Esempi. Problemi di Ottimizzazione Combinatoria. Definizioni fondamentali. Esempi: trasversale (vertex-cover), insieme stabile, insieme dominante, edge-cover, matching (perfetto), knapsack, colorazione di un grafo (numero e indice cromatico), cammino minimo, sottografo ricoprente etc. Formulazioni come programmazione lineare 0-1.
  • Matrici unimodulari e totalmente unimodulari. Condizioni necessarie e condizioni sufficienti. Teorema di Hoffmann-Kruskal. Involucro convesso e formulazione ideale di un problema di PL intera. Esempi: cammino minimo, flusso a costo minimo, matching bipartito, grafi intervallo.
  • Cammini su grafi diretti aciclici (DAG) e programmazione dinamica. Esempi di applicazione: cammini ottimi su DAG, knapsack 0-1. [Proiezione di poliedri, sistemi di disequazioni lineari, Teorema di Fourier-Veronese, metodo di Fourier-Motzkin. Richiami di teoria della dualità nella programmazione lineare. Metodo primale duale. Esempio di applicazione: Metodo di Dijkstra].
  • Matroidi. Algoritmo Greedy. Definizione e caratterizzazione di un matroide (Teorema di Rado). Richiami di algebra lineare: dipendenza e indipendenza lineare, basi, unicità della rappresentazione, Teorema di Steinitz o dello scambio. Esempi: matroide banale, matroide grafico, matroide partizione, matroide vettoriale, [matroide matching]. Rappresentazione di matroidi. [Un applicazione industriale]. [Funzione rango, funzioni submodulari e supermodulari. Rango di un matroide. Funzione di supporto di un insieme convesso. Poliedro submodulare. Estensione di Lòvasz. Poliedro di un matroide, intersezione di matroidi, intersezione di due poliedri submodulari].
  • Algoritmi ad approssimazione garantita. Definizioni. Schemi polinomiali di approssimazione (PTAS, EPTAS, FPTAS). Esempi: TSP: double tree and Christofides; Knapsack 0-1.
  • Matching (perfetto/non perfetto, pesato/non pesato, bipartito/non bipartito). Diseguaglianze duali deboli: trasversale, numero di stabilità, edge-cover e matching. Il caso bipartito: Teoremi di Gallai e König. [Matrici bistocastiche e matching bipartito perfetto. Matching generale: poliedro del matching, Teorema di Edmonds].
  • Rilassamento lineare di un problema di programmazione lineare (mista) intera. Enumerazione implicita: metodo di branch-and-bound. Bound lineari, esempio: Knapsack intero, Knapsack 0-1. Dicotomia su una variabile frazionaria. Bound combinatorici, esempio: TSP.
  • [Separazione di un poliedro intero. Cenni sul Metodo dell’Ellissoide. Separazione e ottimizzazione: Generazione di diseguaglianze valide. Soluzione di PL con un numero esponenziale di disequazioni, esempi: Taglio minimo, TSP, Knapsack 0-1, Insieme Stabile].

  Modulo Ricerca Operativa

  • Problemi di Ottimizzazione: variabili di decisione, vincoli e obiettivi; tecniche di formulazione e classificazione dei modelli
  • Problemi di Ottimizzazione convessa; punti di ottimo locale e globale
  • Geometria della Programmazione Lineare
  • Il metodo del simplesso
  • Teoria delle dualità in Programmazione Lineare e sue applicazioni
  • Interpretazione duale del metodo del simplesso e metodo del simplesso duale