Rhyd Lewis

Cardiff School of Mathematics,

Cardiff University, Cardiff, CF24 4AG, WALES.

Welcome to my webpage. Below you will find information about my teaching, research, publications, and presentations. Some useful research resources, code, and problem instances can also be found by following the links below.

If you would like to contact me, arrange a visit, or are interested in a pursuing a PhD, please use the email address above.

Research and Teaching

I am a reader at Cardiff School of Mathematics and a member of the department's Operational Research Group. I am the director of two MSc programs in the School of Mathematics: the MSc in Operational Research and Applied Statistics, and the MSc in Operational Research, Applied Statistics and Financial Risk. More information can be found here. In addition, here is a nice short video highlighting some of the research activities carried by the School.

I am an associate editor for the International Journal of Metaheuristics, having co-founded the journal in 2007. I am also a member of the program committees for *Evolutionary Computation in Combinatorial Optimisation*, the *Practice and Theory of Automated Timetabling*, *GECCO*, and the *International Metaheuristics Conference* series. From 2015 to 2017 I led a two-year £250k Health and Care Research Wales-funded project entitled "Prudent Elective Surgery Scheduling: A Whole Systems Approach".

I am also a fellow of the Cardiff University Data Innovation Research Institute.

I am currently teaching the following modules in the School of Mathematics: MA2900 Problem Solving and MA3602 Algorithms and Heuristics. Previous modules include MAT002 Statistical Methods; MA0276 Visual Basic for Operational Research; MAT004 Computational Methods; and MA0105 Foundations of Probability. I also previously taught the following modules at Cardiff Business School: BSP658 Business Statistics; BS0511 Quantitative Methods for Business; and BS1501 Applied Statistics and Mathematics for Economics and Business. I am a fellow of the Higher Education Academy.

- The application and analysis of metaheuristic and integer programming algorithms;

- Algorithmic graph theory;

- Graph colouring (including vertex colouring, edge colouring and happy colouring);

- Operating theatre scheduling;

- School bus routing;

- Automated timetabling (course and exam) and related problems;

- Grouping/Partitioning problems;

- Sports timetabling, particularly round-robin scheduling;

- Solving sudoku problems with metaheuristics;

- Bin-packing, trapezoid (trapezium) packing, and the equal-piles problem;

- Vehicle routing and arc routing, particularly dynamic variants of the problem;

Publications and Presentations

Resources

Graph colouring is the task of painting all vertices of a graph so that (a) all pairs of adjacent vertices are assigned different colours, and (b) the number of colours used is minimal. For example, the image on the right shows a solution using just three colours, which is actually the minimum for this particular graph. The graph colouring problem has applications in many practical areas of operations research including university timetabling, sports scheduling, creating seating plans, and solving sudoku puzzles. It is also strongly related to the Four Colour Theorem, which was previously one of the most famous unsolved problems in all of mathematics.

Some short introductory videos into the field of graph colouring can be found at the following links:

- An Introduction to Graph Colouring;

- Constructive Algorithms for Graph Colouring;

- Practical Applications of Graph Colouring.

For further information on graph colouring and its applications, please refer to my 2015 book *A Guide to Graph Colouring: Algorithms and Applications*, ISBN: 978-3-319-25728-0. The suite of graph colouring algorithms used in this book is available here. These have been coded in C++, and the resource also contains compilation and usage instructions. Information on these algorithms can also be found in the paper: *"Lewis, R., J. Thompson, C. Mumford, and J. Gillard (2012) 'A Wide-Ranging Computational Comparison of High-Performance Graph Colouring Algorithms'. Computers and Operations Research, vol. 39(9), pp. 1933-1950"*.

A useful bibliography on the graph colouring problem, maintained by Marco Chiarandini and Stefano Gualandi, can be found here. In addition, information on upper bounds for some well-known problem instances can be found here.

The school bus routing problem involves compiling a list of eligible students and then efficiently organising their transport to school. This process requires the selection of a suitable set of pick-up points (bus stops), the assignment of students to these pick-up points, and then the design of bus routes that visit these stops while getting students to school on time. In doing this, four factors should be considered.: (1) We should try to reduce economic costs by minimising the number of vehicles used; (2) Bus journeys should not be too long for students; (3) Pick-up points should be close to people’s houses; (4) Buses should not be over-filled.

This problem is an interesting mix of vehicle routing, set covering, and the bin packing problem and it can be very difficult to find solutions for. Some of my publications above have looked at producing effective approximation algorithms for this problem. Further details, including visualisations of problems and a suite of benchmark problem instances, can also be found on a dedicated webpage here.

Another problem that involves colouring vertices in a graph is the Maximum Happy Vertices problem. Here, we are given a graph in which some of the vertices are already coloured (as with the left graph in the figure). Our task is to then colour the remaining vertices so that they are given the same colour as all of their neighbours. In the example solution on the right, we see that most vertices are "happy" because they are the same colour as their neighbours. However, because of the colourings specified in the original graph, it is not possible for all vertices to be happy. (Unhappy vertices are marked with a "U".) This sort of problem is useful in identifying community structures in social networks, amongst other things.

The Trapezoid Packing Problem is closely related to the one-dimensional bin packing problem. Here, items are trapezoidal in shape with a fixed height and variable width. A practical application arises in the roofing industry, where large numbers of roof trusses of different lengths and different "end angles" have to be cut from boards of a given length such that wastage is minimsed. Though similar to one-dimensional bin packing, the problem is complicated by the fact that the ends of the trapezoids need to be "nested" so that wastage between consecutive shapes is kept to a minimum. This problem was first introduced and analysed in the 2011 paper 'An Investigation into two Bin Packing Problems with Ordering and Orientation Implications'. The problem instances used in this paper can be downloaded here.

