Breaking More Composition Symmetries Using Search Heuristics

Authors

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

DOI:

https://doi.org/10.1609/aaai.v30i1.10438

Keywords:

Dynamic symmetry breaking, Partial symmetry breaking, Search heuristics

Abstract

The pruning power of partial symmetry breaking depends on the given subset of symmetries to break as well as the interactions among symmetry breaking constraints. In the context of Partial Symmetry Breaking During Search (ParSBDS), the search order determines the set of symmetry breaking constraints to add and thus also makes an impact on node and solution pruning. In this paper, we give the first formal characterization of the pruning behavior of ParSBDS and its improved variants. Introducing the notion of Dominance-Completeness (DC-ness), we show that ParSBDS and variants eliminate the symmetry group of the given subset of symmetries if the resultant search tree is DC, and give an example scenario. Unfortunately, building a DC tree is not always possible. We propose two search heuristics with the aim of having more nodes dominated and thus also pruned during search. Extensive experimentation demonstrates how the proposed heuristics and their combination can drastically reduce the solution set size, search space and runtime when compared against the state-of-the-art static and dynamic symmetry breaking methods.

Downloads

Published

2016-03-05

How to Cite

Lee, J., & Zhu, Z. (2016). Breaking More Composition Symmetries Using Search Heuristics. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10438

Issue

Section

Technical Papers: Search and Constraint Satisfaction