- Docente: Aristide Mingozzi
- Crediti formativi: 6
- SSD: MAT/09
- Lingua di insegnamento: Italiano
- Moduli: Aristide Mingozzi (Modulo 1) Enrico Bartolini (Modulo 2)
- Modalità didattica: Convenzionale - Lezioni in presenza (Modulo 1) Convenzionale - Lezioni in presenza (Modulo 2)
- Campus: Cesena
- Corso: Laurea Magistrale in Scienze e tecnologie informatiche (cod. 8030)
Conoscenze e abilità da conseguire
Al termine del corso, lo studente conosce i modelli e metodi di programmazione lineare a numeri interi per la risoluzione di problemi reali di tipo combinatorico.
Contenuti
Introduzione alla Programmazione a Numeri
Interi:
Formulazioni intere
Formulazioni intere miste
Formulazioni alternative
Esempi
Problemi ben risolti:
Proprietà dei problemi facili
Matrici totalmente unimodulari
Esempi di problemi facili
Rilassamenti e Lower Bounds:
Rilassamento lineare
Rilassamento combinatorio
Rilassamento surrogato
Rilassamento lagrangiano
Ottimalità
Esempi
Programmazione Dinamica:
Motivazioni
Cammini minimi
Knapsack problem
Traveling salesman problem (TSP)
Metodi implementativi
Tagli 2-D a ghigliottina
Rilassamento dello spazio degli stati
Uso di lower bounds
Esempi
Metodi Branch and Bound (B&B):
Branch and Bound basati su LP
Regole di branching
Regole di Dominanza
Esempi di algoritmi B&B
TSP
Assegnamento generalizzato
Set covering/partitioning
Metodi cutting planes:
Disuguagliane valide
Tagli di Gomory
Metodi implementativi
Esempi
Disuguagliane forti
Introduzione ai metodi Branch and Cut
Esempi
Algoritmi Euristici:
Metodi Greedy a ricerca locale
Tabu search
Simulated annealing
Algoritmi genetici e bionomici
Esempi
Testi/Bibliografia
- M.S.Bazaraa, J.J.Jarvis, H.D.Sherali, "Linear programming and network flows", John Wiley & Sons.
- C.H. Papadimitriou, K. Steiglitz, "Combinatorial Optimization, Algorithms and Complexity", Prentice-Hall.
- L.A. Wolsey, "Integer Programming", John Wiley & Sons.
Metodi didattici
Durante le lezioni verranno presentati sia gli aspetti teorici che pratici relativi ai diversi argomenti trattati. Esempi, esercizi ed esercitazioni di laboratorio aiuteranno lo studente a comprendere l'uso degli strumenti matematici presentati.
Modalità di verifica e valutazione dell'apprendimento
Progetto e prova scritta e orale.
Strumenti a supporto della didattica
Dispense, videoproiettore, PC, lavagna luminosa e laboratori.
Orario di ricevimento
Consulta il sito web di Aristide Mingozzi
Consulta il sito web di Enrico Bartolini