44015 - PROGRAMMAZIONE MATEMATICA

Conoscenze e abilità da conseguire

Al termine del corso lo studente conosce i principali metodi teorici ed algoritmici della programmazione matematica; è in grado di sviluppare per un problema reale modelli matematici alternativi; sa come realizzare un algoritmo di programmazione matematica per risolvere un problema reale.

Contenuti

Il corso include una prima parte in cui vengono discussi brevemente i concetti principali di Programmazione lineare e intera.

In particolare:
1. teoria della programmazione lineare e della dualità
2. programmazione lineare intera e branch-and-bound
3. complessità degli algoritmi
4. elementi e problemi della teoria dei grafi


La seconda parte del corso è sulla formulazione, mediante modelli di programmazione lineare intera, di problemi base NP-completi con particolare attenzione alla discussione sulla qualità del loro continuo rilassamento. Vengono discusse alcune applicazioni più complesse che coinvolgono modelli con un numero esponenziale di variabili e / o vincoli, tra cui la presentazione di tecniche di generazione di branch-and-cut e di colonne su alcuni esempi specifici.

Infine, viene discussa anche la definizione di approcci euristici per i problemi NP-completi.

Testi/Bibliografia

Slide e appunti delle lezioni dell'insegnante disponibili online.

Laurence A. Wolsey, Integer Programming, Wiley, 1998.

L'introduzione e le basi del corso possono essere trovate in
Christos H. Papadimitriou e Ken Steiglitz, Combinatorial optimization: algorithms and complexity, Dover 1998.

In particolare:
Chapter 2: Linear Programming and the Simplex Algorithm
Chapter 1, Appendix: Basics and notation of Graphs
Chapter 8: Computational Complexity
Chapter 18: the Branch-and-Bound algorithm for Integer Programming

Metodi didattici

Lezioni frontali ed esercitazioni in aula

Modalità di verifica e valutazione dell'apprendimento

L'esame è finalizzato alla valutazione della comprensione del contenuto del corso.

L'esame è composto da una parte scritta in cui agli studenti viene chiesto di rispondere a domande aperte sul contenuto del corso. Le domande possono includere la soluzione di semplici esercizi. Non è consentito utilizzare alcuna fonte scritta o dispositivo elettronico durante l'esame.

La parte scritta è integrata da una discussione orale sugli argomenti delle domande scritte e su altri argomenti del corso.

La valutazione finale è in una scala 0-30.

Strumenti a supporto della didattica

dispense, diapositive ed esercizi disponibili online

Orario di ricevimento

Consulta il sito web di Daniele Vigo