Objectives and outcomes
The aim of the course is to familiarise students with the most important combinatorial optimisation problems and methods for solving them. Ability to characterise optimal solutions and find efficient algorithms for optimisation problems over discrete structures, such as e.g. network flow problems, optimal matching, matroid optimisation, etc.
Lectures
Integer polyhedra. Pruning methods. Methods of branching and bounding. Methods of implicit enumeration. Optimal trees and paths. Minimum spanning tree and greedy algorithms. Determining the shortest path. Flows in networks. Determining the maximum flow. Determining the flow with the minimal cost. The network simplex method. Optimal matching. Matching in bipartite graphs. Matching in arbitrary graphs. Matching in weighted graphs. The problem of maximum matching. Hamiltonian paths and the travelling salesman problem. Various relaxations of the travelling salesman problem: Lin-Kernighan heuristic. The multiple travelling salesmen problem.
Research work
A part of the course is dedicated to independent research work that includes the application of combinatorial optimisation to computer science and computer engineering.