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 nel laboratorio di Laurea Magistrale al terzo piano (salvo evoluzione della pandemia)

Modulo 1

• mercoledì 02/02/2022: 10:30 - 13:00
• venerdì 04/02/2022: 10:30 - 13:00
• martedì 08/02/2022: 10:30 - 13:00
• venerdì 11/02/2022: 10:30 - 13:00

Modulo 2

• martedì 15/02/2022: 10:30 - 13:00
• venerdì 18/02/2022: 10:30 - 13:00
• martedì 22/02/2022: 10:30 - 13:00
• giovedì 24/02/2022: 10:30 - 13:00

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 (2 febbraio 2022)

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

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

Lezione 2 (4 febbraio 2022)

Euristiche approssimate. Euristiche duali.

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

Lezione 3 (8 febbraio 2022)

Tecniche di rilassamento. Euristiche lagrangiane. Euristiche surrogate.

• Lucidi
• Articoli di approfondimento
• Esercizi sul rilassamento lagrangiano

Lezione 4 (11 febbraio 2022)

Euristiche basate su decomposizioni.

• Lucidi
• Articoli di approfondimento

Lezione 5 (15 febbraio 2022)

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 (18 febbraio 2022)

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 (22 febbraio 2022)

Feasibility pump. Local branching.

• Lucidi
• Articoli di approfondimento

Lezione 8 (24 febbraio 2022)

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

• Lucidi
• Articoli di approfondimento