Advertisement
Published in:
2005 | OriginalPaper | Chapter
Breaking All Value Symmetries in Surjection Problems
Author : Jean-François Puget
Published in: Principles and Practice of Constraint Programming - CP 2005
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.