- ... node
^{1}
- In the paper by Bacchus et
al. bcvbw02 the cost of applying a variable ordering
heuristic at each node is also taken into account. When we
theoretically compare search algorithms in this paper we assume
that they use the same variable ordering, so we do not take this
cost into account.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

- ...#tex2html_wrap_inline1728#
^{2}
- We
assume, without loss of generality, that the algorithm looks for
supports by checking the tuples in lexicographic order.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

- ... it
^{3}
- Note that dual variables
that are already in the stack are never added to it. In this
sense, the stack is implemented as a set.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

- ... variable
^{4}
- ``One
pass'' means that each constraint is processed only once.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

- ...
AC-2001
^{5}
- Note that we can construct similar examples for
any generic AC algorithm.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

- ... classes
^{6}
- Puzzles
66-1010 correspond to square grids with no blank
squares.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

- ... encoding
^{7}
- This was verified by looking at the node visits
of the two algorithms.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

- ...
connected
^{8}
- Experiments showed that these are the minimum
additions that need to be made in order to get hard problems
without altering the structure of the problems too much.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

- ... MGAC
^{9}
- To
create the instances we varied the type of the constraints and the
values of parameters and until non-trivial problems were
generated. We consider as trivial problems that are arc
inconsistent or solvable with no backtracking.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

- ...
encoding
^{10}
- Although the title of Smith's paper
smith02 refers to the DE, the model of the
``still-life'' problem used is based on the double encoding.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.