Programma del corso
Particolare enfasi verrà posta sulla costruzione dei modelli matematici, prendendo come esempio sia problemi di ottimizzazione tipici dell'ambito delle TLC e dell'elettronica, sia problemi classici di ottimizzazione combinatoria.
Parte del corso si terrà in laboratorio, utilizzando un solver state of the art per la soluzione di modelli di ottimizzazione (il pacchetto XPress di FICO, http://www.fico.com/en/products/fico-xpress-solver ).
Gli argomenti trattati sono i seguenti:
per la durata, si tenga presente che 1 lezione si svolge in uno slot di circa 2 ore e mezzo.
Introduzione alla programmazione matematica (ottimizzazione convessa, ottimizzazione vincolata/non vincolata, ottimi locali/globali) (1 lezione).
Cenni di complessità (1 lezione)
Programmazione lineare (PL): (interpretazione geometrica, condizioni di ottimalità, algoritmo del simplesso primale, dualità, simplesso duale) (4 lezioni).
Programmazione lineare (PL): (interpretazione geometrica, condizioni di ottimalità, algoritmo del simplesso primale, dualità, simplesso duale) (4 lezioni).
Problemi a variabili intere (PLI), teoria ed esercitazioni su un pacchetto per la PLI:
Programmazione lineare intera (matrici totalmente unimodulari, rilassamento continuo, disuguaglianze di Chvatal Gomory, algoritmo cutting plane, descrizione poliedrale, Branch and Bound, problema di separazione) (8 lezioni).
Rilassamenti (rilassamento lineare, rilassamento per cancellazione dei vincoli, rilassamento surrogato, rilassamento Lagrangeano e decomposizione Lagrangeana, nessi tra rilassamento Lagrangeano e teoria della dualità) (2 lezioni).
Programmazione lineare intera (matrici totalmente unimodulari, rilassamento continuo, disuguaglianze di Chvatal Gomory, algoritmo cutting plane, descrizione poliedrale, Branch and Bound, problema di separazione) (8 lezioni).
Rilassamenti (rilassamento lineare, rilassamento per cancellazione dei vincoli, rilassamento surrogato, rilassamento Lagrangeano e decomposizione Lagrangeana, nessi tra rilassamento Lagrangeano e teoria della dualità) (2 lezioni).
Ottimizzazione non lineare (solo cenni): (1 lezione).
- Ottimizzazione non vincolata: ottimizzazione lungo una direzione, ottimizzazione di funzioni differenziabili e non differenziabili.
- Ottimizzazione vincolata: condizioni di ottimo di KKT.
Tecniche di decomposizione: generazione di colonne, Branch and Cut, Branch and Price, decomposizione di Benders (7 lezioni).Ottimizzazione bilivello e Stackelberg game, reaction set e condizioni di esistenza di una soluzione (cenni) (1 lezione).
