This module examines the behaviours and properties of various algorithms that can be used for solving combinatorial operational research problems. Primarily the focus is on problems involving networks and graphs, though other sorts of problems such as packing and partitioning are also considered.

A number of problems are looked at, including graph connectivity, shortest path problems, spanning trees, maximum flow problems, matchings, routing problems, bin packing problems, and graph colouring problems. It is shown that some of these problems can be solved using efficient exact algorithms, while others require heuristic techniques and/or approximation algorithms. Hence key concepts surrounding intractability (NP-completeness) are also considered.

The module also considers a number of general purpose heuristic algorithms for intractable problems including metaheuristics. In particular, methods such as neighbourhood search, backtracking, simulated annealing, and evolutionary algorithms are considered. 

MAT062 will only be available to students who can demonstrate suitable prior knowledge from previous studies.

• Apply and prove the behaviour of a number of famous combinatorial optimisation algorithms including Fleury’s and Hierholzer’s algorithms, Depth/Breadth first search; Prim’s and Kruskal’s algorithms, Dijkstra’s algorithm, the Ford-Fulkerson algorithm, the augmenting-path algorithm and the Blossom algorithm.
• Demonstrate the behaviour and properties of a number of heuristics and approximation algorithms for intractable problems including the traveling salesman problem, the vehicle routing problem and variants, the bin packing problem, the trapezoid packing problem, and the graph colouring problem.
• Identify the steps needed to prove when an OR problem is intractable.
• Design suitable heuristics or metaheuristic-based algorithms for a variety of intractable OR problems.

Modules will be delivered through blended learning. You will be guided through learning activities appropriate to your module, which may include:

• Weekly face to face classes (e.g. labs, lectures, exercise classes)
• Electronic resources that you work through at your own pace (e.g. videos, exercise sheets, lecture notes, e-books, quizzes)

Students are also expected to undertake self-guided study throughout the duration of the module.

An ability to formulate and solve a variety of combinatorial optimisation problems;

An appreciation of how real world operational research problems may be expressed and solved;

Transferable Skills:
Clear logical thinking;

Problem solving;

Time management;

Using mathematical and algorithmic principles to solve real-world problems. 

Graph Fundamentals:

• Paths, cycles, and trees;
• Bipartite graphs;
• Graph isomorphism;
• Euler circuits and Hamiltonian circuits;
• Planar Graphs, Euler’s formula and Kuratowski’s theorem.

Exact algorithms for Graphs and Networks:

• Depth/Breadth first search;
• Minimum Spanning Trees (Prim’s and Kruskal’s algorithms);
• Shortest Path Problems (Dijkstras algorithm);
• Maximum flow algorithms (Ford-Fulkerson algorithm);
• Matchings in bipartite and general graphs (Augmenting-Path and Blossom algorithms).

Heuristics for Graphs and Networks:

• Introduction to NP completeness, Cook’s theorem and polynomial reductions;
• Bounded approximation algorithms for the TSP;
• The Vehicle Routing problem and variants;
• Bin packing and trapezoid packing problems.

Graph colouring

• The greedy and iterated greedy algorithms;
• Brooke’s theorem;
• the 5 & 4 colour theorem;
• the DSatur and RLF heuristics;
• the PartialCol algorithm, and practical applications.

General Heuristics and Meta-heuristics:

• An examination of heuristics and metaheuristics (including simulated annealing, tabu search and evolutionary algorithms), applied to graph colouring problems, packing problems and routing problems.