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

TitreUsing solution properties within an enumerative search to solve a sports league scheduling problem
Type de publicationArticle de revue
AuteurHamiez, Jean-Philippe , Hao, Jin-Kao
EditeurElsevier
TypeArticle scientifique dans une revue à comité de lecture
Année2008
LangueAnglais
Date2008/05/28
Numéro10
Pagination1683 - 1693
Volume156
Titre de la revueDiscrete Applied Mathematics
ISSN0166-218X
Mots-clésEnumerative search, Prob026 from CSPLib, Sports league scheduling
Résumé en anglais

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 ⩽ 40 and the direct construction methods available only solve instances where ( T - 1 ) mod 3 ≠ 0 or T / 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.

URL de la noticehttp://okina.univ-angers.fr/publications/ua4276
DOI10.1016/j.dam.2007.08.019
Lien vers le document

http://dx.doi.org/10.1016/j.dam.2007.08.019