Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/84830

Variable symmetry breaking in numerical constraint problems
Goldsztejn, Alexandre; Jermann, Christophe; Ruiz de Angulo García, Vicente; Torras, Carme
Universitat Politècnica de Catalunya. Institut de Robòtica i Informàtica Industrial; Universitat Politècnica de Catalunya. KRD - Cinemàtica i Disseny de Robots; Universitat Politècnica de Catalunya. ROBiri - Grup de Robòtica de l'IRI
Symmetry breaking has been a hot topic of research in the past years, leading to many theoretical developments as well as strong scaling strategies for dealing with hard applications. Most of the research has however focused on discrete, combinatorial, problems, and only few considered also continuous, numerical, problems. While part of the theory applies in both contexts, numerical problems have specificities that make most of the technical developments inadequate. In this paper, we present the rlex constraints, partial symmetry-breaking inequalities corresponding to a relaxation of the famous lex constraints extensively studied in the discrete case. They allow (partially) breaking any variable symmetry and can be generated in polynomial time. Contrarily to lex constraints that are impractical in general (due to their overwhelming number) and inappropriate in the continuous context (due to their form), rlex constraints can be efficiently handled natively by numerical constraint solvers. Moreover, we demonstrate their pruning power on continuous domains is almost as strong as that of lex constraints, and they subsume several previous work on breaking specific symmetry classes for continuous problems. Their experimental behavior is assessed on a collection of standard numerical problems and the factors influencing their impact are studied. The results confirm rlex constraints are a dependable counterpart to lex constraints for numerical problems.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Robòtica
artificial intelligence
mathematical programming
symmetry
constraint programing
numerical constraint satisfaction problems
constraint satisfaction problems
symmetry breaking
variable symmetry breaking
Classificació INSPEC::Cybernetics::Artificial intelligence
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/submittedVersion
Artículo
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Goldsztejn, Alexandre; Jermann, Christophe; Ruiz de Angulo García, Vicente; Torras, Carme
Ulbrich, Stefan; Ruiz de Angulo García, Vicente; Asfour, Tamim; Torras, Carme; Dillmann, Rüdiger
Ulbrich, Stefan; Ruiz de Angulo García, Vicente; Torras, Carme; Asfour, Tamim; Dillmann, Rudiger
Ruiz de Angulo García, Vicente; Torras, Carme
Ruiz de Angulo García, Vicente; Torras, Carme