NETWORK OPTIMIZATION
The aim
of the course is to present basic concepts on network optimization
problems, from modeling, algorithmic and implementation viewpoints.
Instructor Alessandro
Agnetis
Syllabus 2017/18
Review of graphs and linear programming. Shortest path problems.
Algorithms for acyclic graphs. Dijkstra’s
and FloydWarshall’s algorithms. Flow
problems. Max flow, FordFulkerson algorithm. Matching problems.
Maximum matching and node cover. Assignment problem. Hungarian
algorithm. Formulation of decision problems as network optimization.
Use of optimization software to solve network optimization problems.
Exam
For students who attend the course, the exam can be taken by
means of a practical (software) test and a written test (both
scheduled in May, see below).
A student who succeeds in both the above tests will receive a
final grade.
If a student succeeds in one test but not both, the work done
may be taken into account, but the student will still have to
undertake a written test and the oral test.
Regular exams consist of a written test and an oral test.
Course calendar (updated March 15)
Lectures
take place in Classroom 20. Practical lectures take place in the
Computer Science Lab (room 146).
 Wednesday March 7, 1113
 Monday March 12, 913
 Wednesday March 14, 1113
 Monday March 19, 913
 Wednesday March 21, 1113
 Monday March 26, 913
 Wednesday March 28, 1113
 Monday April 9, 913
 Wednesday April 11, 1113
 Monday April 16, 913
 Wednesday April 18, 1113 (optimization software, lab 143)
 Monday April 23, 913
 Wednesday May 2, 1113 (optimization software, lab 143)
 Monday May 7, 913
 Wednesday May 9, 1113 (practical test, lab 143)
 Monday May 28, 913 (written test, room to be defined)
Office hours (students): Tuesday, 14.30  16, Torre Rossa, room R101
Course material
Classnotes prepared by the teacher:
Shortest path problems
(download)
The maximum
flow problem (download)
Matching
problems (download)
Formulation
exercises (download) (Exercises 1115182434 can be skipped)
