Dr Rhyd Lewis
Telephone: +44(0)29 208 74856
Fax: +44(0)29 208 74199
- The application and analysis of metaheuristic algorithms;
- Automated timetabling (course and exam) and related problems;
- Grouping/Partitioning problems;
- Graph colouring;
- Sports timetabling, particularly round-robin ccheduling;
- Solving sudoku problems with metaheuristics;
- Bin-packing, trapezoid (trapezium) packing, and the equal-piles problem;
- Vehicle routing;
- Problem difficulty and problem generation;
- Scheduling, routing, and constraint satisfaction.
Member of Operational Research Group
Member of the Planning and Optimisation Group
Member of School Research Committee
Associate editor for the International Journal of Metaheuristics
Program-committee member for Evolutionary Computation in Combinatorial Optimisation, EvoEnvironment, GECCO, the Congress of Evolutionary Computing and the Practice and Theory of Automated Timetabling conferences.
Some of my research has focused on the timetabling problem formulation used in the first International Timetabling Competition run in 2003. The twenty problem instances used in this competition can be found here. 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 the soft constraints. If anyone has been using these instances in their work then please let me know. A large number of other timetabling problem instances are also available on the website of the Second International Timetabling Competition (ITC2007), which I co-organised in 2007-2008.
This section contains some resources concerned with my research on grouping problems, particulary graph colouring and bin packing problems. A good resource of benchmark problem instances for the one-dimensional bin packing problem can be found here in the problem repository of Scholl and Klein. The "uniform" and "triplet" bin packing instances of Falkenauer can also be found here and are stored on the Operational Research Library of Beasley. Note that these latter instances contain information regarding the minimum number of bins required in optimal solutions, but in a small number of the "uniform" instances, the stated optima are incorrect and will need to be changed manually before use. The correct optima for these instances were determined by I. Gent (Gent, I. (1998) 'Heuristic Solution of Open Bin Packing Problems'. Journal of Heuristics, 3(4), pp. 299-304) and are specified within this publication.)
Moving on to the graph colouring problem, here are a number of comma delimited text files containing the experimental data gained in "Lewis, R. (2009) 'A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing'. Computers and Operations Research, vol. 36(7), pp 2295-2310" (descriptions included). The graph colouring problem generator of Joe Culberson used in this work can also be downloaded from Joe Culberson's graph colouring resources page. As well as this tool, Joe Culberson's webpage also contains a variety of other programs and resources useful for graph colouring research, including solvers, generators and publications.
As you will see from my publications list, some of my work has concerned the use of metaheuristics to help solve sudoku puzzles. If you want to download the c++ code used for the experiments described in "Lewis, R. (2007). 'Metaheuristics can Solve Sudoku Puzzles' Journal of Heuristics, vol. 13 (4), pp 387-401", it can be downloaded here as a .zip file. The c++ 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 your favourite 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.
Some of my previous work has 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. A description of the file layouts is also included in this resource. 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.
Research has also been conducted on an interesting variant of the one-dimensional bin packing problem where items are trapezoidal in shape with a fixed height. A practical application of this problem 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 is introduced and analysed in the paper "Lewis, R., X. Song, K. Dowsland and J. Thompson (2011) 'An Investigation into two Bin Packing Problems with Ordering and Orientation Implications'. European Journal of Operational Research, vol. 213, pp. 52-65." The problem instances used in this paper can be downloaded here.
Making Seating Plans:
Dr Rhyd Lewis is a lecturer in operational research at Cardiff School of Mathematics, Cardiff University. Previously he was a lecturer in quantitative methods at Cardiff Business School. Dr Lewis holds a PhD in Computer Science and Operational Research (Edinburgh Napier University, 2006) and a BSc in Computing (University of Wales, Swansea, 2002).
Dr Lewis is a programme committee member for a number of scientific conferences such as, EvoCop, Evo‐Environment, and PATAT. He has published articles in various scientific journals, conferences and books and is also the co‐founder and associate editor of the International Journal of Metaheuristics (www.inderscience.com/ijmheur). He is part of the LANCS initiative (www.lancs‐initiative.ac.uk) and is a contributing member of the WIMCS Statistics and OR cluster (www.wimcs.ac.uk).