MA3602: Algorithms and Heuristics

School Cardiff School of Mathematics
Department Code MATHS
Module Code MA3602
External Subject Code 100404
Number of Credits 10
Level L6
Language of Delivery English
Module Leader Professor Rhydian Lewis
Semester Spring Semester
Academic Year 2015/6

Outline Description of Module

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. 

Prerequisite Modules: MA0261 Operational Research

On completion of the module a student should be able to

  • 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.

How the module will be delivered

22 - 50 minute lectures.

5 - 50 minute exercise classes.

Some handouts will be provided in hard copy or via Learning Central, but students will also be expected to take notes during lectures.

Students are also expected to undertake at least 50 hours of private study.

Skills that will be practised and developed

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. 

How the module will be assessed

Formative assessment is carried out by means of regular exercises.  Feedback to students on their solutions and their progress towards learning outcomes is provided during classes. 

There is no summative assessment for this module.

Summative assessment is by means of the written examination at the end of the module.  This gives students the opportunity to demonstrate their overall achievement of learning outcomes.  It also allows them to give evidence of the higher levels of knowledge and understanding required for above average marks.

The examination paper has a choice of four from six equally weighted questions.

Assessment Breakdown

Type % Title Duration(hrs)
Exam - Spring Semester 100 Algorithms And Heuristics 2

Syllabus content

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.

Background Reading and Resource List

Cormen, T. H. et al. Introduction to algorithms, MIT Press

Garey, M. and Johnson, D., Computers and intractability: a guide to the theory of NP-completeness, W.H. Freeman

Gibbon, A., Algorithmic graph theory, Cambridge University Press

Osman, I. and Kelly, J., Meta-heuristics: Theory and Applications, Kluwer

Rosen, K. H., Discrete mathematics and its applications, McGraw Hill 


Copyright Cardiff University. Registered charity no. 1136855