---
title: "Symmetry Breaking via LexLeader Feasibility Checkers"
authors:
  - "Justin Yip"
  - "Pascal Van Hentenryck"
doi: "10.5591/978-1-57735-516-8/IJCAI11-121"
url: "https://ijcai.org/proceedings/2011/121"
pdf: "https://ijcai.org/proceedings/2011/0121.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "687-691"
track: ""
keywords:
---

# Symmetry Breaking via LexLeader Feasibility Checkers

Justin Yip, Pascal Van Hentenryck

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 687-691. DOI: [10.5591/978-1-57735-516-8/IJCAI11-121](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-121)

## Abstract

This paper considers matrix models, a class of CSPs which generally exhibit significant 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 efficiently 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 significant performance gains, when jointly used with DoubleLex or SnakeLex.