Abstract
This paper considers matrix models, a class of CSPs which generally exhibit signi?cant symmetries. It proposed the idea of LexLeader feasibility checkers that verify, during search, whether the current partial assignment can be extended into a canonical solution. The feasibility checkers are based on a novel result by [Katsirelos et al., 2010] on how to check ef?ciently whether a solution is canonical. The paper generalizes this result to partial assignments, various variable orderings, and value symmetries. Empirical results on 5 standard benchmarks shows that feasibility checkers may bring signi?cant performance gains, when jointly used with D OUBLE L EX or S NAKE L EX.