Ottimizzazione discreta
A.A. 2025/2026
Learning objectives
L'insegnamento si propone di ampliare i fondamenti della programmazione matematica. Si affronteranno i problemi di ottimizzazione non lineare e si approfondiranno le tecniche per affrontare i problemi di programmazione lineare e lineare intera.
Expected learning outcomes
Capacità di scegliere gli strumenti più adatti per risolvere problemi di ottimizzazione non lineare. Capacità di applicare tecniche di decomposizione per affrontare problemi di programmazione lineare intera, competenze relative alle tecniche utilizzate dai solutori commerciali.
Periodo: Secondo quadrimestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Course syllabus and organization
Edizione unica
Responsabile
Periodo
Secondo quadrimestre
Programma
1. Programmazione lineare intera e misto-intera. Richiami di programmazione lineare. Interpretazione geometrica della PLI, teoria poliedrale. Metodo dei piani di taglio
2. Algoritmi di enumerazione implicita. Branch-and-bound e branch-and-cut. Algoritmo di Balas per PLI 0-1. Programmazione dinamica.
3. Rilassamento Lagrangeano
4. Column generation e branch-and-price
2. Algoritmi di enumerazione implicita. Branch-and-bound e branch-and-cut. Algoritmo di Balas per PLI 0-1. Programmazione dinamica.
3. Rilassamento Lagrangeano
4. Column generation e branch-and-price
Prerequisiti
Sono prerequisiti i concetti fondamentali di Algoritmi e strutture-dati, Programmazione dei calcolatori e Ricerca operativa.
E' utile avere un buona conoscenza dell'inglese tecnico-scientifico.
E' utile avere un buona conoscenza dell'inglese tecnico-scientifico.
Metodi didattici
Lezioni frontali.
Materiale di riferimento
F. Maffioli: "Elementi di programmazione matematica", Casa Editrice Ambrosiana, 2000.
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste in tre prove.
1. Una breve prova scritta per accertare che lo studente abbia maturato le conoscenze necessarie per affrontare le prove successive.
2a. La realizzazione di un progetto nel quale è richiesto allo studente di progettare un algoritmo di ottimizzazione per un problema di ottimizzazione combinatoria concordato col docente, scrivere il codice in un linguaggio di programmazione a scelta dello studente e valutare sperimentalmente le prestazioni del programma.
2b. In alternativa al progetto, la seconda prova può consistere nella preparazione di un seminario di circa 20-30 minuti su un articolo concordato col docente.
3. In ogni caso, l'esame è concluso da una prova orale riguardante gli argomenti del corso che non sono stati oggetto del progetto o del seminario.
1. Una breve prova scritta per accertare che lo studente abbia maturato le conoscenze necessarie per affrontare le prove successive.
2a. La realizzazione di un progetto nel quale è richiesto allo studente di progettare un algoritmo di ottimizzazione per un problema di ottimizzazione combinatoria concordato col docente, scrivere il codice in un linguaggio di programmazione a scelta dello studente e valutare sperimentalmente le prestazioni del programma.
2b. In alternativa al progetto, la seconda prova può consistere nella preparazione di un seminario di circa 20-30 minuti su un articolo concordato col docente.
3. In ogni caso, l'esame è concluso da una prova orale riguardante gli argomenti del corso che non sono stati oggetto del progetto o del seminario.
Professor(s)