Matheuristics for Combinatorial Optimization problems (Corso di dottorato)

Docenti

Il prof. Maurizio Bruglieri del Dipartimento di Design del Politecnico di Milano terrà il primo modulo, di 10 ore distribuite in quattro lezioni.

Il prof. Roberto Cordone del Dipartimento di Informatica dell'Università degli Studi di Milano terrà il secondo modulo, di 10 ore distribuite in quattro lezioni.

Orari e aule

Le lezioni si tengono presso il Dipartimento di Informatica in Via Celoria 18 a Milano

Modulo 1

• mercoledì 17/01/2024: 14:30 - 17:00 nel laboratorio di Laurea Magistrale al quinto piano
• venerdì 19/01/2024: 10:30 - 13:00 nel laboratorio di Laurea Magistrale al terzo piano
• martedì 23/01/2024: 10:30 - 13:00 nel laboratorio di Laurea Magistrale al terzo piano
• venerdì 26/01/2024: 10:30 - 13:00 nel laboratorio di Laurea Magistrale al terzo piano

Modulo 2

• martedì 30/01/2024: 14:30 - 17:00 nel laboratorio di Laurea Magistrale al terzo piano
• venerdì 02/02/2024: 14:30 - 17:00 nel laboratorio di Laurea Magistrale al terzo piano
• mercoledì 07/02/2024: 10:30 - 13:00 nel laboratorio di Laurea Magistrale al terzo piano
• venerdì 09/02/2024: 10:30 - 13:00 nel laboratorio di Laurea Magistrale al quinto piano

Esame

L'esame finale consiste in un seminario di circa un'ora su un argomento da concordare, legato ai contenuti del corso

Lezioni

Il corso si articola secondo la seguente agenda

Lezione 1 (17 gennaio 2024)

Introduzione all'Ottimizzazione Combinatoria e alla Programmazione Matematica. Euristiche di rounding.

• Lucidi
• Articoli di approfondimento
• Esercizi sulle formulazioni
• Soluzioni

Lezione 2 (19 gennaio 2024)

Euristiche approssimate. Euristiche duali.

• Lucidi
• Articoli di approfondimento
• Esercizi sugli algoritmi primali-duali
• Soluzioni

Lezione 3 (23 gennaio 2024)

Tecniche di rilassamento. Euristiche lagrangiane. Euristiche surrogate.

• Lucidi
• Articoli di approfondimento
• Esercizi sul rilassamento lagrangiano

Lezione 4 (26 gennaio 2024)

Euristiche basate su decomposizioni.

• Lucidi
• Articoli di approfondimento

Lezione 5 (30 gennaio 2024)

Introduzione al branch-and-bound e ai risolutori di Programmazione Lineare Intera.
Euristiche basate sulla limitazione dell'albero di branching.

• Lucidi
• Articoli di approfondimento
• Esercizi su risolutori e branch-and-bound
• Dati e soluzioni per gli esercizi sui risolutori
• Soluzioni e osservazioni

Lezione 6 (2 febbraio 2024)

Introduzione al branch-and-bound e ai risolutori di Programmazione Lineare Intera.
Introduzione alla Column Generation. Euristiche di column generation.

• Lucidi
• Articoli di approfondimento

Lezione 7 (7 febbraio 2024)

Feasibility pump. Local branching.

• Lucidi
• Articoli di approfondimento

Lezione 8 (9 febbraio 2024)

Introduzione alla ricerca locale. Euristiche basate sull'interazione fra risolutori e metodi di ricerca locale.

• Lucidi
• Articoli di approfondimento