Issue |
RAIRO-Oper. Res.
Volume 39, Number 2, April-June 2005
|
|
---|---|---|
Page(s) | 87 - 103 | |
DOI | https://doi.org/10.1051/ro:2005006 | |
Published online | 15 October 2005 |
Algorithmes hybrides génériques pour la résolution de problèmes de satisfaction de contraintes
Generic hybrid algorithms for solving constraint satisfaction problems
LERIA, Université d'Angers, 2 bd Lavoisier,
49045 Angers, France; deleau@info.univ-angers.fr; hao@info.univ-angers.fr; saubion@info.univ-angers.fr
Reçu :
9
Mars
2004
Accepté :
8
Février
2005
Nous présentons dans cet article un algorithme générique hybride permettant de combiner des méthodes complètes (programmation par contraintes) et incomplètes (recherche locale) pour la résolution de problèmes de satisfaction de contraintes. Ce schéma algorithmique basé sur la gestion de populations, utilise des techniques de propagation de contraintes intégrant également des heuristiques de recherche locale. Les structures utilisées autorisent une interaction homogène entre les différentes méthodes mises en œuvre et permettent également de bénéficier de leurs atouts respectifs. Nous proposons alors diverses stratégies de combinaisons dont nous mettons en avant l'intérêt sur quelques exemples par le biais d'une implémentation.
Abstract
In this paper, we present a generic hybrid algorithm for combining complete (constraint programming) and incomplete (local search) methods in order to solve constraint satisfaction problems. This algorithmic scheme uses constraint propagation techniques and local search heuristics over populations. The structures involved provide an harmonious interaction between the different methods, and also benefit from the respective methods' assets. We propose various combination strategies and emphasize their interest on some examples which are solved by means of an implementation.
Key words: Satisfaction de contraintes / propagation de contraintes / méthodes de recherche hybride.
© EDP Sciences, 2005
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.