Structural Symmetry Breaking
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 298-302.
Abstract
Symmetry breaking has been shown to be an important method to speed up the search in constraint satisfaction problems that contain symmetry. When breaking symmetry by dominance detection, a computationally efficient symmetry breaking scheme can be achieved if we can solve the dominance detection problem in polynomial time. We study the complexity of dominance detection when value and variable symmetry appear simultaneously in constraint satisfaction problems (CSPs) with single-valued variables and set-CSPs. We devise an efficient dominance detection algorithm for CSPs with single-valued variables that yields symmetry-free search trees and that is based on the abstraction to the actual, intuitive structure of a symmetric CSP.
@inproceedings{ijcai2005p131,
title = {Structural Symmetry Breaking},
author = {Sellmann, Meinolf and Van Hentenryck, Pascal},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {298--302},
year = {2005},
url = {https://ijcai.org/proceedings/2005/131},
}
TY - CPAPER TI - Structural Symmetry Breaking AU - Sellmann, Meinolf AU - Van Hentenryck, Pascal T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 298 EP - 302 UR - https://ijcai.org/proceedings/2005/131 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
