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

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

2011-09-26

arxiv.org/abs/1109.5714v1

Journal Of Artificial Intelligence Research, Volume 24, pages 641-684, 2005

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.1776

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.

Affiliated with

Also associated with

No associations

Rating

Binary Encodings of Non-binary Constraint Satisfaction Problems: Algorithms and Experimental Results does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Binary Encodings of Non-binary Constraint Satisfaction Problems: Algorithms and Experimental Results, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary Encodings of Non-binary Constraint Satisfaction Problems: Algorithms and Experimental Results will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-61555