Combinatorial Optimization
A.Y. 2024/2025
Learning objectives
The objectives of the course are: 1) to learn some polynomial time algorithms for graph optimization problems and the theoretical foundations on which these algorithms are based; 2) to implement some of the algorithms presented (a part of the course takes place in a computer lab); 3) to understand when the search for polynomial algorithms, for a new combinatorial optimization problem, is probably destined to fail (by means of the computational complexity theory).
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 can be attended as a single course.
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
Algorithms and data-structures. Computer programming. Operations research. English.
Teaching methods
Lectures.
Teaching Resources
R.K. Ahuja, T.L. Magnanti, J.B. Orlin "Network flows", Prentice Hall, 1993
Assessment methods and Criteria
The exam consists of three steps.
1. A short written exam to verify that the student has got the necessary knowledge
to enter the next steps.
2a. A project in which the student is required to design an optimization algorithm for a combinatorial optimization problem agreed with the teacher,
to code it in a programmming language selected by the student and to evaluate it experimentally.
2b. As an alternative to the project, the second step can consist of a seminar of 20-30 minutes on a paper agreed with the teacher.
3. In all cases, the exam is concluded by an oral exam on the topics not covered by the project or seminar.
1. A short written exam to verify that the student has got the necessary knowledge
to enter the next steps.
2a. A project in which the student is required to design an optimization algorithm for a combinatorial optimization problem agreed with the teacher,
to code it in a programmming language selected by the student and to evaluate it experimentally.
2b. As an alternative to the project, the second step can consist of a seminar of 20-30 minutes on a paper agreed with the teacher.
3. In all cases, the exam is concluded by an oral exam on the topics not covered by the project or seminar.
MAT/09 - OPERATIONS RESEARCH - University credits: 6
Lessons: 48 hours
Professor:
Righini Giovanni
Shifts:
Turno
Professor:
Righini GiovanniProfessor(s)