Using solution properties within an enumerative search to solve a sports league scheduling problem

This paper presents an enumerative approach for a particular sports league scheduling problem known as “Prob026” in CSPLib. Despite its exponential-time complexity, this simple method can solve all instances involving a number T   of teams up to 50 in a reasonable amount of time while the best known tabu search and constraint programming algorithms are limited to T⩽40T⩽40 and the direct construction methods available only solve instances where (T-1)mod3≠0 or T/2T/2 is odd. Furthermore, solutions were also found for some T values up to 70. The proposed approach relies on discovering, by observation, interesting properties from solutions of small problem instances and then using these properties in the final algorithm to constraint the search process.