Combinatorial Optimization

Course Description

The course deals with the theory, algorithms and applications of discrete (also known as combinatorial) optimization with an emphasis on problems regarding flows, paths and matchings on graphs. More specifically, the course presents algorithms for the problems of shortest path, maximum flow, minimum-cost flow, maximum-cardinality and maximum-weight matchings (mostly regarding bipartite graphs) and, last, stable matchings and b-matchings on bipartite graphs.

Apart from solving such problems using specialized combinatorial algorithms, the students are also expected to formulate applications and real-life problems as flow, path or matching problems on graphs. In addition, this course introduces general methods for discrete optimization problems that can be modeled as Linear Integer Programs, i.e., Branch-and-Bound and Branch-and-Cut. 

The purpose of this course is the understanding of algorithmic design specifically for discrete optimization algorithms defined on graphs and integer programming methods. Apart from understanding all related notions, the purpose is to investigate the application of such algorithms (i.e., algorithms for paths, flows and matchings) on real-life problems.

The course material includes the following topics:

• Network Flows and Integer Programming
• Shortest-path algorithms: Dijkstra, Bellman-Ford, Floyd-Warshall
• Maximum-flow and minimum-cost flow algorithms
• Matching algorithms in bipartite graphs: maximum-cardinality matching, maximum-weight matching, stable matching and stable b-matching
• Applications modeled as flow problems: project management, job assignment to machines, distinct and restricted representatives, capital allocation, etc.
• Integer Programming: Branch-and-bound methods, Balas' additive algorithm, Branch-and-Cut methods
• Applications of Integer Programming
• Trees: properties, transversal algorithms, minimum-spanning tree algorithms, Steiner trees.