Breaking Symmetry for Knowledge Compilation

Constraint programming is a powerful paradigm for solving combinatorial problems. Diagnosis, planning, and product configuration, are example use-cases. While reasoning about the solution space of combinatorial problems is usually intractable, compilation methods are often used to pre-compute a representation that can answer queries in time that is polynomial in the representation size. Symmetry breaking constraints can be added to a combinatorial problem to eliminate symmetries and reduce the number of states to be explored. Finding compact representations is often the bottleneck of compilation methods. One approach that is sometimes used is partial compilation whereby a subset of the solutions of a set of constraints are compiled, e.g. those that are considered most important or most likely to be useful. In this paper we investigate if breaking symmetries always leads to a smaller compiled representation. We considered four compilers and four highly symmetrical problems. A reduction is observed in all the problems for the compilation size when we break symmetries, with top-down compilers seeing greater reduction.