Return to search

Symmetry Breaking Ordering Constraints

Many problems in business, industry, and academia can be modelled as constraint programs consisting of matrices of decision variables. Such “matrix models” often have symmetry. In particular, they often have row and column symmetry as the rows and columns can freely be permuted without affecting the satisfiability of assignments. Existing methods have difficulty in dealing with the super-exponential number of symmetries in a problem with row and column symmetry. We therefore propose some ordering constraints which can effectively break such symmetries. To use these constraints in practice, we develop some efficient linear time propagators. We demonstrate the effectiveness of these symmetry breaking ordering constraints on a wide range of problems. We also show how such ordering constraints can be used to deal with partial symmetries, as well as value symmetries.

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:uu-3991
Date January 2004
CreatorsKiziltan, Zeynep
PublisherUppsala universitet, Data- och systemvetenskap, Uppsala : Data- och systemvetenskap
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageEnglish
TypeDoctoral thesis, monograph, info:eu-repo/semantics/doctoralThesis, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.002 seconds