Article: Binary Encodings of Non-binary Constraint Satisfaction Problems: Algorithms and Experimental Results

Skip to first unread message

Nov 18, 2005, 7:31:18 PM11/18/05
JAIR is pleased to announce the publication of the following article:

Samaras, N. and Stergiou, K. (2005)
"Binary Encodings of Non-binary Constraint Satisfaction Problems: Algorithms and Experimental Results",
Volume 24, pages 641-684.

For quick access via your WWW browser, use this URL:

A non-binary Constraint Satisfaction Problem (CSP) can be
solved directly using extended versions of binary techniques.
Alternatively, the non-binary problem can be translated into an
equivalent binary one. In this case, it is generally accepted that
the translated problem can be solved by applying well-established
techniques for binary CSPs. In this paper we evaluate the
applicability of the latter approach. We demonstrate that the use
of standard techniques for binary CSPs in the encodings of
non-binary problems is problematic and results in models that are
very rarely competitive with the non-binary representation. To
overcome this, we propose specialized arc consistency and search
algorithms for binary encodings, and we evaluate them
theoretically and empirically. We consider three binary
representations; the hidden variable encoding, the dual encoding,
and the double encoding. Theoretical and empirical results show
that, for certain classes of non-binary constraints, binary
encodings are a competitive option, and in many cases, a better
one than the non-binary representation.

The article is available via:

-- (also see

-- World Wide Web: The URL for our World Wide Web server is
For direct access to this article and related files try:

-- Anonymous FTP from Carnegie-Mellon University (USA):
The compressed PostScript file is named

For more information about JAIR, visit our WWW or FTP sites, or

Steven Minton
JAIR Managing Editor

Reply all
Reply to author
0 new messages