2005 | OriginalPaper | Buchkapitel
Breaking All Value Symmetries in Surjection Problems
verfasst von : Jean-François Puget
Erschienen in: Principles and Practice of Constraint Programming - CP 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose a surprisingly simple new way of breaking all value symmetries with constraints. Our method requires the addition of one variable per value of the problem plus a linear number of binary constraints. The set of constraints is automatically computed from the symmetries of the problem using computational group theory. Our method applies to problems where every value is taken by at least one variable. Such problems occur frequently in practice. Various experiments show that our method is extremely effective when compared to previously published methods.