×

Symmetry breaking. (English) Zbl 1067.68631

Walsh, Toby (ed.), Principles and practice of constraint programming - CP 2001. 7th international conference, Paphos, Cyprus, November 26 – December 1, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42863-1). Lect. Notes Comput. Sci. 2239, 93-107 (2001).
Summary: Symmetries in constraint satisfaction or combinatorial optimization problems can cause considerable difficulties for exact solvers. One way to overcome the problem is to employ sophisticated models with no or at least less symmetries. However, this often requires a lot of experience from the user who is carrying out the modeling. Moreover, some problems even contain inherent symmetries that cannot be broken by remodeling. We present an approach that detects symmetric choice points during the search. It enables the user to find solutions for complex problems with minimal effort spent on modeling.
For the entire collection see [Zbl 0984.00059].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: Link