Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
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 Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : mercredi 9 juin 2021 - 14:58:04
Dernière modification le : mercredi 20 octobre 2021 - 03:19:09

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

4