An Efficient Way of Breaking Value Symmetries

Jean-François PugetAAAI 2006

Abstract

Constraint Satisfaction Problems (CSPs) often exhibit symmetries that lead to redundant search efforts. While independent methods for breaking variable and value symmetries exist, combining them efficiently remains a challenge. This paper introduces a method that leverages lexicographical (lex) and element constraints to break both types of symmetries simultaneously. We also propose a new global constraint for scenarios with a large number of interchangeable values. Evaluation on classic benchmarks shows significant speedups, reducing backtracks and solving previously intractable instances.

Introduction

In Constraint Programming (CP), symmetries are transformations that map solutions to other solutions, effectively duplicating the search space. For instance, in map coloring, permuting the set of available colors results in symmetric solutions. These symmetries can be categorized into variable symmetries (permutations of variables) and value symmetries (permutations of values).

The primary difficulty lies in the interaction between these two types. Breaking one often interferes with the other, leading to "un-broken" symmetries. Existing methods like SBDS or SBDD modify the search engine, which can be complex to implement. This work seeks a more integrated approach using standard constraints.

Methodology

The proposed approach consists of two primary components:

Lex + Element Constraints

The core insight is that a value symmetry $\theta$ can be modeled as an array lookup, represented in CP as an element constraint: $x^\theta = A_\theta[x]$. By incorporating this into the "Lex Leader" framework, we can enforce that a solution $V$ must be lexicographically smaller than or equal to its symmetric variant $A_\theta[V^\sigma]$, where $\sigma$ is a variable symmetry. This allows for the simultaneous breaking of both symmetry types using standard modeling primitives.

Global Constraint for Interchangeable Values

When dealing with a large number of value symmetries—such as when all values are interchangeable—adding individual constraints for every permutation becomes computationally expensive. To address this, we developed a global constraint and a forward-checking algorithm. This algorithm prunes values that would lead to non-lexicographically minimal solutions, effectively extending the "GE-tree" approach to handle variable symmetries.

Experimental Evaluation

The effectiveness of the method was tested on three highly symmetric benchmarks:

  1. Graceful Graphs: Labeling graph components such that edge labels are unique.
  2. $n \times n$ Queens Coloring: A chessboard coloring problem with no monochromatic conflicts on rows, columns, or diagonals.
  3. Dodecahedron Graph Coloring: A vertex coloring problem involving 120 variable symmetries.

Results and Discussion

The experimental results demonstrate that the proposed method significantly outperforms previous state-of-the-art techniques in both execution time and search reduction.

Comparison of symmetry breaking methods on Graceful Graph benchmarks.

As shown in the Graceful Graphs results, the new method (labeled LEX) achieved a massive speedup on the $K4 \times K3$ problem, finding solutions in 293 seconds compared to 38,000 seconds for earlier methods.

Performance comparison on Dodecahedron Graph Coloring.

In the Dodecahedron Coloring task, the method was substantially faster than the GAP-SBDD approach. For instance, with 4 colors, the execution time dropped from 879 seconds to just over 2 seconds. The method also revealed that previous studies had missed half of the dodecahedron's symmetries (the inversions), which were handled seamlessly here.

Conclusion

This work provides a robust and efficient framework for breaking combined variable and value symmetries. By treating value permutations as data within a lexicographical framework, we achieve completeness without modifying the search engine. Future work will focus on scaling the method to even larger symmetry groups and integrating it with automated symmetry detection tools.

Summary updated

BibTeX
@inproceedings{puget2006efficient,
  author = {Jean-François Puget},
  title = {{An Efficient Way of Breaking Value Symmetries}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure