This module examines the behaviours and properties of various algorithms that are 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. Several topics are covered, including graph connectivity, shortest path problems, spanning trees, maximum flow problems, matchings, routing problems, bin packing, and graph colouring. 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 neighbourhood search, simulated annealing, and evolutionary algorithms. 

Recommended modules: MA1500 (R), MA2601 (R)

• Apply and prove the behaviour of several famous combinatorial optimisation algorithms including Hierholzer algorithm, Depth and 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 various heuristics and approximation algorithms for intractable problems, including the traveling salesman problem, the vehicle routing problem, 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.

You will be guided through learning activities appropriate to this module. This includes:

• Weekly face to face classes (e.g. labs, lectures, exercise classes)
• Electronic resources to support the learning. Students are also expected to undertake at least 50 hours of self-guided study throughout the duration of the module, including completion of formative assessments

• 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 include clear logical thinking, problem solving, time management, and using mathematical and algorithmic principles to solve real-world problems. Formative assignments may contain a small amount of Python programming, though previous exposure to the language is not assumed.

THE OPPORTUNITY FOR REASSESSMENT IN THIS MODULE:

Opportunities for re-assessment is only permitted provided you have not failed more credit than in the resit rule adopted by your programme.  If the amount of credit you have failed is more than permitted by the relevant resit rule, you may be permitted to repeat study if you are within the threshold set for the Repeat rule adopted by your programme.  You will be notified of your eligibility to resit/repeat any modules after the Examining Board in the Summer period.

All resit assessments will be held in the Resit Examination period, prior to the start of the following academic session.

Graph Fundamentals:       

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

Exact algorithms for Graphs and Networks:      

• Depth and Breadth first search.
• Minimum Spanning Trees (Prim’s and Kruskal’s algorithms).
• Shortest Path Problems (Dijkstra’s 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 problem.

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.

Graph Colouring

• Greedy algorithms and bounds on the chromatic number
• the DSatur and PartialCol algorithm