Mateuristiche per problemi di ottimizzazione combinatoria (Modulo 2)

L'Ottimizzazione Combinatoria è un vasto dominio di studio, concentrato su problemi di ottimizzazione con un insieme finito di soluzioni.
Ha importanti applicazioni pratiche a campi diversi, fra cui l'intelligenza artificiale, il machine learning, il routing, lo scheduling, la localizzazione, il progetto e l'analisi di reti.
Siccome molti problemi di Ottimizzazione Combinatoria sono NP-difficili, le euristiche sono un approccio risolutivo naturale.
Le mateuristiche, anche note col nome di euristiche basate su modelli,
sfruttano l'informazione fornita da modelli di programmazione matematica, cioe' dalla rappresentazione dello spazio delle soluzioni ammissibili attraverso uguaglianze e disuguaglianze imposte su opportune variabili di decisione. Il vantaggio di questi metodi rispetto alle euristiche e metaeuristiche classiche, basate su soluzioni,
consiste nell'informazione aggiuntiva che danno, per esempio in termini di garanzie a priori o a posteriori sulla qualità della soluzione restituita. Il primo modulo del corso introduce i concetti fondamentali della programmazione matematica
e passa in rassegna le mateuristiche basate su metodi di rilassamento e di decomposizione. Il secondo modulo del corso discute le mateuristiche che sfruttano la disponibilità di risolutori di programmazione matematica e quelle che interagiscono con metaeuristiche basate su soluzioni. I due moduli sono piuttosto indipendenti, ma il secondo richiede i concetti di base richiamati nel primo.