Softening Gcc and Regular with preferences

ABSTRACT

In this paper, we present the soft global constraints Σ-gcc and Σ-regular which are the soft versions with preferences of well-known global constraints Gcc and Regular. For each of them, we introduce a new violation based semantic which takes into account preferences and propose algorithms to enforce hyperarc consistency in polynomial time, making use of flow theory.

REFERENCES

• 1: L. R. Ford and D. R. Fulkerson. Flow in Networks. Princeton University Press, 1962.
• 2: Pascal Van Hentenryck , Helmut Simonis , Mehmet Dincbas, Constraint satisfaction using constraint logic programming, Artificial Intelligence, v.58 n.1-3, p.113-159, Dec. 1992 [doi>10.1016/0004-3702(92)90006-J]
• 3: Jean-Philippe Metivier , Patrice Boizumault , Samir Loudni, All Different: Softening AllDifferent in Weighted CSPs, Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence, p.223-230, October 29-31, 2007 [doi>10.1109/ICTAI.2007.45]
• 4: G. Pesant. A regular language membership constraint for finite sequences of variables. In Wallace {10}, pages 482--495.
• 5: J. C. Régin. Generalized arc consistency for global cardinality constraint. In AAAI/IAAI, Vol. 1, pages 209--215, 1996.
• 6: Jean-Charles Régin, Arc Consistency for Global Cardinality Constraints with Costs, Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming, p.390-404, October 11-14, 1999
• 7: R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2): 146--160, 1972.
• 8: W. J. van Hoeve. A hyper-arc consistency algorithm for the soft alldifferent constraint. In Wallace {10}, pages 679--689.
• 9: Willem-Jan Hoeve , Gilles Pesant , Louis-Martin Rousseau, On global warming: Flow-based soft global constraints, Journal of Heuristics, v.12 n.4-5, p.347-373, September 2006 [doi>10.1007/s10732-006-6550-4]
• 10: M. Wallace, editor. CP 2004, volume LNCS 3258. Springer, 2004.
• 11: A. Zanarini, M. Milano, and G. Pesant. Improved algorithm for the soft global cardinality constraint. In J. Christopher Beck and Barbara M. Smith, editors, CPAIOR, volume 3990 of LNCS, pages 288--299. Springer, 2006.