Abstract
Constraint toolkits generally propose a sum constraint where a global objective variable should be equal to a sum of local objective variables, on which bound-consistency is achieved. To solve optimization problems this propagation is poor. Therefore, ad-hoc techniques are designed for pruning the global objective variable by taking account of the interactions between constraints defined on local objective variables. Each technique is specific to each (class of) practical problem. In this paper, we propose a new global constraint which deals with this issue in a generic way. We propose a sum constraint which exploits the propagation of a set of constraints defined on local objective variables.
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
Kovács, A., Beck, J.C.: A global constraint for total weighted completion time for cumulative resources. Constraints (2010) (in print)
Larrosa, J., Meseguer, P., Schiex, T., Verfaillie, G.: Reversible DAC and other improvements for solving Max-CSP. Proceedings AAAI, pp. 347–352 (1998)
Larsson, T., Patriksson, M.: On side constrained models of traffic equilibria. In: Proc. of the 19th Course of the International School of Mathematics, pp. 169–178. Plenum Press, New York (1995)
Petit, T., Poder, E.: Global propagation of side constraints for solving over-constrained problems. Annals of Operations Research 184, 295–315 (2011)
Régin, J.-C., Petit, T., Bessière, C., Puget, J.-F.: An original constraint based approach for solving over constrained problems. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 543–548. Springer, Heidelberg (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Régin, JC., Petit, T. (2011). The Objective Sum Constraint. In: Achterberg, T., Beck, J.C. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2011. Lecture Notes in Computer Science, vol 6697. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21311-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-21311-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21310-6
Online ISBN: 978-3-642-21311-3
eBook Packages: Computer ScienceComputer Science (R0)