MA25210 Combinatorial Optimisation
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. algorithms) for exploring the solution space.
Module aims
To introduce students to basic concepts and techniques of combinatorial optimisation.
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, cliques, colourings and matroids. We will also discuss "intractable" (e.g. NPhard) problems.
Learning outcomes
By the end of the module, students should be able to:
 Upon completion of the module the students should be able to apply various combinatorial structures (graphs, matroids, etc.) and basic algorithmic techniques (breadthfirst search, depthfirst search, etc.) to describe and solve fundamental problems of combinatorial optimization (shortest path, travelling salesman, etc.).
Indicative reading list
Main Reference:
B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 6th Edition, 2018. Ebook available through the Warwick Library; click the link.
Other Resources:
A. Bondy and U. S. R. Murty, Graph Theory with Applications, Elsevier, 1976. Available through the link.
W.J. Cook, William H. Cunningham, W. R. Pulleybank, and A. Schrijver, Combinatorial Optimization, WileyInterscience Series in Discrete Mathematics, 1998.
C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.
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 reallife optimisation problems and apply formal methods to solve them.
Study time
Type  Required 

Lectures  30 sessions of 1 hour (30%) 
Tutorials  9 sessions of 1 hour (9%) 
Private study  31 hours (31%) 
Assessment  30 hours (30%) 
Total  100 hours 
Private study description
Review lectured material and work on set exercises.
Costs
No further costs have been identified for this module.
You do not need to pass all assessment components to pass the module.
Assessment group B
Weighting  Study time  

2 hour examination (Summer)  100%  30 hours 

Assessment group R
Weighting  Study time  

Inperson Examination  Resit  100%  

Feedback on assessment
Exam feedback.
Courses
This module is Core option list A for:

UMAAGV17 Undergraduate Mathematics and Philosophy
 Year 2 of GV17 Mathematics and Philosophy
 Year 2 of GV17 Mathematics and Philosophy
 Year 2 of GV17 Mathematics and Philosophy
 Year 2 of UMAAGV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
This module is Core option list B for:
 Year 3 of UMAAGV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
This module is Core option list D for:
 Year 4 of UMAAGV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
This module is Option list A for:

UCSAG4G1 Undergraduate Discrete Mathematics
 Year 2 of G4G1 Discrete Mathematics
 Year 2 of G4G1 Discrete Mathematics
 Year 2 of UCSAG4G3 Undergraduate Discrete Mathematics

UMAAG105 Undergraduate Master of Mathematics (with Intercalated Year)
 Year 2 of G105 Mathematics (MMath) with Intercalated Year
 Year 4 of G105 Mathematics (MMath) with Intercalated Year

UMAAG100 Undergraduate Mathematics (BSc)
 Year 2 of G100 Mathematics
 Year 2 of G100 Mathematics
 Year 2 of G100 Mathematics
 Year 3 of G100 Mathematics
 Year 3 of G100 Mathematics
 Year 3 of G100 Mathematics

UMAAG103 Undergraduate Mathematics (MMath)
 Year 2 of G100 Mathematics
 Year 2 of G103 Mathematics (MMath)
 Year 2 of G103 Mathematics (MMath)
 Year 3 of G100 Mathematics
 Year 3 of G103 Mathematics (MMath)
 Year 3 of G103 Mathematics (MMath)
 Year 2 of UMAAG1NC Undergraduate Mathematics and Business Studies
 Year 2 of UMAAG1N2 Undergraduate Mathematics and Business Studies (with Intercalated Year)
 Year 2 of UMAAGL11 Undergraduate Mathematics and Economics
 Year 2 of UECAGL12 Undergraduate Mathematics and Economics (with Intercalated Year)

USTAGG14 Undergraduate Mathematics and Statistics (BSc)
 Year 2 of GG14 Mathematics and Statistics
 Year 2 of GG14 Mathematics and Statistics

UMAAG101 Undergraduate Mathematics with Intercalated Year
 Year 2 of G101 Mathematics with Intercalated Year
 Year 4 of G101 Mathematics with Intercalated Year
This module is Option list B for:

UPXAGF13 Undergraduate Mathematics and Physics (BSc)
 Year 2 of GF13 Mathematics and Physics
 Year 2 of GF13 Mathematics and Physics

UPXAFG31 Undergraduate Mathematics and Physics (MMathPhys)
 Year 2 of FG31 Mathematics and Physics (MMathPhys)
 Year 2 of FG31 Mathematics and Physics (MMathPhys)

USTAY602 Undergraduate Mathematics,Operational Research,Statistics and Economics
 Year 2 of Y602 Mathematics,Operational Research,Stats,Economics
 Year 2 of Y602 Mathematics,Operational Research,Stats,Economics