Publication
Exploiting single-cycle symmetries in branch-and-prune algorithms
Conference Article
Conference
International Conference on Principles and Practice of Constraint Programming (CP)
Edition
13th
Pages
864-871
Doc link
http://dx.doi.org/10.1007/978-3-540-74970-7_65
File
Abstract
As a first attempt to exploit symmetries in continuous con-
straint problems, we focus on permutations of the variables consisting of
one single cycle. We propose a procedure that takes advantage of these
symmetries by interacting with a Branch-and-Prune algorithm without
interfering with it. A key concept in this procedure are the classes of
symmetric boxes formed by bisecting a n-dimensional cube at the same
point in all dimensions at the same time. We quantify these classes as a
function of n. Moreover, we propose a simple algorithm to generate the
representatives of all these classes for any number of variables at very
high rates. A problem example from the chemical field and a kinematics
solver are used to show the performance of the approach in practice.
Categories
automation, robot kinematics.
Scientific reference
V. Ruiz de Angulo and C. Torras. Exploiting single-cycle symmetries in branch-and-prune algorithms, 13th International Conference on Principles and Practice of Constraint Programming, 2007, Providence, Estats Units d'Amèrica, in Principles and Practice of Constraint Programming - CP 2007, Vol 4741 of Lecture Notes in Computer Science, pp. 864-871, 2007, Springer Verlag, Berlin, Alemanya.
Follow us!