Boosting SBDS for Partial Symmetry Breaking in Constraint Programming

Authors

  • Jimmy Lee The Chinese University of Hong Kong
  • Zichen Zhu The Chinese University of Hong Kong

DOI:

https://doi.org/10.1609/aaai.v28i1.9112

Abstract

The paper proposes a dynamic method, Recursive SBDS(ReSBDS), for efficient partial symmetry breaking. Wefirst demonstrate how (partial) Symmetry BreakingDuring Search (SBDS) misses important pruning opportunitieswhen given only a subset of symmetries tobreak. The investigation pinpoints the culprit and in turnsuggests rectification. The main idea is to add extra conditionalconstraints during search recursively to prunealso symmetric nodes of some pruned subtrees. Thus,ReSBDS can break extra symmetry compositions, butis carefully designed to break only the ones that areeasy to identify and inexpensive to break. We presenttheorems to guarantee the soundness and terminationof our approach, and compare our method with popularstatic and dynamic methods. When the variable (value)heuristic is static, ReSBDS is also complete in eliminatingall interchangeable variables (values) given only thegenerator symmetries. Extensive experimentations confirmthe efficiency of ReSBDS, when compared againststate of the art methods.

Downloads

Published

2014-06-21

How to Cite

Lee, J., & Zhu, Z. (2014). Boosting SBDS for Partial Symmetry Breaking in Constraint Programming. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.9112

Issue

Section

Main Track: Search and Constraint Satisfaction