Information Technology Reference
In-Depth Information
search for solutions proceeds as before, but with fast permutation group algo-
rithms supplying information that restricts search to symmetrically inequivalent
nodes. Both SBDS and SBDD have been successfully implemented in this way
[6,7] using
-ECL
i
PS
e
, an interface between the ECL
i
PS
e
[8] constraint logic
programming system and the
GAP
[9] computational group theory system.
An even more recent advance has been the theory of GE-trees [10].
The construction and traversal of a GE-tree breaks all symmetries in any
CSP. In the special - but common - case that the CSP has only value sym-
metries (for example graph colouring problems, where the colours are distinct
but interchangeable) a GE-tree can be constructed in low-degree polynomial
time. GE-trees provide both a useful analytic framework for comparing symme-
try breaking methods, and, for value symmetries, a practical method for ecient
search.
In this paper we describe initial results, both theoretical and practical, con-
cerning the integration of GE-tree construction with SBDD. We combine heuris-
tic AI search with mathematical structures and algorithms in order to extend
and enhance existing - mainly pure AI - techniques.
In the remainder of this paper we provide a formal framework for CSPs,
variable and value symmetries and GE-trees. In the following section, we describe
SBDD and make some observations about variations of this algorithm. In the
next two sections we identify and discuss a mathematically special, but common,
situation in which we can uncouple variable and value symmetries. We follow this
with preliminary results for a range of symmetry breaking approaches involving
various combinations of SBDD and GE-tree methods.
GAP
1.1 CSPs and Symmetries
Definition 1.
ACSP
L
is a set of constraints
C
acting on a finite set of vari-
ables
∆
:=
{A
1
,A
2
,...,A
n
}
, each of which has finite domain of possible values
D
i
:=
D
(
A
i
)
⊆ Λ
.A
solution
to
L
is an instantiation of all of the variables in
∆
such that all of the constraints in
are satisfied.
Constraint logic programming systems such as ECL
i
PS
e
model CSPs using
constraints over finite domains. The usual search method is depth-first, with
values assigned to variables at choice points. After each assignment a partial
consistency test is applied: domain values that are found to be inconsistent are
deleted, so that a smaller search tree is produced. Backtrack search is itself a con-
sistency technique, since any inconsistency in a current partial assignment (the
current set of choice points) will induce a backtrack. Other techniques include
forward-checking, conflict-directed backjumping and look-ahead.
Statements of the form (
var
=
val
) are called
literals
, so a partial assignment
is a conjunction of literals. We denote the set of all literals by
χ
, and generally
denote variables in Roman capitals and values by lower case Greek letters. We
denote “constrained to be equal” by # =.
C
Definition 2.
Given a CSP
L
, with a set of constraints
, and a set of literals
χ
,a
symmetry
of
L
is a bijection
f
:
χ → χ
such that a full assignment
A
of
L
satisfies all constraints in
C
C
if and only if
f
(
A
)
does.
Search WWH ::
Custom Search