Research Publications

We present a general method for dynamically posting symmetry breaking constraints during search. The basic idea is very simple. Given any set of symmetry breaking constraints, if during search a symmetry of one of these constraints is entailed and this is consistent with previously posted symmetry breaking constraints, then we post this constraint. The method works best with problems where symmetry can be broken with a small number of symmetry breaking constraints. We illustrate the method with two examples where a polynomial number of symmetry breaking constraints break an exponential number of symmetries. Like existing static meth- ods for symmetry breaking, this symmetry breaking method benefits from fast and effective constraint propagation. In addition, like exist- ing dynamic methods for symmetry breaking, this symmetry break- ing methods does not conflict with the branching heuristic. Initial experimental results appear promising.