Abstract
In constraint optimization, global constraints play a decisive role. To develop an efficient optimization tool, we need to be able to assess whether we are still able to improve the objective function further. This observation has lead to the development of a special kind of global constraints, so-called optimization constraints [2,5]. Roughly speaking, an optimization constraint expresses our wish to search for improving solutions only while enforcing feasibility for at least one of the constraints of the problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Knapsack Problem
- Constraint Programming
- Dynamic Programming Algorithm
- Global Constraint
- Optimization Constraint
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Fahle, T., Sellmann, M.: Cost-Based Filtering for the Constrained Knapsack Problem. Annals of Operations Research 115, 73–93 (2002)
Focacci, F., Lodi, A., Milano, M.: Cost-Based Domain Filtering. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 189–203. Springer, Heidelberg (1999)
Freuder, E.C.: A Sufficient Condition for Backtrack-Free Search. Journal of the ACM 29(1), 24–32 (1982)
Ibarra, O.H., Kim, C.E.: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems. Journal of the ACM 22(4), 463–468 (1975)
Milano, M.: Integration of Mathematical Programming and Constraint Programming for Combinatorial Optimization Problems. In: Tutorial at CP 2000 (2000)
Sellmann, M.: The Practice of Approximated Consistency for Knapsack Constraints. In: Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI), pp. 179–184. AAAI Press, Menlo Park (2004)
Sellmann, M.: Approximated Consistency for Knapsack Constraints. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 679–693. Springer, Heidelberg (2003)
Sellmann, M., Fahle, T.: Constraint Programming Based Lagrangian Relaxation for the Automatic Recording Problem. Annals of Operations Research 118, 17–33 (2003)
Trick, M.: A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints. In: 3rd International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR), pp. 113–124 (2001)
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
Sellmann, M. (2005). Approximated Consistency for the Automatic Recording Problem. 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_72
Download citation
DOI: https://doi.org/10.1007/11564751_72
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)