Abstract
We define the Same and UsedBy constraints. UsedBy takes two sets of variables X and Z such that |X| ≥ |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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Beldiceanu, N., Katriel, I., Thiel, S.: Filtering algorithms for the Same and UsedBy constraints. Research Report MPI-I-2004-1-001, Max-Planck-Institut für Informatik, Saarbrücken, Germany (2004)
Gabow, H.N., Tarjan, R.E.: A Linear-Time Algorithm for a Special Case of Disjoint Set Union. Journal of Computer and System Sciences 30(2), 209–221 (1985)
Ford Jr., L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)
Katriel, I., Thiel, S.: Fast bound consistency for the global cardinality constraint. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 437–451. Springer, Heidelberg (2003)
Mehlhorn, K., Thiel, S.: Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 306–319. Springer, Heidelberg (2000)
Régin, J.-C.: A filtering algorithm for constraints of difference in CSPs. In: Proceedings of the 12th National Conference on Artificial Intelligence (AAAI 1994), pp. 362–367 (1994)
Régin, J.-C.: Generalized Arc-Consistency for Global Cardinality Constraint. In: Proceedings of the 13th National Conference on Artificial Intelligence (AAAI 1996), pp. 209–215 (1996)
Médecins sans Frontières, http://www.doctorswithoutborders.org/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beldiceanu, N., Katriel, I., Thiel, S. (2004). Filtering Algorithms for the Same Constraint. In: Régin, JC., Rueher, M. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2004. Lecture Notes in Computer Science, vol 3011. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24664-0_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-24664-0_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21836-4
Online ISBN: 978-3-540-24664-0
eBook Packages: Springer Book Archive