Breaking symmetries in all different problems
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 272-276.
Abstract
Adding symmetry breaking constraints is one of the oldest ways of breaking variable symmetries for CSPs. For instance, it is well known that all the symmetries for the pigeon hole problem can be removed by ordering the variables. We have generalized this result to all CSPs where the variables are subject to an all different constraint. In such case it is possible to remove all variable symmetries with a partial ordering of the variables. We show how this partial ordering can be automatically computed using computational group theory (CGT). We further show that partial orders can be safely used together with the GE-tree method of [Roney-Dougal et al., 2004]. Experiments show the efficiency of our method.
@inproceedings{ijcai2005p150,
title = {Breaking symmetries in all different problems},
author = {Puget, Jean-Francois},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {272--276},
year = {2005},
url = {https://ijcai.org/proceedings/2005/150},
}
TY - CPAPER TI - Breaking symmetries in all different problems AU - Puget, Jean-Francois T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 272 EP - 276 UR - https://ijcai.org/proceedings/2005/150 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
