Cardiff Business School

CBS Faculty

Current Activities

• I am a lecturer and member of the Quantitative Methods Research Group the Cardiff Business School at Cardiff University.
• I am joint Editor in Chief for the International Journal of Metaheuristics
• I am one of the co-organisers of the Second International Timetabling Competition, which is currently underway and began on the 1st of August 2007.
• I am currently lecturing on the following modules in Cardiff Business School: BSP658 Business Statistics; BS0511 Quantitative Methods for Business; BS1501 Applied Statistics & Mathematics for Economics and Business.
• I am a member of the program committee for the Evolutionary Computation in Combinatorial Optimisation (EvoCop) Series.
  

Research Interests

• Operations Research;
• Application of metaheuristics (such as evolutionary algorithms, simulated annealing, tabu search, iterated local search and ant colony optimisation);
• Automated timetabling (course and exam);
• Grouping/Partitioning Problems;
• Solving Sudoku Problems with Metaheuristics;
• Graph colouring;
• Bin-packing and the equal-piles problem;
• The traveling salesperson problem;
• Problem difficulty;
• Scheduling, routing, and constraint satisfaction.

Publications

2008

Lewis, R. (2008) 'A Survey of Metaheuristic-based Techniques for University Timetabling Problems'. OR Spectrum, vol 30 (1) pp 167-190 [bibtex] (The original publication is available at www.springerlink.com [bibtex]

2007

Lewis, R. (2007) 'Metaheuristics can Solve Sudoku Puzzles'. Journal of Heuristics, vol. 13 (4), pp 387-401. [bibtex] (The original publication is available at www.springerlink.com)

Lewis, R., Paechter, B. 'Finding Feasible Timetables Using Group-Based Operators'. IEEE Transactions on Evolutionary Computation, 11(3), pp 397-413. [bibtex]

Lewis, R. (2007) 'On the Combination of Constraint Programming and Stochastic Search: The Sudoku Case'. In Hybrid Metaheuristics (Lecture Notes in Computer Science vol. 4771) T. Bartz-Beielstein, M. Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph, and M. Sampels (Eds.) Berlin: Springer-Verlag, pp 96-107, ISBN 978-3-540-75513-5 [bibtex] (The original publication is available at www.springerlink.com)

Lewis, R., Paechter, B., McCollum, B. (2007) 'Post Enrolment based Course Timetabling: A Description of the Problem Model used for Track Two of the Second International Timetabling Competition'. Cardiff Working Papers in Accounting and Finance A2007-3, Cardiff Business School, Cardiff University, Wales, CF10 3EU, August 2007. ISSN: 1750-6658 [bibtex]

Lewis, R., Paechter, B., and Rossi-Doria, O. (2007) 'Metaheuristics for University Course Timetabling'. In Evolutionary Scheduling (Studies in Computational Intelligence, vol. 49), K. Dahal, Kay Chen Tan, P. Cowling (Eds.) Berlin: Springer-Verlag, pp 237-272, ISBN: 3540485821 [bibtex]

2006

Lewis, R. (2006) 'Metaheuristics for University Course Timetabling'. Doctoral Thesis, Napier University, Edinburgh, Scotland. [bibtex]

2005

Lewis, R. and Paechter, B. (2005). 'An Empirical Analysis of the Grouping Genetic Algorithm: The Timetabling Case'. In Proceedings of the 2005 IEEE World Congress on Evolutionary Computation, Edinburgh, Scotland, pp 2856-2863, ISBN 0-7803-9363-5. [bibtex]

Lewis, R. and Paechter, B. (2005). 'Application of the Grouping Genetic Algorithm to University Course Timetabling'. In Evolutionary Computation in Combinatorial Optimisation (Lecture Notes in Computer Science vol. 3448) J. Gottlieb and G. Raidl (Eds.) Berlin: Springer-Verlag, pp 144-153, ISBN 3-540-25337 [bibtex] (The original publication is available at www.springerlink.com)

2004

Lewis, R. and Paechter, B. (2004). 'New Crossover Operators for Timetabling with Evolutionary Algorithms'. In Proceedings of the 5th International Conference on Recent Advances in Soft Computing (RASC 2004), A. Lofti (Ed.), Nottingham, England, pp 189-195. ISBN: 1-84233-110-8. [bibtex]

resources

Timetabling: Some of the research that I have done has focused on a timetabling problem formulation that was used for the 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 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 I'd be delighted to hear from them. Also have a look at the Second International Timetabling Competition (ITC2007), which began on the 1st of August 2007.

Sudoku: As you will see from my publications list, some of my work has concerned the use of metaheuristics (particularly simulated annealing) to help solve sudoku puzzles. If you want do 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 (also as a zip file).

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. A linux tar.gz version of the same program is available here

Demonstrating how a small sudoku solution can be converted into a graph colouring problem