Seminario - Ottimizzazione combinatoria attraverso programmazione lineare e formulazioni estese

Di seguito l'abstract dell'intervento:
L'ottimizzazione combinatoria è all'intersezione tra matematica discreta, informatica teorica e ricerca operativa. Tratta di problemi di ottimizzazione su un dominio discreto, spesso formulati tramite programmi interi (IP) o lineari (LP), la cui risoluzione spesso richiede un approccio sia geometrico sia combinatorio.  Quando si cerca di modellare un problema tramite disequazioni lineari, spesso è utile aggiungere variabili ausiliarie, ottenendo una formulazione estesa (ovvero in uno spazio di dimensione più alta) ma più facilmente rappresentabile (con un numero di disequazioni minori).
Verrà presentata una breve introduzione alla materia basata sull'esempio dell'albero ricoprente minimo (minimum spanning tree).