Filtering algorithms for the Same constraint

Beldiceanu, Nicolas; Katriel, Irit; Thiel, Sven; Régin, Jean-Charles; Rueher, Michel

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Filtering algorithms for the Same constraint

MPS-Authors

/persons/resource/persons44744

Katriel, Irit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45615

Thiel, Sven
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Beldiceanu, N., Katriel, I., & Thiel, S. (2004). Filtering algorithms for the Same constraint. In Integration of AI and OR techniques in constraint programming for combinatorial optimization problems: First International Conference, CPAIOR 2004 (pp. 65-79). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-291A-A

Abstract

We define the \Same\ and \UsedBy\ constraints. \UsedBy\ takes two sets of variables $X$ and $Z$ such that $|X|\ge |Z|$ and assigns values to them such that the multiset of values assigned to the variables in $Z$ is contained in the multiset of values assigned to the variables in $X$. \Same\ is the special case of \UsedBy\ in which $|X|=|Z|$. In this paper we show algorithms that achieve arc consistency and bound consistency for the \Same\ constraint and in its extended version we generalize them for the \UsedBy\ constraint.