Hidden Variable Encoding

As theoretical results suggested, and empirical results confirmed, solving problems in the HVE using algorithms that only instantiate original variables is essentially analogous to solving the non-binary representation directly. All the commonly used algorithms for non-binary problems can be applied, with adjustments, to the HVE, and vice versa. When such algorithms are used, the HVE offers some (moderate) computational savings compared to the non-binary representation, especially in sparse problems. These savings are due to the ability of the AC algorithm in the HVE to detect inconsistencies earlier than the corresponding GAC algorithm in the non-binary representation. Therefore, we conjecture that the HVE is applicable in sparse non-binary problems where the constraints are extensionally specified. In other cases, the HVE is either less efficient in run times than the non-binary representation (e.g. dense problems), or building the HVE adds space overheads that are not justified by the marginal gains in search effort. Additionally, there is not enough empirical evidence to suggest that the essential difference between search algorithms for the HVE and the non-binary representation, i.e. the ability of the former to branch on dual variables, can make the HVE significantly more efficient in some class of problems. This, coupled with the fact that any benefits gained by instantiating dual variables can be maximized if the double encoding is used instead of the HVE, limits the applicability of such algorithms.