91717 - ALGORITHMS FOR COMBINATORIAL OPTIMIZATION PROBLEMS M

Anno Accademico 2020/2021

  • Docente: Paolo Toth
  • Crediti formativi: 6
  • SSD: MAT/09
  • Lingua di insegnamento: Inglese
  • Modalità didattica: Convenzionale - Lezioni in presenza
  • Campus: Bologna
  • Corso: Laurea Magistrale in Ingegneria informatica (cod. 0937)

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 piu` efficienti 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. Utilizzazione del software CPLEX per la soluzione di modelli di Programmazione Lineare e Programmazione Lineare Intera e Mista.

4. Algoritmi esatti per la soluzione di problemi NP-difficili. Algoritmi “branch-and-bound”: alberi decisionali, tecniche di rilassamento, miglioramento dei rilassamenti, tecnica del subgradiente, criteri di dominanza, tecnica del core problem; 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”).

5. 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”.

6. 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”).

7. Analisi sperimentale delle prestazioni computazionali degli algoritmi proposti.

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

Testi/Bibliografia

Testi di consultazione:

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.

C. Barnhart, G. Laporte (editors), Transportation, Handbooks in Operations Research and Management Science, North Holland, 2007.

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;

Esercitazioni in Laboratorio.

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. Prova opzionale di utilizzazione del Package CPLEX.

Strumenti a supporto della didattica

Trasparenze a cura del docente (distribuite durante le lezioni e disponobili sul sito del corso).

Orario di ricevimento

Consulta il sito web di Paolo Toth

SDGs

Città e comunità sostenibili Consumo e produzione responsabili

L'insegnamento contribuisce al perseguimento degli Obiettivi di Sviluppo Sostenibile dell'Agenda 2030 dell'ONU.