Constraint Satisfaction Problems (CSPs) appear in many real-life applications such as scheduling, resource allocation, timetabling, vehicle routing, frequency allocation, etc. Most CSPs can be naturally and efficiently modelled using non-binary (or n-ary) constraints that may involve an arbitrary number of variables. It is well known that any non-binary CSP can be converted into an equivalent binary one. The most well-known translations are the dual encoding [Dechter PearlDechter Pearl1989] and the hidden variable encoding [Rossi, Petrie, DharRossi et al.1990]. The ability to translate any non-binary CSP into binary has been often used in the past as a justification for restricting attention to binary CSPs. Implicitly, the assumption had been that when faced with a non-binary CSP we can simply convert it into a binary one, and then apply well-known generic techniques for solving the binary equivalent. In this paper we will show that this assumption is flawed because generic techniques for binary CSPs are not suitable for binary encodings of non-binary problems.
In the past few years, there have been theoretical and empirical studies on the efficiency of binary encodings and comparisons between binary encodings and the non-binary representation [Bacchus van BeekBacchus van Beek1998,Stergiou WalshStergiou Walsh1999,Mamoulis StergiouMamoulis Stergiou2001,SmithSmith2002,Bacchus, Chen, van Beek, WalshBacchus et al.2002]. Theoretical results have showed that converting non-binary CSPs into binary equivalents is a potentially efficient way to solve certain classes of non-binary problems. However, in the (limited) empirical studies there are very few cases where this appears to be true, with Conway's ``game of Life'' [SmithSmith2002] being the most notable exception. There are various reasons for this. In many cases, the extensive space requirements of the binary encodings make them infeasible. Also, in many non-binary problems we can utilize efficient specialized propagators for certain constraints, such as the algorithm developed by Régin Regin94 for the all-different constraint. Converting such constraints into binary is clearly impractical. Another reason, which has been overlooked, is that most (if not all) experimental studies use well-known generic local consistency and search algorithms in the encodings. In this way they fail to exploit the structure of the constraints in the encodings, ending up with inefficient algorithms. To make the binary encodings a realistic choice of modelling and solving non-binary CSPs, we need algorithms that can utilize their structural properties. Finally, it is important to point out that the use of a binary encoding does not necessarily mean that we have to convert all the non-binary constraints in a problem into binary, as it is commonly perceived. If we are selective in the constraints we encode, based on properties such as arity and tightness, then we can get efficient hybrid models.
To address these issues, we show that the use of specialized arc consistency and search algorithms for binary encodings of non-binary CSPs can lead to efficient models. We consider three encodings; the dual, the hidden variable, and the double encoding. The latter, which is basically the conjunction of the other two encodings, has received little attention but may well turn out to be the most significant in practice. The aim of this study is twofold. First, to present efficient algorithms for the binary encodings and analyze them theoretically and experimentally. Second, and more importantly, to investigate if and when the use of such algorithms can help solve non-binary problems efficiently. Towards these aims, we make the following contributions:
This paper is structured as follows. In Section 2 we give the necessary definitions and background. In Section 3 we describe a specialized arc consistency algorithm for the hidden variable encoding. We also demonstrate that all the extensions of forward checking to non-binary CSPs can be emulated by binary forward checking algorithms that run in the hidden variable encoding. In Section 4 we explain how the complexity of arc consistency in the dual encoding can be improved and describe a specialized arc consistency algorithm. Section 5 discusses algorithms for the double encoding. In Section 6 we present experimental results on random and structured problems that demonstrate the usefulness of the proposed algorithms. We also draw some conclusions regarding the applicability of the encodings, based on theoretical and experimental results. Section 7 discusses related work. Finally, in Section 8 we conclude.
Nikolaos Samaras 2005-11-09