
Course unit
OPTIMIZATION ALGORITHMS
SSM0014104, A.A. 2015/16
Information concerning the students who enrolled in A.Y. 2013/14
ECTS: details
Type 
ScientificDisciplinary Sector 
Credits allocated 
Educational activities in elective or integrative disciplines 
MAT/09 
Operational Research 
8.0 
Course unit organization
Period 
Second semester 
Year 
3rd Year 
Teaching method 
frontal 
Type of hours 
Credits 
Teaching hours 
Hours of Individual study 
Shifts 
Lecture 
8.0 
56 
144.0 
No turn 
Examination board
Board 
From 
To 
Members of the board 
6 a.a. 2015/2016 
01/10/2015 
30/09/2018 
ANDREATTA
GIOVANNI
(Presidente)
DE GIOVANNI
LUIGI
(Membro Effettivo)
FERRANTE
MARCO
(Membro Effettivo)

5 a.a. 2014/2015 
01/10/2014 
30/09/2020 
DE FRANCESCO
CARLA
(Presidente)
ANDREATTA
GIOVANNI
(Membro Effettivo)
DE GIOVANNI
LUIGI
(Membro Effettivo)
FERRANTE
MARCO
(Membro Effettivo)

Prerequisites:

Basic knowledge of linear algebra: vector spaces (basis, linear independent vectors), matrices (determinant of a matrix, nonsingular matrices, inverse matrix, rank of a matrix). 
Target skills and knowledge:

At the end of the course the student is supposed to know main optimization problems and to be aware of the difficulty of their resolution. He should know that there are "easy" and "difficult" problems, and that this difference depends not only on the problem itself, but also on its formulation.
Focus on main algorithms for linear, integer and network optimization problems. 
Examination methods:

Written test (mandatory), based on exercises plus some theoretical questions; an optional oral test may be required.
Foreign students may take the final test in English. 
Assessment criteria:

Evaluate the level of knowledge and comprehension of the solution methods presented during the course. 
Course unit contents:

 Introduction to operations research, some examples of decision problems formulated as Optimization problems.
 Linear Optimization: simplex algorithm and duality theory.
 Linear Integer Optimization: equivalent formulations, Total Unimodularity, Cutting Plane method, Branch and Bound method.
 Network Optimization: Graph Theory, computational complexity, some problems choosen among minimum spanning trees, shortest paths, maximum flow, assignment problem. Knapsack problem and Traveling Salesman Problem solved using Branch and Bound techniques. 
Planned learning activities and teaching methods:

The course is taught in Italian.
Its web site contains a lot of material for the students, in particular exercises.
Students will be required to work out some exercises, that will then be solved by the teacher in class. 
Additional notes about suggested reading:

Suggested references:
2)Fischetti M., Lezioni di Ricerca Operativa, Libreria Progetto, Padova, 1999
3) Luenberger D.G., Linear and Nonlinear Programming, Addison Wesley, Reading, 1984
4) Andreatta G., Mason F. e Romanin Jacur G., Appunti di ottimizzazione su reti, Libreria Progetto, Padova, seconda edizione, 1996.
A list of english references may be required. 
Textbooks (and optional supplementary readings) 

M. Bruglieri, A. Colorni, Ricerca Operativa. : Zanichelli, 2012.


