Algoritmi E Modelli Per L'ottimizzazione Discreta 2017/2018

1. Programmazione lineare (ricapitolazione): principi base, cenni metodo del simplesso, dualità, condizioni di ottimalità.

2. Programmazione lineare intera:

- Modelli di Programmazione Lineare Intera.

- Formulazione e loro qualità.

- Totale unimodularità. Esempi: problema dell'Assegnamento (Bipartite matching). Problema dei trasporti.

- Metodi per la PLI: Branch-and-bound, Branch-and-bound combinatori, Gomory-cuts. Programmazione Dinamica 

3. Programmazione lineare e lineare intera:

- formulazioni "non compatte".

- Metodi per la soluzione di PL non compatti: Problema di separazione e pricing (column generation/cut generations). Esempi: cutting stock, shortest (s,t)-path.

4. Rilassamento di un problema di ottimizzazione intera:

- Continuo,

- Lagrangiano,

- Altri tipi di rilassamento di un PLI, 

- Esempi.

5. Algoritmi approssimati: 

- Principi di base, definizione, esempi (TSP, Multiprocessor scheduling).

- Metodi primali-duali per l'approssimazione di PLI. Esempio: facility location.

6. Approfondimenti:

- Cenni di teoria della complessità computazionale.

- Algoritmi randomizzati per problemi di ottimizzazione deterministici.

7. Case study:

- Vehicle Routing Problem.