In our 2016 publication 'How to Pack Trapezoids: Exact and Evolutionary Algorithms' significant improvements to the results reported in the 2011 paper were achieved by (a) designing and making use of an exact polynomial-time algorithm for optimally packing a set of fixed-height trapezoids into a single bin, and (b) by using a number of specialised evolutionary-based methods when packing across multiple bins. The source code and a detailed breakdown of the results of this work is available here.

Some of my research has focussed on the production of efficient algorithms for timetabling problems. A large number of timetabling problem instances are available for this problem on the website of the Second International Timetabling Competition (ITC2007). Some hard timetabling instances can also be found here. This latter set contains sixty problem instances of varying sizes that are intended to be more difficult than the competition instances with regards to both finding feasibility and satisfying soft constraints. Source code and results for the algorithm presented in *Lewis, R. and J. Thompson (2015) 'Analysing the Effects of Solution Space Connectivity with an Effective Metaheuristic for the Course Timetabling Problem'. European Journal of Operational Research, vol. 240, pp. 637-648* can be found here

An important part of our £250k Health and Care Research Wales-funded project "*Prudent Elective Surgery Scheduling: A Whole Systems Approach*", was the production of optimal surgery schedules at hospitals. When a patient enters a hospital for an elective operation, it is imperative that a bed is available for them to go into after surgery. However, sometimes all beds in the ward will be occupied, meaning that the operation will have to be cancelled. Our research has shown that cancellations occur far less frequently if operations are scheduled throughout the week appropriately. As part of this, our models also need to take into account various hospital requirements, the unexpected arrival or emergency patients, and the variability in the time patients take to recover after their operations. More information can be found in my list of publications.

Many transportation problems in operational research, such as the travelling salesman problem and vehicle routing problem, make use of a distance matrix. This is a matrix that gives the optimal driving distance (or travel time) between all pairs of locations within a set. A small number of online services exist for producing distance matrices, such as the Google Maps Distance Matrix API, but the sizes of matrices offered are usually very limited. To these ends, here is my own program for producing large distance matrices and travel time matrices. This program is coded in C# and uses Bing Maps to produce matrices of up to 1079x1079 entries in a single sitting. Larger matrices can also be produced, though users should ensure they do not exceed the Bing daily usage limit (see the instructions within the attachment).

Some of my work has concerned the use of metaheuristics to help solve sudoku puzzles. The C++ code used for experiments described in *"Lewis, R. (2007). 'Metaheuristics can Solve Sudoku Puzzles' Journal of Heuristics, vol. 13 (4), pp. 387-401"*, can be downloaded here. Code for the random sudoku problem instance generator used in this research can be downloaded here.

Regarding Sudoku, here is a very useful Sudoku to Graph Coloring Converter. This program reads in a single sudoku problem (from a text file) and converts it into the equivalent graph coloring problem. The output file appears in the DIMACS format which can then be used as the input file for any suitable graph coloring algorithm. If a solution using the correct number of colours is found, this can then be easily converted back into the Sudoku representation, giving a valid solution to the original problem.

The travelling salesman problem (TSP) asks the following: "Given a set of cities with distances between each pair, what is the shortest tour that visits each city exactly once?" This is a famous example of an NP-hard problem and it is often used to help motivate the use of heuristics and metaheuristics. To these ends, here is a simple MS Excel-based program for finding approximate solutions to randomly generated Euclidean TSPs. This program is intended to show the run-time characteristics of (1) random descent, (2) simulated annealing, (3) steepest descent, (4) tabu search, and (5) evolutionary algorithms. A number of animated charts are also included to help illustrate their various run-time characteristics.

A sociogram is a graphical representation of social links between people. The example on the right shows data collected in a small classroom. Each node represents a student and arrows indicate friendships. Black arrows indicate that A likes B, and double-headed blue arrows indicate that both A and B like each other. Colours on the nodes are also used it indicate students that are popular (green), rejected (grey), controversial (orange) and neglected (pink). These classifications are based on the work of Robin Banerjee, found here.

An easy-to-use Excel-based tool for creating sociogram visualisations can be found by following this link. When drawing the network, the program uses a variant of simulated annealing to decide where to place each node on the plane, making the network easier to interpret visually. The cost function of this algorithm seeks to ensure a suitable balance between five criteria: (a) the arrows should not be too long; (b) pairs of arrows should not cross; (c) nodes should be spread out evenly; (d) nodes should not be too close to the border; and (e) arrows should not pass too closely to other nodes. If you want to know more about this optimisation algorithm, please contact me.

Previous work has also looked at the scheduling of sports events, and in particular round-robin leagues and tournaments. Here is a link to the ten sports scheduling benchmark problem files used in the paper *"Lewis, R. and J. Thompson (2011) 'On the Application of Graph Colouring Techniques in Round-Robin Sports Scheduling'. Computers and Operations Research, vol. 38(1), pp. 190-204".* Source code (C++) for the round-robin to graph colouring program, which was used to generate many of the graphs in the paper, can be found here.

Want to avoid sitting next to annoying guests at a party? See state of the art combinatorial optimisation techniques in action with this Wedding Seating Planner tool available at www.weddingseatplanner.com.

Maybe you're going on holiday and want to reduce airline baggage charges. If so, have a look at these ten tips for packing suitcases, which were produced for the GoCompare website.

Photos