Graph Colouring:

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. This problem has applications in many practical areas of operations research including university timetabling, sports scheduling, creating seating plans, and solving sudoku puzzles.

A suite of high-performance graph colouring algorithms is available here. These have been coded in c++ and were used for the comparison 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". The specific algorithms contained in this suite include: (1) the PartialCol algorithm of Blochliger and Zufferey; (2) the TabuCol algorithm of Hertz and de Werra; (3) the hybrid evolutionary algorithm of Galinier and Hao; (4) the AntCol algorithm of Thompson and Dowsland; (5) the hill climbing algorithm of Lewis; and (6) the complete, backtracking algorithm of Korman. Two single-parse constructive methods, DSatur and the greedy algorithm, are also included in this suite. Descriptions and references for all of these algorithms can be found in the abovepublication.

Timetabling:

Some of my research has focused on the timetabling problem formulation used in the firstInternational 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 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).

Bin Packing:

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.

Sudoku:

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

Sports Scheduling:

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 theround-robin to graph colouring program, which was used to generate many of the graphs in the paper, can be found here.

Trapezoid Packing:

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:

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.