Proceedings

Reducing Checks and Revisions in Coarse-grained MAC Algorithms

Download BibTeX Cite

Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 236-240.

© 2005 International Joint Conferences on Artificial Intelligence

Abstract

Arc consistency algorithms are widely used to prune the search space of Constraint Satisfaction Problems (CSPs). Coarse-grained arc consistency algorithms like AC-3, AC-3d and AC-2001 are efficient when it comes to transforming a CSP to its arc-consistent equivalent. These algorithms repeatedly carry out revisions. Revisions require support checks for identifying and deleting all unsupported values from the domain of a variable. In revisions for difficult problems most values have some support. Indeed, most revisions are ineffective, i.e. they cannot delete any value and consume a lot of checks and time. We propose two solutions to overcome these problems. First we introduce the notion of a Support Condition (SC) which guarantees that a value has some support. SCs reduce support checks while maintaining arc consistency during search. Second we introduce the notion of a Revision Condition (RC) which guarantees that all values have support. A RC avoids a candidate revision and queue maintenance overhead. For random problems, SCs reduce the checks required by MAC-3 (MAC-2001) up to 90% (72%). RCs avoid at least 50% of the total revisions. Combining the two results in reducing 50% of the solution time.

  1. [Achlioptas et al., 2000] Dimitri Achlioptas, Carla Gomes, Henry Kautz, and Bart Selman. Generating satisfiable problem instances. In AAAI/IAAI, pages 256-261, 2000.
  2. [Bessière and Cordier, 1993] C. Bessière and M. Cordier. Arc-consistency and arc-consistency again. In Proceed- ings of the 11 th National Conference on Artificial Intelli- gence (AAAI'93), Washington, DC, 1993. [Bessière and Régin, 2001]
  3. C. Bessière and J.-C. Régin. Re- fining the basic constraint propagation algorithm. In Pro- ceedings of the Seventeenth International Joint Confer- ence on Artificial Intelligence (IJCAI'2001), pages 309- 315, 2001. IJCAI
  4. [Boussemart et al., 2004] F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais. Support inference for generic filtering. In Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming, 2004.
  5. [Gent et al., 2001] I.P. Gent, E. MacIntyre, P. Prosser, B. Smith, and T. Walsh. Random constraint satisfaction: Flaws and structure. Journal of Constraints, 6(4):345-372, 2001.
  6. [Mackworth, 1977] A.K. Mackworth. Consistency in net- works of relations. Artificial Intelligence, 8:99-118, 1977.
  7. [McGregor, 1979] J.J. McGregor. Relational consistency al- gorithms and their application in finding subgraph and graph isomorphisms. Information Sciences, 19:229-250, 1979.
  8. [Mehta and van Dongen, 2004] D. Mehta and M.R.C. van Dongen. Two new lightweight arc consistency algorithms. In M.R.C. van Dongen, editor, Proceedings of the First In- ternational Workshop on Constraint Propagation and Im- plementation (CPAI'2004), pages 109-123, 2004.
  9. [Mohr and Henderson, 1986] R. Mohr and T. Henderson. Arc and path consistency revisited. Artificial Intelligence, 28:225-233, 1986.
  10. [Sabin and Freuder, 1994] D. Sabin and E.C. Freuder. Con- tradicting conventional wisdom in constraint satisfaction. In A.G. Cohn, editor, Proceedings of the Eleventh Eu- ropean Conference on Artificial Intelligence (ECAI'94), pages 125-129.
  11. [van Dongen and Mehta, 2004] M.R.C. van Dongen and D. Mehta. Queue representation for arc consistency algo- rithms. In L. McGinty and B. B.Crean, editors, Proceed- ings of the Fifteenth Irish Conference on Artificial Intelli- gence and Cognitive Science, pages 334-343, 2004.
  12. [van Dongen, 2004] M.R.C. van Dongen. Saving support- checks does not always save time. Artificial Intelligence Review, 21(3-4):317-334, 2004.
  13. [Wallace and Freuder, 1992] R.J. Wallace and E.C. Freuder. Ordering heuristics for arc consistency algorithms. In Pro- ceedings of the Ninth Canadian Conference on Artificial Intelligence, pages 163-169, Vancouver, B.C., 1992.

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

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