Filtering algorithms for the same and UseBy constraints

• Autorzy: Beldiceanu N. , Katriel I. , Thiel S.
• Języki publikacji: EN

Abstrakty

EN

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. We show algorithms that achieve arc-consistency and bound-consistency for these constraints.

Słowa kluczowe

EN

arc-consistency; bound-consistency; constraint programming; filtering algorithm; global constraint; network flow; strongly connected component

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2006
• Tom: Vol. 16, no. 2
• Strony: 191--220
• Opis fizyczny: Bibliogr. 12 poz., rys., tab., wzory

Twórcy

autor

Beldiceanu N.

autor

Katriel I.

autor

Thiel S.

• LINA FRE CNRS 2729, Ecole des Mines de Nantes, Fr-44307 nantes Cedex 3 France,

Bibliografia

• [1] E. BARCUCCI, A. DEL LUNGO, M. NIVAT and R. PINZANI: Reconstructing convex polynominoes from their horizontal and vertical projections. Theoretical Computer Science, 155 (1996) 321-347.
• [2] N. BELDICEANU, I. KATRIEL and S. THIEL: Filtering algorithms for the same constraint. In J.-C. Regin and M. Rueher, (Eds), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems (CPAl-OR 2004), 3011 LNCS, Springer-Verlag, (2004), 65-79.
• [3] H. N. GABOW and R. E. TARJAN: A Linear-Time Algorithm for a Special Case of Disjoint Set Union. J. Computer and System Sciences, 30(2), (1985), 209-221.
• [4] D. GALE: A theorem on flows in networks. Pacif. J. Math., 7 (1957), 1073-1082.
• [5] G. T. HERMAN and A. KUHA (EDS.): Discrete Tomography: Foundations, Algorithms and Applications. Birkhauser Boston, Cambridge, MA, 1999.
• [6] L. R. FORD JR. and D. R. FULKERSON: Flows in Networks. Princeton University Press, 1962.
• [7] I. KATRIEL and S. THIEL: Fast bound consistency for the global cardinality constraint. Proc. 9th Int. Conf. on Principles and Practice of Constraint Programming (CP 2003), 2833 LNCS, (2003), 437-451.
• [8] K. MEHLHORN and S. THIEL: Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint. Proc. 6th Int. C0111. on Principles and Practice of Constraint Programming (CP 2000), 1894 LNCS, (2000), 306-319.
• [9] J.-C. REGIN: A filtering algorithm for constraints of difference in CSPs. Proc. 12th National Conj. on Artificial Intelligence (AAAI-94), (1994), 362-367.
• [10] J.-C. REGIN: Generalized Arc-Consistency for Global Cardinality Constraint. Proc. 13th National Conf. on Artificial Intelligence (AAA1-96), (1996), 209-215.
• [11] J.-C. REGIN and C. GOMES: The cardinality matrix constraint. In M. Wallace, (Ed), Principles and Practice of Constraint Programming (CP'2004), 3258 LNCS, Springer-Verlag, (2004), 572-587.
• [12] Medecins sans Frontieres. http://www.doctorswithoutborders.org/.