breaking value symmetries in matrix models using channeling constraints
Multi-aspect Assignment Problems (MAPs) can be naturally formulated into various matrix models of Constraint Satisfaction Problems (CSPs), which can contain both variable and value symmetries, using different viewpoints. While variable symmetry breaking constraints can be expressed relatively easily and executed efficiently by enforcing lexicographic ordering, value symmetry breaking constraints are difficult to formulate. We show when value symmetries in one viewpoint correspond to variable symmetries in another, and when symmetry breaking constraints in two viewpoints are consistent. Our results allow tackling value symmetries efficiently using additional viewpoints and channeling constraints. Experiments on the social golfer problem and a variant of the quasigroup existence problem confirm the benefits of our proposal against conventional methods.
csp symmetry breaking