Abstract
Constraint satisfaction problems (CSPs) have a rich history in Artificial Intelligence and have become one of the most versatile mechanisms for representing complex relationships in real life problems. A CSP’s variables and constraints determine its primal constraint network. For every primal representation, there is an equivalent dual representation where the primal constraints are the dual variables, and the dual constraints are compatibility constraints on the primal variables shared between the primal constraints [1]. In this paper, we compare the performance of local search in solving Constraint Satisfaction Problems using the primal constraint graph versus the dual constraint graph.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
S. Nagarajan, On Dual Encodings for Constraint Satisfaction, Ph.D. thesis, University of Regina, 2001.
E. Tsang, Foundation of Constraint Satisfaction, Academic Press, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huang, M., Liu, Z., Goodwin, S.D. (2003). Dueling CSP Representations: Local Search in the Primal versus Dual Constraint Graph. In: Xiang, Y., Chaib-draa, B. (eds) Advances in Artificial Intelligence. Canadian AI 2003. Lecture Notes in Computer Science, vol 2671. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44886-1_61
Download citation
DOI: https://doi.org/10.1007/3-540-44886-1_61
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40300-5
Online ISBN: 978-3-540-44886-0
eBook Packages: Springer Book Archive