Introductory description

The focus of combinatorial optimisation is on finding the "optimal" object (i.e. an object that maximises or minimises a particular function) from a finite set of mathematical objects. Problems of this type arise frequently in real world settings and throughout pure and applied mathematics, operations research and theoretical computer science. Typically, it is impractical to apply an exhaustive search as the number of possible solutions grows rapidly with the "size" of the input to the problem. The aim of combinatorial optimisation is to find more clever methods (i.e. efficient algorithms) for exploring the solution space.

Module web page

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

This module provides an introduction to combinatorial optimisation. Our main focus is on several fundamental problems arising in graph theory and algorithms developed to solve them. These include problems related to shortest paths, minimum weight spanning trees, matchings, network flows, etc. We will also discuss "intractable" (e.g. NP-hard) problems.

Learning outcomes

By the end of the module, students should be able to:

• Upon completion of the module the students will be able to apply various combinatorial structures and algorithmic techniques to describe and solve fundamental problems of combinatorial optimization,
• apply covered techniques to concrete combinatorial problems,
• state and prove key results presented in the module,
• creatively adapt the presented methods to other combinatorial settings.

Indicative reading list

Main Reference:

D. Du, P. Pardalos, X. Hu, & W. Wu, Introduction to Combinatorial Optimization, Springer 2022.

Other Resources:

• W.J. Cook, William H. Cunningham, W. Pulleybank, & A. Schrijver, Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics, 1998.
• B. Korte & J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 6th Edition, 2018.
• J Lee, A First Course in Combinatorial Optimization, Cambridge University Press, 2010.
• C.H. Papadimitriou & K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.
• L.A. Wolsey & G.L Nemhauser, Integer and Combinatorial Optimization, Wiley 1999.

Subject specific skills

The module will help the students to develop an algorithmic style of thinking.

Transferable skills

Upon completion of the module the students should be able to formalise real-life optimisation problems and apply formal methods to solve them.