# MA252 - Combinatorial Optimisation

**Module code:**MA252**Module name:**Combinatorial Optimisation**Department:**Mathematics Institute**Credit:**12

Content and teaching | Assessment | Availability

## Module content and teaching

###### Principal aims

This module provides an introduction to combinatorial optimisation. In particular, we discuss linear programming techniques and various fundamental graph-theoretic algorithms. Among others we aim to cover, shortest path algorithms, minimum spanning trees, matchings and coverings in bipartite and non-bipartite graphs, network flows, cliques and colorings. In addition, we discuss complexity classes of problems and NP-completeness.

###### Principal learning outcomes

At the end of the course you are expected to have good understanding of the theoretical aspects of linear programming.and various fundamental graph theoretic notions and algorithms. You should also have a good grasp of the role of various complexity classes of combinatorial optimisation problems and appreciate constructive proofs in finite mathematics.

###### Departmental link

http://go.warwick.ac.uk/MA252/

###### Other essential notes

Prerequisites: MA106 Linear Algebra. Basic knowledge of discrete mathematics could be helpful.

## Module assessment

Assessment group | Assessment name | Percentage |
---|---|---|

12 CATS (Module code: MA252-12) | ||

B (Examination only) | 2 hour examination (Summer) | 100% |

## Module availability

This module is available on the following courses:

###### Core

N/A

###### Optional Core

- Undergraduate Mathematics and Philosophy (GV17) - Year 3
- Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations (GV19) - Year 4

###### Optional

- Undergraduate Mathematics and Physics (BSc MMathPhys) (FG33) - Year 3
- Undergraduate Mathematics (BSc) (G100) - Year 2
- Undergraduate Mathematics (BSc) (G100) - Year 3
- Undergraduate Mathematics with Intercalated Year (G101) - Year 2
- Undergraduate Mathematics with Intercalated Year (G101) - Year 4
- Undergraduate Mathematics (MMath) (G103) - Year 2
- Undergraduate Mathematics (MMath) (G103) - Year 3
- Undergraduate Master of Mathematics (with Intercalated Year) (G105) - Year 2
- Undergraduate Master of Mathematics (with Intercalated Year) (G105) - Year 3
- Undergraduate Master of Mathematics (with Intercalated Year) (G105) - Year 4
- Undergraduate Mathematics (MMath) with Study in Europe (G106) - Year 2
- Undergraduate Mathematics (MMath) with Study in Europe (G106) - Year 3
- Undergraduate Mathematics and Statistics (BSc MMathStat) (G1G3) - Year 2
- Undergraduate Mathematics and Statistics (BSc MMathStat) (G1G3) - Year 3
- Undergraduate Mathematics and Statistics (BSc MMathStat) (G1G3) - Year 4
- Undergraduate Mathematics and Business Studies (with Intercalated Year) (G1N2) - Year 2
- Undergraduate Mathematics and Business Studies (G1NC) - Year 2
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G300) - Year 2
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G300) - Year 3
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G300) - Year 4
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30A) - Year 3
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30A) - Year 4
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30A) - Year 5
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30B) - Year 3
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30B) - Year 4
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30B) - Year 5
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30C) - Year 3
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30C) - Year 4
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30C) - Year 5
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30D) - Year 3
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30D) - Year 4
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (G30D) - Year 5
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30E) - Year 3
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30E) - Year 4
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30E) - Year 5
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30F) - Year 3
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30F) - Year 4
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30F) - Year 5
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30G) - Year 3
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30G) - Year 4
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30G) - Year 5
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30H) - Year 3
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30H) - Year 4
- Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated (G30H) - Year 5
- Undergraduate Discrete Mathematics (G4G1) - Year 2
- Undergraduate Discrete Mathematics (G4G3) - Year 2
- Undergraduate Mathematics and Physics (BSc) (GF13) - Year 3
- Undergraduate Mathematics and Physics (with Intercalated Year) (GF14) - Year 4
- Undergraduate Mathematics and Statistics (BSc) (GG14) - Year 2
- Undergraduate Mathematics and Statistics (BSc) (GG14) - Year 3
- Undergraduate Mathematics and Statistics (with Intercalated Year) (GG17) - Year 4
- Undergraduate Mathematics and Economics (GL11) - Year 2
- Undergraduate Mathematics and Economics (GL11) - Year 3
- Undergraduate Mathematics and Economics (with Intercalated Year) (GL12) - Year 2
- Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations (GV19) - Year 3
- Undergraduate Mathematics,Operational Research,Statistics and Economics (Y602) - Year 2
- Undergraduate Mathematics,Operational Research,Statistics and Economics (Y602) - Year 3
- Undergraduate Mathematics,Operational Research,Statistics,Economics (with Intercalated Year) (Y603) - Year 4