iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/3-540-45349-0_34
Arc Consistency on n-ary Monotonic and Linear Constraints | SpringerLink
Skip to main content

Arc Consistency on n-ary Monotonic and Linear Constraints

  • Conference paper
  • First Online:
Principles and Practice of Constraint Programming – CP 2000 (CP 2000)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1894))

Abstract

Many problems and applications can be naturally modelled and solved using constraints with more than two variables. Such n-ary constraints, in particular, arithmetic constraints are provided by many finite domain constraint programming systems. The best known worst case time complexity of existing algorithms (GAC-schema) for enforcing arc consistency on general CSPs is O(edn) where d is the size of domain, e is the number of constraints and n is the maximum number of variables in a single constraint. We address the question of efficient consistency enforcing for n-ary constraints. An observation here is that even with a restriction of n-ary constraints to linear constraints, arc consistency enforcing is NP-complete. We identify a general class of monotonic n-ary constraints (which includes linear inequalities as a special case). Such monotonic constraints can be made arc consistent in time O(en 3 d). The special case of linear inequalities can be made arc consistent in time O(en 2 d) using bounds-consistency which exploits special properties of the projection function.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. F. Bacchus and P. van Beek, “On the conversion between non-binary and binary constraint satisfaction problems”, Proceedings of AAAI-98, Madison, WI, 1998

    Google Scholar 

  2. F. Benhamou, D. McAllester, and P. van Hentenryck, “CLP(intervals) Revisited”, Proceedings of 1994 International Symposium on Logic Programming, 124–138, 1994

    Google Scholar 

  3. F. Benhamou and W. Older, “Applying Interval Arithmetic to Real Integer and Boolean Constraints”, Journal of Logic Programming32(1), 1997

    Google Scholar 

  4. C. Bessiere, “Arc-consistency and arc-consistency again”, Artificial Intelligence 65:179–190, 1994

    Article  Google Scholar 

  5. C. Bessiere and J. Regin, “Arc consistency for general constraint networks: preliminary results”, Proceedings of IJCAI-97, Nagoya, Japan, 1997

    Google Scholar 

  6. C. Bessiere and J. Regin, “MAC and combined heuristics: two reasons to forsake FC(and CBJ?) on hard problems”, Proceedings of Principles and Practice of Constraint Programming, Cambridge, MA. 61–75, 1996

    Google Scholar 

  7. P. Codognet and D. Diaz, “Compiling Constraints in CLP(FD)”, Journal of Logic Programming 27(3), 185–226, 1996

    Article  MATH  MathSciNet  Google Scholar 

  8. E. Davis Constraint Propagation with Interval Labels Artificial Intelligence 32, 281–331, 1987

    Article  MATH  MathSciNet  Google Scholar 

  9. R. Dechter, I. Meiri and J. Pearl Temporal constraint networks Artificial Intelligence 49, 61–95, 1992

    Article  MathSciNet  Google Scholar 

  10. R. Dechter and J. Pearl, “Tree clustering for constraint networks”, Artificial Intelligence 38:353–366, 1989

    Article  MATH  MathSciNet  Google Scholar 

  11. E. Hyvonen Constraint reasoning based on interval arithmetic: the tolerance propagation approach Artificial Intelligence 58, 71–112, 1992

    Article  MathSciNet  Google Scholar 

  12. ILOG, ILOG SOLVER Reference Manual

    Google Scholar 

  13. Joxan Jaffar, Michael J. Maher, Peter J. Stuckey and Roland H. C. Yap Beyond Finite Domains PPCP’94: Proceedings of the Second Workshop on Principles and Practice of Constraint Programming, 1994, 86–94

    Google Scholar 

  14. J. Lauriere, “A language and a program for stating and solving combinatorial problems”, Artificial Intelligence 10:29–127, 1978

    Article  MATH  MathSciNet  Google Scholar 

  15. Y. Lebbah and O. Lhomme Acceleration methods for numeric CSPs Proc. of AAAI-98 1998

    Google Scholar 

  16. Lhomme, Olivier, Consistency Techniques for Numeric CSPs, Proceedings of IJCAI-93, Chambery, France, 232–238, 1993

    Google Scholar 

  17. A. K. Mackworth, “Consistency in Networks of Relations”, Artificial Intelligence 8(1):118–126, 1977

    Article  MathSciNet  Google Scholar 

  18. A. K. Mackworth, “On reading sketch maps”, Proceedings of IJCAI-77, 598–606, Cambridge MA, 1977

    Google Scholar 

  19. R. Mohr and G. Masini, “Good old discrete relaxation”, Proceedings of ECAI-88, 651–656, Munchen, FRG, 1988

    Google Scholar 

  20. R. E. Moore, Interval Analysis, Prentice Hall, 1966

    Google Scholar 

  21. G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, New York, Wiley, 1988

    MATH  Google Scholar 

  22. Older W. and Vellin, A. Constraint Arithmetic on Real Intervals Constraint Logic Programming: Selected Research, Benhamou, F. and Colmerauer, A.(eds.), 175–195, 1993

    Google Scholar 

  23. C. H. Papadimitriou, “On the complexity of integer programming”, J. of the ACM 28(4):765–768, 1981

    Article  MATH  MathSciNet  Google Scholar 

  24. J. C. Regin, “Generalized arc consistency for global cardinality constraint”, Proceedings of AAAI-96, 209–215, Portland, OR, 1996

    Google Scholar 

  25. F. Rossi, C. Petrie, and V. Dhar, “On the equivalence of constraint satisfaction problems”, Proceedings of the 9th European Conference on Artificial Intelligence, 550–556, Stockholm, Sweden, 1990

    Google Scholar 

  26. P. van Beek and R. Dechter, “On the minimality and global consistency of row-convex constraint networks”, Journal of the ACM 42(3):543–561, 1995

    Article  MATH  Google Scholar 

  27. P. van Hentenryck, Constraint Satisfaction and Logic Programming, MIT Press, Cambridge, 1989

    Google Scholar 

  28. P. van Hentenryck, Y. Deville, and C. M. Teng, “A Generic Arc-Consistency Algorithm and its Specializations”, Artif. Int. 58(1992):291–321, 1992

    Article  Google Scholar 

  29. P. van Hentenryck, L. Michel, and Y. Deville, Numerica: A Modeling Language for Global Optimization, MIT Press, Cambridge

    Google Scholar 

  30. D. L. Waltz, “Generating semantic descriptions from drawings of scenes with shadows”, MAC-AI-TR-217, MIT, 1972

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2000 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Yuanlin, Z., Yap, R.H.C. (2000). Arc Consistency on n-ary Monotonic and Linear Constraints. In: Dechter, R. (eds) Principles and Practice of Constraint Programming – CP 2000. CP 2000. Lecture Notes in Computer Science, vol 1894. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45349-0_34

Download citation

  • DOI: https://doi.org/10.1007/3-540-45349-0_34

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-41053-9

  • Online ISBN: 978-3-540-45349-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics