Raccolta di appunti per ottimizzazione Combinatoria e Reti

Anno Accademico 2003/04

1. Introduzione

• 4. Ottimizzazione Combinatoria
  • 4.1 Introduzione

  • 4.2 Programmazione Lineare Intera (Mista)
    • 4.2.1 Il rilassamento continuo
    • 4.2.2 Formulazioni di PL equivalenti per la PLI
    • 4.2.3 Diseguaglianze valide

  • 4.3 Dimostrazioni di ottimalità

  • Riferimenti Bibliografici

  2. Algoritmi polinomiali di ottimizzazione di reti

  • 2.1. Flusso di costo minimo e cammini minimi.
    
  • 2.2. Flusso massimo.
    
  • 2.3. Albero di copertura di costo minimo.
    
  • 2.4 Problemi di accoppiamento.
    
  • 2.5 Routing in reti di comunicazione.
    
  • 2.6 Progetto di reti di comunicazione.
    

  3. Approcci euristici

• 5. Algoritmi euristici
  • 5.1 Algoritmi greedy
    • 5.1.1 Esempi di algoritmi greedy
    • 5.1.2 Algoritmi greedy con garanzia sulle prestazioni
    • 5.1.3 Matroidi

  • 5.2 Algoritmi di ricerca locale
    • 5.2.1 Esempi di algoritmi di ricerca locale
    • 5.2.2 Intorni di grande dimensione
    • 5.2.3 Metaeuristiche

  • Riferimenti Bibliografici

  4. Tecniche di rilassamento

• 6. Tecniche di rilassamento
  • 6.1 Rilassamento continuo
    • 6.1.1 Efficacia del rilassamento continuo
    • 6.1.2 Informazione generata dal rilassamento continuo

  • 6.2 Eliminazione di vincoli

  • 6.3 Rilassamento Lagrangiano
    • 6.3.1 Teoria del rilassamento Lagrangiano
    • 6.3.2 Algoritmi per il rilassamento Lagrangiano
    • 6.3.3 Informazione generata dal rilassamento Lagrangiano

  • 6.4 Rilassamento surrogato

  • Riferimenti Bibliografici

  5. Algoritmi esatti per problemi NP-ardui

• 7. Algoritmi enumerativi
  • 7.1 Algoritmi di enumerazione implicita
    • 7.1.1 Uno schema generale
    • 7.1.2 Implementare un algoritmo enumerativo
    • 7.1.3 Esempi di algoritmi enumerativi

  • 7.2 Programmazione dinamica

  • 7.3 Tecniche poliedrali

  • Riferimenti Bibliografici

  ---

  Aggiornamento: 13/01/2004