91717 - ALGORITHMS FOR COMBINATORIAL OPTIMIZATION PROBLEMS M

Conoscenze e abilità da conseguire

At the end of the course, the students are able to analyze the computational complexity and to define the Mixed Integer Linear Programming (MILP) models of the Combinatorial Optimization problems. The students are able to obtain tight relaxations of the MILP models, and to design exact enumerative algorithms (based on the branch-and-bound, branch-and-cut and branch-and-price approaches) for determining the optimal solution of the Combinatorial Optimization problems. The students are also able to solve the MILP models by using the software package CPLEX.

Contenuti

Il Corso si propone di illustrare i modelli matematici e gli algoritmi esatti più efficaci proposti per la soluzione di problemi NP-difficili di Ottimizzazione Combinatoria. Particolare attenzione viene dedicata al comportamento sperimentale dei modelli e degli algoritmi considerati.

Il Corso sviluppa i seguenti argomenti:

1. Classificazione dei problemi di ottimizzazione.

2. Modelli matematici e complessità computazionale di importanti problemi di ottimizzazione combinatoria.

3. Algoritmi esatti per la soluzione di problemi NP-difficili. Algoritmi “branch-and-bound”: alberi decisionali, tecniche di rilassamento; algoritmi per problemi di “Knapsack”, per il problema del circuito hamiltoniano a costo minimo in grafi orientati (“Asymmetric Travelling Salesman Problem”), per il problema della “copertura” a costo minimo (“Set Covering Problem”).

4. Algoritmi “branch-and-cut”: aggiunta di vincoli per il miglioramento dei rilassamenti, procedure di separazione per la soluzione di modelli con un numero elevato di vincoli; algoritmi per l'“Asymmetric Travelling Salesman Problem”.

5. Algoritmi “branch-an-price”: procedure di generazione di colonne per la soluzione di modelli con un numero elevato di variabili decisionali; algoritmi per problemi di “caricamento” di contenitori (“Bin Packing Problem”) e di “colorazione” di grafi (“Vertex Coloring Problem”).

6. Analisi sperimentale delle prestazioni computazionali degli algoritmi proposti.

Propedeuticità: moduli di base di Informatica e di Ricerca Operativa.

Testi/Bibliografia

S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, J. Wiley, 1990.

G. Gutin, A. Punnen (editors), The Traveling Salesman Problem and Its Variations, Kluwer, 2002.

Wiley Encyclopedia in Operations Research and Management Science, Wiley, 2011.

P. Toth, D. Vigo (editors), Vehicle Routing: Problems, Methods and Applications, MOS-SIAM Series on Optimization, 2014.

Metodi didattici

Lezioni in Aula;

Esercitazioni in Aula;

Modalità di verifica e valutazione dell'apprendimento

Prove scritte relative alla definizione di modelli matematici, all’analisi della complessità computazionale, alla definizione di problemi rilassati ed allo sviluppo di algoritmi esatti per la soluzione di problemi di ottimizzazione combinatoria NP-difficili.

Strumenti a supporto della didattica

Note del docente

Orario di ricevimento

Consulta il sito web di Enrico Malaguti

Consulta il sito web di Michele Monaci