Decompositions of All Different, Global Cardinality and Related Constraints
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 419-423.
Abstract
We show that some common and important global constraints like ALLDIFFERENT and GCC can be decomposed into simple arithmetic constraints on which we achieve bound or range consistency, and in some cases even greater pruning. These decompositions can be easily added to new solvers. They also provide other constraints with access to the state of the propagator by sharing variables. Such sharing can be used to improve propagation between constraints. We report experiments with our decomposition in a pseudo-Boolean solver. Christian Bessiere, George Katsirelos, Nina Narodytska, Claude-Guy Quimper, Toby Walsh
@inproceedings{ijcai2009p77,
title = {Decompositions of All Different, Global Cardinality and Related Constraints},
author = {Bessiere, Christian and Katsirelos, George and Narodytska, Nina and Quimper, Claude-Guy and Walsh, Toby},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {419--423},
year = {2009},
url = {https://ijcai.org/proceedings/2009/77},
}
TY - CPAPER TI - Decompositions of All Different, Global Cardinality and Related Constraints AU - Bessiere, Christian AU - Katsirelos, George AU - Narodytska, Nina AU - Quimper, Claude-Guy AU - Walsh, Toby T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 419 EP - 423 UR - https://ijcai.org/proceedings/2009/77 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
