This article presents a basic scheme for deriving systematically a filtering algorithm from the graph properties based representation of global constraints. This scheme is based on the bounds of the graph parameters used in the description of a global constraint. The article provides bounds for the most common used graph parameters.
Mots-clés : global constraint, graph constraint, filtering, bound
@article{RO_2006__40_4_327_0,
author = {Beldiceanu, Nicolas and Petit, Thierry and Rochart, Guillaume},
title = {Bounds of graph parameters for global constraints},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {327--353},
publisher = {EDP-Sciences},
volume = {40},
number = {4},
year = {2006},
doi = {10.1051/ro:2007001},
mrnumber = {2308191},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2007001/}
}
TY - JOUR AU - Beldiceanu, Nicolas AU - Petit, Thierry AU - Rochart, Guillaume TI - Bounds of graph parameters for global constraints JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2006 SP - 327 EP - 353 VL - 40 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2007001/ DO - 10.1051/ro:2007001 LA - en ID - RO_2006__40_4_327_0 ER -
%0 Journal Article %A Beldiceanu, Nicolas %A Petit, Thierry %A Rochart, Guillaume %T Bounds of graph parameters for global constraints %J RAIRO - Operations Research - Recherche Opérationnelle %D 2006 %P 327-353 %V 40 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2007001/ %R 10.1051/ro:2007001 %G en %F RO_2006__40_4_327_0
Beldiceanu, Nicolas; Petit, Thierry; Rochart, Guillaume. Bounds of graph parameters for global constraints. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 4, pp. 327-353. doi : 10.1051/ro:2007001. http://www.numdam.org/articles/10.1051/ro:2007001/
[1] , and, Global Constraints for Partial CSPs: A Case-Study of Resource and Due Date Constraints, in Principles and Practice of Constraint Programming (CP'98), edited by M. Maher and J.-F. Puget, Springer-Verlag, Lect. Notes Comput. Sci. 1520 (1998) 87-101.
[2] , Global Constraints as Graph Properties on a Structured Network of Elementary Constraints of the Same Type, in Principles and Practice of Constraint Programming (CP'2000), edited by R. Dechter, Springer-Verlag, Lect. Notes Comput. Sci. 1894 (2000) 52-66. Preprint available as SICS Tech Report T2000-01. | Zbl
[3] , Global Constraints as Graph Properties on Structured Network of Elementary Constraints of the Same Type. Technical Report T2000-01, Swedish Institute of Computer Science (2000). | Zbl
[4] , and, Deriving Filtering Algorithms from Constraint Checkers, in Principles and Practice of Constraint Programming (CP'2004), edited by M. Wallace, Springer-Verlag, Lect. Notes Comput. Sci. 3258 (2004) 107-122. Preprint available as SICS Tech Report T2004-08.
[5] , and, Global Constraint Catalog. Technical Report T2005-08, Swedish Institute of Computer Science (2005).
[6] and, Cost Evaluation of Soft Global Constraints, in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CP-AI-OR 2004), edited by J.-C. Régin and M. Rueher, Springer-Verlag, Lect. Notes Comput. Sci. 3011 (2004) 80-95. | Zbl
[7] ,,, and, Filtering Algorithms for the nvalue Constraint, in International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR'05), Prague, Czech Republic, edited by R. Barták and M. Milano, Springer-Verlag, Lect. Notes Comput. Sci. 3524 (2005) 79-93 | Zbl
[8] and, To Be or not to Be... a Global Constraint, in Principles and Practice of Constraint Programming (CP'2003), edited by F. Rossi, Springer-Verlag, Lect. Notes Comput. Sci. 2833 (2003) 789-794.
[9] and, Refining the Basic Constraint Propagation Algorithm, in Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, 2001, edited by B. Nebel, Morgan Kaufmann (2001) 309-315.
[10] , and, CP(Graph): Introducing a Graph Computation Domain in Constraint Programming, in Principles and Practice of Constraint Programming (CP'2005), edited by P. van Beek, Springer-Verlag, Lect. Notes Comput. Sci. 3709 (2005) 211-225.
[11] and, Partial constraint satisfaction. Artificial Intelligence 58 (1992) 21-70.
[12] and, Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Company (1979). | MR | Zbl
[13] , Implementing Global Constraints as Structured Graphs of Elementary Constraints. Scientific Journal Acta Cybernetica 16 (2003) 241-258. | Zbl
[14] , and, A Generic Arc Consistency Algorithm and its Specializations. Artificial Intelligence 57 (1992) 291-321. | Zbl
[15] , and, Design, implementation, and evaluation of the constraint language cc(FD). J. Logic Programming 37 (1998) 139-164. | Zbl
[16] and, Fast Bound Consistency for the global cardinality Constraint, in Principles and Practice of Constraint Programming (CP'2003), edited by F. Rossi, Springer-Verlag, Lect. Notes Comput. Sci. 2833 (2003) 437-451.
[17] and, Faster Algorithms for Bound-Consistency of the sortedness and the alldifferent Constraint, in Principles and Practice of Constraint Programming (CP'2000), edited by R. Dechter, Springer-Verlag, Lect. Notes Comput. Sci. 1894 (2000) 306-319. | Zbl
[18] , Networks of constraints: Fundamental properties and applications to picture processing. Information Science 7 (1974) 95-132. | Zbl
[19] and, An algorithm for minimum cover of a graph. American Math. Soc. 10 (1959) 315-319. | Zbl
[20] , A Regular Language Membership Constraint for Finite Sequences of Variables, in Principles and Practice of Constraint Programming (CP'2004) edited by M. Wallace, Springer-Verlag, Lect. Notes Comput. Sci. 3258 (2004) 482-495.
[21] , and, Meta constraints on violations for over constrained problems, in 12th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2000), 13-15 November 2000, Vancouver, BC, Canada, IEEE Computer Society (2000) 358-365.
[22] , and, Specific filtering algorithms for over constrained problems, in Principles and Practice of Constraint Programming (CP'2001), edited by T. Walsh, Springer-Verlag, Lect. Notes Comput. Sci. 2239 (2001) 451-463. | Zbl
[23] ,, and, Improved Algorithms for the global cardinality Constraint, in Principles and Practice of Constraint Programming (CP'2004), edited by M. Wallace, Springer-Verlag, Lect. Notes Comput. Sci. 3258 (2004) 542-556.
[24] , A Filtering Algorithm for Constraints of Difference in CSP, in 12th National Conference on Artificial Intelligence (AAAI-94) (1994) 362-367.
[25] , Generalized Arc Consistency for global cardinality Constraint, in 14th National Conference on Artificial Intelligence (AAAI-96) (1996) 209-215.
[26] , The Symmetric alldiff Constraint, in 16th Int. Joint Conf. on Artificial Intelligence (IJCAI-99) (1999) 420-425.
[27] , On an Extremal Problem in Graph Theory. Mat. Fiz. Lapok 48 (1941) 436-452, in Hungarian. | Zbl
[28] , A Hyper-Arc Consistency Algorithm for the soft alldifferent Constraint, in Principles and Practice of Constraint Programming (CP'2004), edited by M. Wallace, Springer-Verlag, Lect. Notes Comput. Sci. 3258 (2004) 679-689.
[29] , and, On global warming: Flow-based soft global constraints, in Journal of Heuristics 12 (2006) 347-373. | Zbl
[30] , Solving Constraint Satisfaction Problems using Finite State Automata, in National Conference on Artificial Intelligence (AAAI-92), AAAI Press (1992) 453-458.
Cité par Sources :
