English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/127517
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:

Variable symmetry breaking in numerical constraint problems

AutorGoldsztejn, Alexandre; Jermann, Christophe; Ruiz de Angulo, Vicente; Torras, Carme
Palabras claveSymmetries
Variable symmetries
Numerical constraints
Constraint programming
Fecha de publicación2015
CitaciónArtificial Intelligence 229: 105-125 (2015)
ResumenSymmetry 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.
Versión del editorhttp://dx.doi.org/10.1016/j.artint.2015.08.006
Identificadoresissn: 0004-3702
e-issn: 1872-7921
Aparece en las colecciones: (IRII) Artículos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
constraint-problems.pdf714,16 kBAdobe PDFVista previa
Mostrar el registro completo

NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.