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.
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.
@article{RO_2005__39_2_87_0,
author = {Deleau, Herv\'e and Hao, Jin-Kao and Saubion, Fr\'ed\'eric},
title = {Algorithmes hybrides g\'en\'eriques pour la r\'esolution de probl\`emes de satisfaction de contraintes},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {87--103},
publisher = {EDP-Sciences},
volume = {39},
number = {2},
year = {2005},
doi = {10.1051/ro:2005006},
mrnumber = {2181793},
zbl = {1104.90056},
language = {fr},
url = {http://archive.numdam.org/articles/10.1051/ro:2005006/}
}
TY - JOUR AU - Deleau, Hervé AU - Hao, Jin-Kao AU - Saubion, Frédéric TI - Algorithmes hybrides génériques pour la résolution de problèmes de satisfaction de contraintes JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2005 SP - 87 EP - 103 VL - 39 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro:2005006/ DO - 10.1051/ro:2005006 LA - fr ID - RO_2005__39_2_87_0 ER -
%0 Journal Article %A Deleau, Hervé %A Hao, Jin-Kao %A Saubion, Frédéric %T Algorithmes hybrides génériques pour la résolution de problèmes de satisfaction de contraintes %J RAIRO - Operations Research - Recherche Opérationnelle %D 2005 %P 87-103 %V 39 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro:2005006/ %R 10.1051/ro:2005006 %G fr %F RO_2005__39_2_87_0
Deleau, Hervé; Hao, Jin-Kao; Saubion, Frédéric. Algorithmes hybrides génériques pour la résolution de problèmes de satisfaction de contraintes. RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 2, pp. 87-103. doi : 10.1051/ro:2005006. http://archive.numdam.org/articles/10.1051/ro:2005006/
[1] and, editors. Local Search in Combinatorial Optimization. John Wiley and Sons (1997). | MR | Zbl
[2] and, Extending chip in order to solve complex scheduling problems. J. Math. Comput. Modelling 17 (1993) 57-73.
[3] , From chaotic iteration to constraint propagation, in 24th International Colloquium on Automata, Languages and Programming (ICALP '97), Springer. Lect. Notes Comput. Sci. 1256 (1997) 36-55. Invited lecture.
[4] and, Introducing global constraints in chip. J. Math. Comput. Modelling 20 (1994) 97-123. | Zbl
[5] , Heterogeneous constraint solving, in Proceedings of the Fifth international conference on algebraic and logic programming, ALP'96, Springer. Lect. Notes Comput. Sci 1256 (1996) 62-76.
[6] , and, A chessboard coloring problem revisited, in Proceedings of the 7th Workshop on Practical Solving of NP-complete Problems (JNPC01), Toulouse (2001).
[7] ,, and, Local search and constraint programming, in Handbook of Metaheuristics, edited by F. Glover and G. Kochenberger, Kluwer (2002). | MR | Zbl
[8] , and, http://www.4c.ucc.ie/~tw/csplib/, funded by the UK Network of Constraints.
[9] and, Tabu Search. Kluwer Academic Publishers (1997). | MR | Zbl
[10] , Constraint Satisfaction in Logic Programming. MIT Press (1989). | MR
[11] , Adaptation in Natural and Artificial Systems. U. of Michigan Press (1975). | MR | Zbl
[12] and, Local search with constraint propagation and conflict-based heuristics. Artif. Intell. 139 (2002) 21-45. | Zbl
[13] and, Vers une unification des algorithmes de résolution de csp2002) 155-168.
[14] , Encyclopedia on Artificial Intelligence, chapter Constraint Satisfaction. John Wiley (1987).
[15] and, Using milp and cp for the scheduling of batch chemical processes. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Spinger. Lect. Notes Comput. Sci. 3011 (2004) 1-20. | Zbl
[16] and, Programming with Constraints, An introduction. MIT Press (1998). | MR | Zbl
[17] and, Arc and path consistency revisited. Artif. Intell. 28 (1986) 225-233.
[18] and, A view of local search in constraint programming, in Proc. of the Second International Conference on Principles and Practice of Constraint Programming, edited by E. Freuder, Springer. Lect. Notes Comput. Sci. 1118 (1996) 353-366.
[19] , A hybrid search architecture applied to hard random 3-sat and low-autocorrelation binary sequences, in Principles and Practice of Constraint Programming - CP 2000 edited by R. Dechter, Springer. Lect. Notes Comput. Sci. 1894 (2000) 337-352. | Zbl
[20] , A filtering algorithm for constraint of difference in csps, in National Conference of Artificial Intelligence (1994) 362-367.
[21] , Using constraint programming and local search methods to solve vehicle routing problems, in Principles and Practice of Constraint Programming - CP98, Springer. Lect. Notes Comput. Sci. 1520 (1998) 417-431.
[22] , Foundations of Constraint Satisfaction. Academic Press, London (1993).
[23] and, Filtrage par arc-consistance et recherche tabou pour l'allocation de fréquence avec polarisation, in Actes des JNPC 2002 (2002).
Cité par Sources :
