Abstract
A general approach to improving constraint solving is to take advantage of information on the structure and particularities of the considered constraints. Specific properties can determine the use of customized solvers, or they can be used to improve solver cooperation and propagation strategies. We propose a framework in which properties are seen as abstractions of the underlying constraints, and relate them to the literature on abstract reasoning. We mainly exemplify this framework on numerical constraints, where such properties as monotonicity and convexity are important. In particular, we show how deductions can be made on such constraints to dynamically infer properties. We overview connections with recent works, and we give guidelines and examples on how this kind of tool can be integrated into existing or customized constraint-solvers.
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
F. Benhamou and W. J. Older. Applying interval arithmetic to real, integer, and boolean constraints. J. of Logic Programming, 32(1):1–24, 1997.
L. Bordeaux, E. Monfroy, and F. Benhamou. Raisonnement automatique sur les propriétés de contraintes numériques. In Actes des 11èmes J. Franc. de Programmation en Logique et par Contraintes (JFPLC), Nice, France, 2002. Hermès. in french.
P. Cousot and R. Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Conf. Record of the 4th Annual ACM Symp. on Principles of Programming Languages (POPL), pages 238–252, Los Angeles, CA, 1977. ACM Press, New York, NY.
P. Cousot and R. Cousot. Abstract interpretation and application to logic programs. J. of Logic Programming, 13(2–3):103–179, 1992.
Y. Deville, O. Barette, and P. Van Hentenryck. Constraint satisfaction over connected row convex constraints. Artificial Intelligence, 109(1–2):243–271, 1999.
E. C. Freuder. A sufficient condition for backtrack-free search. J. of the ACM, 29(1):24–32, 1982.
F. Giunchiglia and T. Walsh. A theory of abstraction. Artificial Intelligence, 56(2–3): 323–390, 1992.
L. Granvilliers, E. Monfroy, and F. Benhamou. Symbolic-interval cooperation in constraint programming. In Proc. of the Int. Symp. on Symbolic and Algebraic Computation (ISSAC), London, Ontario, 2001. ACM Press.
E. R. Hansen. Global Optimization Using Interval Analysis. Pure and Applied Mathematics. Marcel Dekker Inc., 1992.
D. Lesaint. Inferring constraint types in constraint programming. In Proc. of the 8th Int. Conf. on Principles and Practice of Constraint Programming (CP), LNCS, pages 492–507, Ithaca, NY, 2002. Springer.
K. Marriott and P.-J. Stuckey. Approximating interaction between linear arithmetic constraints. In Proc. of the International Symposium on Logic Programming (ISLP), pages 571–585, Ithaca, NY, 1994. MIT Press.
R. E. Moore. Interval Analysis. Prentice-Hall, 1966.
S. Nash and A. Sofer. Linear and Nonlinear Programming. McGraw Hill, 1996.
E. Petrov and E. Monfroy. Automatic analysis of composite solvers. In Proc. of the 14th IEEE Int. Conf. on Tools with Artificial Intelligence (ICTAI), Washington, 2002. IEEE Press. To appear.
D. Sam-Haroud and B. Faltings. Consistency techniques for continuous constraints. Constraints, 1(1–2):85–118, 1996.
Z. Yuanlin and R. H. C. Yap. Arc consistency on n-ary monotonic and linear constraints. In Proc. of the 6th Int. Conf. on Principles and Practice of Constraint Programming (CP), LNCS, pages 470–483, Singapore, 2000. Springer.
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
Bordeaux, L., Monfroy, E., Benhamou, F. (2003). Towards Automated Reasoning on the Properties of Numerical Constraints. In: O’Sullivan, B. (eds) Recent Advances in Constraints. CologNet 2002. Lecture Notes in Computer Science, vol 2627. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36607-5_4
Download citation
DOI: https://doi.org/10.1007/3-540-36607-5_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00986-3
Online ISBN: 978-3-540-36607-2
eBook Packages: Springer Book Archive