Combinatorial Optimization
A.Y. 2023/2024
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
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, Algorithms and data-structures.
Teaching methods
Lectures
Teaching Resources
Ahuja, Magnanti, Orlin, "Network Flows: Theory, Algorithms, and Applications", Pearson
Assessment methods and Criteria
Project or seminar.
Professor(s)