Bounds of graph parameters for global constraints

Nicolas Beldiceanu; Thierry Petit; Guillaume Rochart

RAIRO - Operations Research (2007)

  • Volume: 40, Issue: 4, page 327-353
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Beldiceanu, Nicolas, Petit, Thierry, and Rochart, Guillaume. "Bounds of graph parameters for global constraints." RAIRO - Operations Research 40.4 (2007): 327-353. <http://eudml.org/doc/105353>.

@article{Beldiceanu2007,
abstract = { 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. },
author = {Beldiceanu, Nicolas, Petit, Thierry, Rochart, Guillaume},
journal = {RAIRO - Operations Research},
keywords = {Global constraint; graph constraint; filtering; bound.; global constraint},
language = {eng},
month = {2},
number = {4},
pages = {327-353},
publisher = {EDP Sciences},
title = {Bounds of graph parameters for global constraints},
url = {http://eudml.org/doc/105353},
volume = {40},
year = {2007},
}

TY - JOUR
AU - Beldiceanu, Nicolas
AU - Petit, Thierry
AU - Rochart, Guillaume
TI - Bounds of graph parameters for global constraints
JO - RAIRO - Operations Research
DA - 2007/2//
PB - EDP Sciences
VL - 40
IS - 4
SP - 327
EP - 353
AB - 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.
LA - eng
KW - Global constraint; graph constraint; filtering; bound.; global constraint
UR - http://eudml.org/doc/105353
ER -

References

top
  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.  
  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).  
  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.  
  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  
  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 Intelligence58 (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).  
  13. D. Hanák, Implementing Global Constraints as Structured Graphs of Elementary Constraints. Scientific Journal Acta Cybernetica16 (2003) 241–258.  
  14. P. Van Hentenryck, Y. Deville and C.M. Teng, A Generic Arc Consistency Algorithm and its Specializations. Artificial Intelligence57 (1992) 291–321.  
  15. P. Van Hentenryck, V. Saraswat and Y. Deville, Design, implementation, and evaluation of the constraint language cc(FD). J. Logic Programming37 (1998) 139–164.  
  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.  
  18. U. Montanari, Networks of constraints: Fundamental properties and applications to picture processing. Information Science7 (1974) 95–132.  
  19. R.Z. Norman and M.O. Rabin, An algorithm for minimum cover of a graph. American Math. Soc.10 (1959) 315–319.  
  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.  
  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. Lapok48 (1941) 436–452, in Hungarian.  
  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 Heuristics12 (2006) 347–373.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.