Information Technology Reference
In-Depth Information
We finish this section with a brief discussion of the expected eciency gain
of this technique over plain SBDD. With SBDD, the cost at each node
of
determining dominance is potentially exponential: for each completed subtree,
we must determine whether or not it is possible to map the set of literals cor-
responding to the root of that subtree into the set of literals at
N
.Bestknown
algorithms for this run in moderately exponential time (that is,
O
(
e
n
c
)where
c<
1and
n
is the number of points that the group is acting on: namely
N
,the
sum of the domain sizes). In our hybrid GE-tree and SBDD construction, the
selection of a collection of orbit representatives for the down-edges for a node is
done in low-degree polynomial time: there is a proof in [10] that the time is no
worse than
O
˜(
n
|χ|
4
), but the actual bound is lower than this. We then perform
SBDD on a reduced number of possible nodes, and with a smaller group.
5
Experiments
In [10] we showed that, for many CSPs, the cost of reformulating the problem
into one with only value symmetry is clearly outweighed by the gains of the GE-
tree construction, which is a polynomial-time method. In this paper we address
the more standard question of CSPs with both value and variable symmetries.
We take a highly symmetric CSP with known solutions, and compare symmetry
breaking combinations.
The queens graph is a graph with
2
nodes corresponding to squares of a
chessboard. There is an edge between nodes iff they are on the same row, column,
or diagonal, i.e. if two queens on those squares would attack each other in the
absence of any intervening pieces. The colouring problem is to colour the queens
graph with
n
colours. If possible, this corresponds to a set of
n
solutions to the
n
queens problem, forming a disjoint partition of the squares of the chessboard.
The problem is described by Martin Gardner. There is a construction for
n
congruent to 1 or 5 modulo 6, i.e. where
n
is not divisible by either 2 or 3. Other
cases are settled on a case by case basis. Our CSP model has the cells of an
n × n
array as variables, each having domain 1
...n
. The variable symmetries
are those of a square (the dihedral group of order 8). The value symmetries are
the
n
! permutations of the domain values (the symmetric group of degree
n
).
Our symmetry breaking approaches (using
n
-ECL
i
PS
e
)are:
GAP
-
SBDD only;
-
GE-tree construction for the value symmetries, with SBDD only used to
check the symmetric equivalence of solutions (GEtree+iso);
-
GE-tree construction for the value symmetries, with SBDD - on the full
symmetry group for the CSP - at each node (GEtree+SBDDfull);
-
GE-tree construction for the value symmetries, with SBDD - on the sym-
metry group for the variables - at each node (GEtree+SBDDval).
-ECL
i
PS
e
cpu times for a range of values for
n
. It seems
clear that GE-tree combined with full SBDD is competitive with SBDD only. It
also seems clear that only using SBDD (or any other isomorph rejection method)
Table 1 gives the
GAP
Search WWH ::
Custom Search