Information Technology Reference
In-Depth Information
A symmetry group
G
for a CSP can quickly be tested for complementary
valuesymmetry.Thereareseveraldifferent ways of doing so, depending on
how
G
has been constructed. If
G
has been input as a collection of pure value
symmetries and a collection of pure variable symmetries then we always have
complementary variable symmetry, and the construction of the subgroup of value
symmetries and the group of variable symmetries is immediate.
So suppose that
G
has not been input in this form, and that we have
G
and
a list of the domains for each variable. If the domains are not equal, and we have
some value symmetries, then assume also that the bijections between each pair
of domains are given.
We first check that the subgroup of value symmetries forms a normal sub-
group of
G
, which can be done in time polynomial in
|χ|
. We then form the
Val
: this basically means that we divide out by the
subgroup of all value symmetries, and can also be done in polynomial time. If
the size of this quotient group is equal to the size of the group of variable sym-
metries, then the CSP has complementary variable symmetry, as it is clear that
the only permutation of the set of all literals which lies in both the group of
variable symmetries and the group of value symmetries is the identity map.
If the variables of the CSP share a common domain, the fastest way to find
the group of variable symmetries (if this is not immediately clear from the way
in which
G
has been described) is to compute the pointwise stabiliser in
quotient group
of
G
by
G
G
of
each of the values. This can be done in low-degree polynomial time [11].
In the next section we describe a new algorithm for symmetry breaking which
is applicable to all CSPs with complementary variable symmetry.
4
SBDD on Complements
This approach can be summarized by saying that we construct a GE-tree for
the set of value symmetries, and then search this using SBDD. However, we do
not use SBDD on the full group, as this would involve also checking the value
symmetries once more, but instead carry out SBDD only on the subgroup of
variable symmetries.
In more detail, we proceed as follows. At each node
N
in the search tree we
start by applying the GE-tree algorithm for
G
Val
N
with a variable
X
to label
N
,say
α
1
,
α
2
,...,α
k
∈
and produce a short list of possible downedges from
Dom(
X
).
We now perform dominance detection on each of
(
X
=
α
i
), but in a
2-stage process separating out the variable mapping from the value mapping.
That is, using only
G
N∪
Var
is dominated by the
variables in any other node. Each time that we find dominance by a node
we check whether Var(
N
)
∪{X}
M
,
this implies that Var(
Mg
)
⊆
Var(
N∪{X}
). We therefore apply
g
to the literals
Val
in
M
, and check whether there is an element of
G
that can map the resulting
collection of literals to
N∪
(
X
=
α
i
)for1
≤ i ≤ k
, bearing in mind that
we now know precisely which literal in
Mg
must be mapped to each literal in
N∩
(
X
=
α
i
), since the value group fixes the variables occurring in each literal.
This latter query is therefore a low-degree polynomial time operation.
Search WWH ::
Custom Search