Proceedings

Structuring Techniques for Constraint Satisfaction Problems

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 418-422.

© 1997 International Joint Conferences on Artificial Intelligence

Abstract

We present a structuring method for discrete constraint satisfaction problems (CSPs). It takes advantage of interchangeabilities to represent sets of equivalent values by meta-values and thus obtain more compact representations. Strongly related variables are clustered into meta-variables to create occurrences of interchangeabilities. By iterative application, a CSP can be transformed into an hierarchy of equivalent CSPs, where each problem is significantly simpler than the original one. This structure is particularly advantageous when a large set of possible solutions must be inspected.

  1. [Ciarlet et a/. , 1994] P. Ciarlet, F. Lamur, and B.F. Smith. On the influence of the partitioning schemes on the efficiency of overlapping domain decomposition methods. Technical Report 94-23806, UCLA Com- putitional and Applied Mathematics, Los Angeles, CA 90024-1555, 1994.
  2. [Dechter and Meiri, 1994] R. Dechter and I. Meiri. Ex- perimental evaluation of preprocessing algorithms for constraint satisfaction problems. Artificial Intelli- gence, 68:211-241 , 1994.
  3. [Dechter and Pearl , 1989] Rina Dechter and Judea Pearl. Tree Clustering for Con- straint Networks. Artificial Intelligence, 38:353-366 , 1989.
  4. [Fiedler, 1973] M. Fiedler. graphs. Czechoslovak (98) :298-305, 1973. Algebraic connectivity of Mathematical Journal, 23 [Freuder, 1991]
  5. Eugene C . Freuder. Eliminating Inter- changeable Values in Constraint Satisfaction Prob- lems. In Proc. of AAAI-91 , pages 227-233, Anaheim, CA, 1991.
  6. [Freuder, 1992] Eugene C. Freuder. Constraint solving techniques. In E. Tyngu B. Mayoh and J. Penjaen, ed- itors, Constraint Programming of series F: Computer and Sytems Sciences, pages 51-74 . NATO ASI Series, 1992.
  7. [Hogg, 1996] T. Hogg. Refining the phase transition in combinatorical search. Artificial Intelligence, 81:127- 154, 1996.
  8. [Hubbe and Freuder, 1992] P.D. Hubbe and E.C. Freuder. An efficient Cross Product Representation of the Constraint Satisfaction Search Space. In Proc. of AAAI-92, pages 421-427, San Jose, CA , 1992.
  9. [Knuth, 1975] D. E. Knuth . Estimating the efficiency of backtrack programs. Mathematics of Computations, 29 :121-136, 1975.
  10. [MacGregor, 1978] R. M. MacGregor. On Partitioning a Graph . PhD thesis, University of California, Berkeley, 1978.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards