NETWORK OPTIMIZATION (updated
March 14)
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 14)
Lectures
take place in Classroom 20. Practical lectures (on optimization
software, indicated with *) take place in Classroom 146 (Computer
Science Lab).
 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 (*)
 Monday April 23, 913
 Wednesday May 2, 1113 (*)
 Monday May 7, 913
 Wednesday May 9, 1113 (*  practical test)
 Monday May 28, 913 (written test)
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)
