Abstract
Many combinatorial problems require of their solutions that they achieve a certain balance of given features. In the constraint programming literature, little has been written to specifically address this issue, particularly at the modeling level. We propose a new constraint dedicated to balancing, based on well-known and well-understood concepts in statistics. We show how it can be used to model different situations in which balance is important. We also design efficient filtering algorithms to guide the search towards balanced solutions.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Problem 30 of CSPLIB, www.csplib.org
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)
Lemaître, M., Verfaillie, G., Bataille, N.: Exploiting a Common Property Resource under a Fairness Constraint: a Case Study. In: Proc. IJCAI, Stockholm, Sweden (1999)
Quimper, C.-G., van Beek, P., López-Ortiz, A., Golynski, A., Sadjad, S.B.: An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 600–614. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pesant, G., Régin, JC. (2005). SPREAD: A Balancing Constraint Based on Statistics. In: van Beek, P. (eds) Principles and Practice of Constraint Programming - CP 2005. CP 2005. Lecture Notes in Computer Science, vol 3709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11564751_35
Download citation
DOI: https://doi.org/10.1007/11564751_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29238-8
Online ISBN: 978-3-540-32050-0
eBook Packages: Computer ScienceComputer Science (R0)