Treffer: Symmetry breaking revisited

Title:
Symmetry breaking revisited
Authors:
PUGET, Jean-Francois
Source:
Principles and practices of constraint programmingConstraints (Dordrecht). 10(1):23-46
Publisher Information:
Heidelberg: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 27 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Théorie programmation, Programming theory, Intelligence artificielle, Artificial intelligence, Résolution de problèmes, jeux, Problem solving, game playing, Arbre recherche, Search tree, Arbol investigación, Brisure symétrie, Symmetry breaking, Ruptura simetría, Résolution problème, Problem solving, Resolución problema, Satisfaction contrainte, Constraint satisfaction, Satisfaccion restricción, Plan bloc incomplet équilibré, Social golfer problem
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
ILOG, Gentilly, France
ISSN:
1383-7133
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=16518388
Rights:
Copyright 2005 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.16518388
Database:
PASCAL Archive

Weitere Informationen

Symmetries in constraint satisfaction problems (CSPs) are one of the difficulties that practitioners have to deal with. We present in this paper a new method based on the symmetries of decisions taken from the root of the search tree. This method can be seen as an improvement of the SBDD method presented by Focacci and Milano [7] and Fahle et al. [5]. We present a simple formalization of our method for which we prove correctness and completeness results. We show that our method is theoretically more efficient as the size of each no-good is smaller. This theoretical analysis is confirmed by thorough experimental evaluation on highly symmetrical real world problems. We are able to break all symmetries for problems with more than 1078 symmetries.