Bounds of graph parameters for global constraints
RAIRO - Operations Research - Recherche Opérationnelle, Volume 40 (2006) no. 4, pp. 327-353.

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.

DOI: 10.1051/ro:2007001
Classification: 68R01
Keywords: global constraint, graph constraint, filtering, bound
Beldiceanu, Nicolas ; Petit, Thierry ; Rochart, Guillaume 1

1 Bouygues e-lab, 78061 St Quentin en Yvelines, France
@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://archive.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://archive.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://archive.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, Volume 40 (2006) no. 4, pp. 327-353. doi : 10.1051/ro:2007001. http://archive.numdam.org/articles/10.1051/ro:2007001/

[1] P. Baptiste, C. Le Pape and L. Peridy, 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] N. Beldiceanu, 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] N. Beldiceanu, 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] N. Beldiceanu, M. Carlsson and T. Petit, 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] N. Beldiceanu, M. Carlsson and J.-X. Rampon, Global Constraint Catalog. Technical Report T2005-08, Swedish Institute of Computer Science (2005).

[6] N. Beldiceanu and T. Petit, 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] C. Bessière, E. Hebrard, B. Hnich, Z. Kızıltan and T. Walsh, 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] C. Bessière and P. Van Hentenryck, 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] C. Bessière and J.-C. Régin, 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] G. Dooms, Y. Deville and P. Dupont, 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] E.C. Freuder and R.J. Wallace, Partial constraint satisfaction. Artificial Intelligence 58 (1992) 21-70.

[12] M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Company (1979). | MR | Zbl

[13] D. Hanák, Implementing Global Constraints as Structured Graphs of Elementary Constraints. Scientific Journal Acta Cybernetica 16 (2003) 241-258. | Zbl

[14] P. Van Hentenryck, Y. Deville and C.M. Teng, A Generic Arc Consistency Algorithm and its Specializations. Artificial Intelligence 57 (1992) 291-321. | Zbl

[15] P. Van Hentenryck, V. Saraswat and Y. Deville, Design, implementation, and evaluation of the constraint language cc(FD). J. Logic Programming 37 (1998) 139-164. | Zbl

[16] I. Katriel and S. Thiel, 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] K. Mehlhorn and S. Thiel, 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] U. Montanari, Networks of constraints: Fundamental properties and applications to picture processing. Information Science 7 (1974) 95-132. | Zbl

[19] R.Z. Norman and M.O. Rabin, An algorithm for minimum cover of a graph. American Math. Soc. 10 (1959) 315-319. | Zbl

[20] G. Pesant, 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] T. Petit, J-C. Régin and C. Bessière, 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] T. Petit, J-C. Régin and C. Bessière, 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] C.-G. Quimper, A. López-Ortiz, P. Van Beek and A. Golynski, 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] J.-C. Régin, A Filtering Algorithm for Constraints of Difference in CSP, in 12th National Conference on Artificial Intelligence (AAAI-94) (1994) 362-367.

[25] J.-C. Régin, Generalized Arc Consistency for global cardinality Constraint, in 14th National Conference on Artificial Intelligence (AAAI-96) (1996) 209-215.

[26] J.-C. Régin, The Symmetric alldiff Constraint, in 16th Int. Joint Conf. on Artificial Intelligence (IJCAI-99) (1999) 420-425.

[27] P. Turán, On an Extremal Problem in Graph Theory. Mat. Fiz. Lapok 48 (1941) 436-452, in Hungarian. | Zbl

[28] W.-J. Van Hoeve, 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] W.-J. Van Hoeve, G. Pesant and L.-M. Rousseau, On global warming: Flow-based soft global constraints, in Journal of Heuristics 12 (2006) 347-373. | Zbl

[30] N.R. Vempaty, Solving Constraint Satisfaction Problems using Finite State Automata, in National Conference on Artificial Intelligence (AAAI-92), AAAI Press (1992) 453-458.

Cited by Sources: