Arathi Ramani and Igor L. Markov, EECS Department, University of Michigan
GSymEx is a tool for automatically detecting and extracting symmetries in generic constraint programming problems. It is part of a larger system for the structure-aware compilation of CSPs. The system includes a high-level specification language in which CSPs can be specified, a parser, symmetry detection component and a compiler that translates constraints into instances of Boolean Satisfiability (SAT) and 0-1 Integer Linear Programming (ILP). It also includes the capability to add symmetry breaking predicates (SBPs) to the reduced SAT or 0-1 ILP instances. The symmetry extraction component, GSymEx, can be used independently to automatically detect symmetries in constraints that can be used by other constraints solvers or algorithms. The goal of GSymEx is to provide efficient, automatic symmetry detection capability for a wide range of CSPs. Symmetries are detected by graph automorphism - a graph is built from the constraints and symmetries in the graph are detected using the graph automorphism program Saucy. GSymEx generalizes the symmetry detection tool Shatter. For more information on the GSymEx input format, and for code or binaries, please contact us by email at: r a m a n i a {at} e e c s {dot} u m i c h {dot} e d u