- Docente: Daniele Vigo
- Crediti formativi: 6
- SSD: MAT/09
- Lingua di insegnamento: Italiano
- Modalità didattica: Convenzionale - Lezioni in presenza
- Campus: Bologna
- Corso: Laurea Magistrale in Matematica (cod. 8208)
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
SDGs
L'insegnamento contribuisce al perseguimento degli Obiettivi di Sviluppo Sostenibile dell'Agenda 2030 dell'ONU.