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.

Nikolaos Samaras
2005-11-09