Abstract
This paper addresses constraint solving over continuous domains in the context of decision making, and discusses the trade-off between precision in the definition of the solution space and the computational efforts required. In alternative to local consistency, we propose maintaining global hull-consistency and present experimental results that show that this may be an appropriate alternative to other higher order consistencies. We tested various global hull enforcing algorithms and the best results were obtained with the integration of a local search procedure within interval constraint propagation.
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
Benhamou, F., McAllester, D., Van Hentenryck, P.: CLP(Intervals) revisited. In: Logic Programming Symposium, pp. 124–131. MIT Press, Cambridge (1994)
Benhamou, F., Older, W.J.: Applying Interval Arithmetic to Real, Integer and Boolean Constraints. Journal of Logic Programming 32(1), 1–24 (1997)
Bordeaux, L., Monfroy, E., Benhamou, F.: Improved bounds on the complexity of kB-consistency. In: Proceedings of 17th IJCAI, pp. 640–650 (2001)
Cleary, J.G.: Logical Arithmetic. Future Computing Systems 2(2), 125–149 (1987)
Collavizza, H., Delobel, F., Rueher, M.: Extending Consistent Domains of Numeric CSP. In: IJCAI, pp. 406–413 (1999)
Cruz, J., Barahona, P.: An Interval Constraint Approach to Handle Parametric ODEs for Decision Support. In: Principles Practice Constraint Programming, pp. 478–479. Springer, Heidelberg (1999)
Cruz, J., Barahona, P., Benhamou, F.: Integrating Deep Biomedical Models into Medical DSSs: an Interval Constraint Approach. In: AI in Medicine, pp. 185–194. Springer, Heidelberg (1999)
Cruz, J., Barahona, P.: Global Hull Consistency with Local Search for Continuous Constraint Solving. In: 10th Portuguese Conference on AI, pp. 349–362. Springer, Heidelberg (2001)
Cruz, J., Barahona, P.: Handling Differential Equations with Constraints for Decision Support. In: Frontiers of Combining Systems, pp. 105–120. Springer, Heidelberg (2000)
Demmel, J.W.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997)
Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Least Squares. Prentice-Hall, Englewood Cliffs (1983)
Fletcher, R., Reeves, C.: Function Minimization by Conjugate Gradients. Computer Journal 7, 149–154 (1964)
Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
Goualard, F.: Langages et environnements en programmation par contraintes d’intervalles. Thèse de doctorat. Université de Nantes (2000)
Hansen, E.: Global Optimization Using Interval Analysis. Marcel Dekker, New York (1992)
Sam-Haroud, D., Faltings, B.V.: Consistency Techniques for Continuous Constraints. Constraints 1(1,2), 85–118 (1996)
Krippahl, L., Barahona, P.: Applying Constraint Propagation to Protein Structure Determination. In: Principles Practice Constraint Programming, pp. 289–302. Springer, Heidelberg (1999)
Lhomme, O.: Consistency Techniques for Numeric CSPs. In: IJCAI, pp. 232–238. IEEE Pr., Los Alamitos (1993)
Montanari, U.: Networks of Constraints: Fundamental Properties and Applications to Picture Processing. Information Science 7(2), 95–132 (1974)
Moore, R.E.: Interval Analysis. Prentice-Hall, Englewood Cliffs (1966)
Ortega, J., Rheinboldt, W.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, London (1970)
Puget, J.-F., Van Hentenryck, P.: A Constraint Satisfaction Approach to a Circuit Design Problem. Journal of Global Optimization, MIT Press (1997)
Stoer, J., Burlisch, R.: Introduction to Numerical Analysis. Springer, Heidelberg (1980)
Van Hentenryck, P., McAllester, D., Kapur, D.: Solving Polynomial Systems Using a Branch and Prune Approach. SIAM Journal of Numerical Analysis 34(2) (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cruz, J., Barahona, P. (2003). Maintaining Global Hull Consistency with Local Search for Continuous CSPs. In: Bliek, C., Jermann, C., Neumaier, A. (eds) Global Optimization and Constraint Satisfaction. COCOS 2002. Lecture Notes in Computer Science, vol 2861. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39901-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-39901-8_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20463-3
Online ISBN: 978-3-540-39901-8
eBook Packages: Springer Book Archive