The course is taught in English.
insegnamento obbligatorio per la Laurea Magistrale in Informatica, collocato al I semestre del I anno, questo corso presenta contenuti sia metodologici sia applicativi. In particolare, scopo del corso è fornire agli studenti strumenti teorici ed operativi per la modellazione e la risoluzione di problemi di ottimizzazione propri dell'ingegneria dell'informazione.
L'ottimizzazione mette a disposizione potenti metodologie matematiche (modelli matematici, algoritmi e software) per la soluzione di problemi complessi consistenti nella minimizzazione (o massimizzazione) di funzioni obiettivo, nel rispetto di opportuni vincoli.
Partendo da problemi reali quali la progettazione di reti di calcolatori, le gestione di data base, la diagnostica degli errori, verranno studiati la teoria e gli algoritmi risolutivi dei problemi di ottimizzazione che ne stanno alla base, prestando particolare attenzione alla loro complessità computazionale ed ai metodi di soluzione.

Gli studenti approfondiranno gli strumenti e le metodologie per la soluzione di problemi di ottimizzazione vincolati. Gli studenti impareranno ad usare la programmazione lineare continua ed intera e a scegliere il metodo di soluzione più adatto al tipo di problema. Particolare attenzione sarà data a problemi su grafi, quali il min cost flow ed il multicommodity network design. Verrà studiata la complessità computazionale dei problemi di ottimizzazione, che condiziona la scelta dei metodi più opportuni per la risoluzione di tali problemi. I metodi che si studieranno sono di tipo esatto (Branch and Bound, Dynamic Programming, Branch and Cut) e approssimato (euristiche e metaeuristiche).
Le capacità sviluppate dagli studenti consisteranno nella costruzione di modelli matematici e dei relativi algoritmi per la risoluzione di problemi di ottimizzazione dell'ingegneria dell'informazione, quali flussi su reti, network design, localizzazione, scheduling e routing.

È richiesto di aver correttamente appreso le basi matematiche proprie dei corsi delle lauree di primo livello.
È richiesta anche una buona conoscenza del linguaggio C.

Argomenti trattati nel corso:
- Introduzione alla Programmazione Lineare.
- Complessità computazionale.
- Metodi esatti di ottimizzazione: Branch and Bound, Dynamic Programming, Branch and Cut.
- Metodi euristici di ottimizzazione: algoritmi greedy, GRASP, Beam Search, metaeuristiche (Tabu Search, Simulated Annealing, Genetic Algorithms, ACO, VNS, RBS).
- Problemi su grafi.

Presentation
Compulsory course for the Master of Science in Computer Science, located in the first half of the first year, this course presents both methodological and practical contents. In particular, the aim of the course is to provide students with theoretical and operational tools for modeling and solving optimization problems in information engineering.
The optimization provides powerful mathematical methods (mathematical models, algorithms, and software) for solving complex problems involving the minimization (or maximization) of objective functions, subject to appropriate constraints.
Starting from real problems such as the design of networks of computers, data base management, network flows, we will study the theory and algorithms for solving optimization problems that underlie those problems, paying particular attention to their computational complexity and the required solution methods.

Knowledge and skills to acquire
Students will study the methods and tools for solving constrained optimization problems. They will learn how to use linear continuous and integer programming and choose the most suitable solution method to the problem. Particular attention will be given to graph problems such as the min cost flow problem and multicommodity network design problem. We will study the computational complexity of optimization problems, which influences the choice of the most suitable methods for solving such problems. The methods that will be studied are both exact methods (Branch and Bound, Dynamic Programming, Branch and Cut) and approximate methods (heuristic and metaheuristics).
The skills developed by students will consist of the construction of mathematical models and related algorithms for solving optimization problems of information engineering, such as flows across networks, network design, location, scheduling, and routing.

La maggioranza delle lezioni/esercitazioni si svolgerà in aula. Sono previste esercitazioni in laboratorio in cui gli studenti dovranno implementare alcuni degli algoritmi proposti.
Gli studenti avranno a disposizione delle librerie che saranno utili per l'implementazione degli algoritmi.

Sono disponibili dispense delle lezioni e delle esercitazioni, esempi di scritti di esame ed esercizi, e i manuali per le esercitazioni di laboratorio. Tutto il materiale didattico è scaricabile da un sito web o attraverso il portale.
Sono consigliati i seguenti libri di testo:
R. Tadei, F. Della Croce, 'Elementi di Ricerca Operativa', Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
R. Tadei, F. Della Croce, A. Grosso, 'Fondamenti di Ottimizzazione', Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
M. Ghirardi, A. Grosso, G. Perboli, 'Esercizi di Ricerca Operativa', Progetto Leonardo, Editrice Esculapio, Bologna, 2009.
D. J. Luenberger, "Linear and Nonlinear Programming", Springer, 3rd ed., 2008.
G.L. Nemhauser, L.A. Wolsey, "Integer Programming", Wiley, 1998.

R. Tadei, F. Della Croce, 'Elementi di Ricerca Operativa', Progetto Leonardo, Editrice Esculapio, Bologna, 2010.
R. Tadei, F. Della Croce, A. Grosso, 'Fondamenti di Ottimizzazione', Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
M. Ghirardi, A. Grosso, G. Perboli, 'Esercizi di Ricerca Operativa', Progetto Leonardo, Editrice Esculapio, Bologna, 2009.
R.K. Ahuja et al., "Network Flows", Prentice Hall, New Jersey, 1993.
D. J. Luenberger, "Linear and Nonlinear Programming", Springer, 3rd ed., 2008.
G.L. Nemhauser, L.A. Wolsey, "Integer Programming", Wiley, 1998.

L'esame prevede una prova scritta (in casi particolari, può essetre previsto un esame orale). Gli studenti saranno invitati a svolgere delle tesine di approfondimento sugli argomenti del corso.

The final examination consists of a written test (in special cases, an oral examination could be expected).