Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

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

Abstract :

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.

Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03255363
Contributeur : Okina Université d'Angers <>
Soumis le : mercredi 9 juin 2021 - 14:58:04
Dernière modification le : jeudi 10 juin 2021 - 03:39:58

Lien texte intégral

Identifiants

Collections

Citation

Jean-Philippe Hamiez, Jin-Kao Hao. Using solution properties within an enumerative search to solve a sports league scheduling problem. Discrete Applied Mathematics, Elsevier, 2008, 156 (10), pp.1683 - 1693. ⟨10.1016/j.dam.2007.08.019⟩. ⟨hal-03255363⟩

Partager

Métriques

Consultations de la notice

5