Combinatorial Optimization
A.Y. 2021/2022
Learning objectives
The objective of this course is to teach the main algorithms and techniques to compute optimal solutions to combinatorial optimization problems with special emphasis on graph optimization.
Expected learning outcomes
Ability to design and implement efficient algorithms to solve polynomial complexity optimization problems on graphs.
Lesson period: First semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
Lesson period
First semester
More specific information on the delivery mode of training activities for the academic year 2021/22 will be provided in the forthcoming months, depending on the evolution of the public health situation.
Course syllabus
· Graphs, definitions and properties.
· Problems of minimum cost connectivity. Minimum cost spanning tree: Kruskal, Prim, Boruvka algorithms. Minimum cost spanning arborescence: Edmonds algorithm.
· Shortest path problems. Unweighted graphs: BFS algorithm. Weighted acyclic graphs: Critical Path Method. Graphs without negative cost cycles: Bellman-Ford algorithm. Graphs without negative cost arcs: Dijkstra algorithm. Floyd-Warshall algorithm for the computation of the all-pairs shortest paths matrix on a weighted digraph.
· Optimal flow problems. Ford-Fulkerson algorithm for the maximum flow problem and its implementations. Algorithms for the maximum flow minimum cost problem. Duality: max flow - min cut theorem. Gomory and Hu algorithm for finding a minimum cut in a weighted graph.
· Bipartite matching problems. The Hungarian algorithm.
· Minimum cost transportation problems. Dantzig algorithm.
· Problems of minimum cost connectivity. Minimum cost spanning tree: Kruskal, Prim, Boruvka algorithms. Minimum cost spanning arborescence: Edmonds algorithm.
· Shortest path problems. Unweighted graphs: BFS algorithm. Weighted acyclic graphs: Critical Path Method. Graphs without negative cost cycles: Bellman-Ford algorithm. Graphs without negative cost arcs: Dijkstra algorithm. Floyd-Warshall algorithm for the computation of the all-pairs shortest paths matrix on a weighted digraph.
· Optimal flow problems. Ford-Fulkerson algorithm for the maximum flow problem and its implementations. Algorithms for the maximum flow minimum cost problem. Duality: max flow - min cut theorem. Gomory and Hu algorithm for finding a minimum cut in a weighted graph.
· Bipartite matching problems. The Hungarian algorithm.
· Minimum cost transportation problems. Dantzig algorithm.
Prerequisites for admission
Operations research
Teaching methods
Lectures.
Teaching Resources
R.K. Ahuja, T.L. Magnanti, J.B. Orlin "Network flows", Prentice Hall, 1993
Assessment methods and Criteria
Preliminary written exam, about half-an-hour long, with no books. Then (a) project work and oral exam or (b) presentation of a scientific paper and oral exam.
Educational website(s)
Professor(s)