skip to main content

Algorithm 852: RealPaver: an interval solver using constraint satisfaction techniques

Published:01 March 2006Publication History
Skip Abstract Section

Abstract

RealPaver is an interval software for modeling and solving nonlinear systems. Reliable approximations of continuous or discrete solution sets are computed using Cartesian products of intervals. Systems are given by sets of equations or inequality constraints over integer and real variables. Moreover, they may have different natures, being square or nonsquare, sparse or dense, linear, polynomial, or involving transcendental functions.The modeling language permits stating constraint models and tuning parameters of solving algorithms which efficiently combine interval methods and constraint satisfaction techniques. Several consistency techniques (box, hull, and 3B) are implemented. The distribution includes C sources, executables for different machine architectures, documentation, and benchmarks. The portability is ensured by the GNU C compiler.

Skip Supplemental Material Section

Supplemental Material

References

  1. Alefeld, G. and Herzberger, J. 1983. Introduction to Interval Computations. Academic Press, NY.Google ScholarGoogle Scholar
  2. Apt, K. R. 2000. The role of commutativity in constraint propagation algorithms. ACM Trans. Program. Lang. Syst. 22, 6, 1002--1036. Google ScholarGoogle Scholar
  3. Benhamou, F., Goualard, F., Granvilliers, L., and Puget, J.-F. 1999. Revising hull and box consistency. In Proceedings of the International Conference on Logic Programming (ICLP). The MIT Press, Las Cruces, Calif., 230--244. Google ScholarGoogle Scholar
  4. Benhamou, F., McAllester, D., and Van Hentenryck, P. 1994. CLP(intervals) revisited. In Proceedings of the Logic Programming Symposium (ILPS). MIT Press, Ithaca, N.Y. 124--138. Google ScholarGoogle Scholar
  5. Benhamou, F. and Older, W. J. 1997. Applying interval arithmetic to real, integer and boolean constraints. J. Logic Program. 32, 1, 1--24.Google ScholarGoogle Scholar
  6. Berleant, D. and Kreinovich, V. 2003. cs.utep.edu/interval-comp/main.html.Google ScholarGoogle Scholar
  7. Berz, M. and Makino, K. 2002. COSY INFINITY: User's Guide and Reference Manual. Michigan State University. http://cosy.pa.msu.edu/.Google ScholarGoogle Scholar
  8. Ceberio, M. and Granvilliers, L. 2002a. Horner's rule for interval evaluation revisited. Comput. 69, 1, 51--81. Google ScholarGoogle Scholar
  9. Ceberio, M. and Granvilliers, L. 2002b. Solving nonlinear equations by abstraction, gaussian elimination, and interval methods. In Proceedings of the International Workshop on Frontiers of Combining Systems. LNCS, vol. 2309. Springer, Berlin, 117--131. Google ScholarGoogle Scholar
  10. Cousot, P. and Cousot, R. 1977. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the ACM Symposium on Principles of Programming Languages, R. Sethi, ed. ACM Press, Los Angeles, Calif. 238--252. Google ScholarGoogle Scholar
  11. Fourer, R., Gay, D. M., and Kernighan, B. W. 2003. AMPL: A Modeling Language for Mathematical Programming, 2nd ed. Duxbury Press, Pacific Grove, CA. Google ScholarGoogle Scholar
  12. Free Software Foundation 2002. Bison 1.35. Free Software Foundation.Google ScholarGoogle Scholar
  13. Granvilliers, L. 2001. On the combination of interval constraint solvers. Reliable Comput. 7, 6, 467--483.Google ScholarGoogle Scholar
  14. Granvilliers, L. 2003. RealPaver User's Manual, version 0.3. University of Nantes, France. www.sciences.univ-nantes.fr/info/perso/permanents/granvil/realpaver.Google ScholarGoogle Scholar
  15. Granvilliers, L. and Benhamou, F. 2001. Progress in the solving of a circuit design problem. J. Global Optimization 20, 2, 155--168. Google ScholarGoogle Scholar
  16. Granvilliers, L., Benhamou, F., and Huens, E. 2001. Nonlinear constraint propagation. Deliverable of the COCONUT Project.Google ScholarGoogle Scholar
  17. IEEE. 1985. IEEE Standard for Binary Floating-Point Arithmetic. IEEE Computer Society. Reaffirmed 1990.Google ScholarGoogle Scholar
  18. ILOG 2001. Ilog Solver 5.2. ILOG.Google ScholarGoogle Scholar
  19. Jaulin, L., Kieffer, M., Didrit, O., and Walter, E. 2001. Applied Interval Analysis: With Examples in Parameter and State Estimation, Robust Control and Robotics. Springer, Berlin.Google ScholarGoogle Scholar
  20. Kearfott, R. B. 1996. Rigorous Global Search: Continuous Problems. Kluwer Academic Publishers, Dordrecht, Netherlands.Google ScholarGoogle Scholar
  21. Lebbah, Y., Rueher, M., and Michel, C. 2002. A global filtering algorithm for handling systems of quadratic equations and inequations. In Proceedings of the Principles and Practice of Constraint Programming (CP). LNCS, vol. 2470. Springer, Berlin, 109--123. Google ScholarGoogle Scholar
  22. Lhomme, O. 1993. Consistency techniques for numeric CSPs. In Proceedings of the International Joint Conference of Artificial Intelligence (IJCAI). Morgan Kaufman, ed. Chambéry, France, 232--238.Google ScholarGoogle Scholar
  23. Meier, M. and Schimpf, J. 1993. ECLiPSe User Manual. Tech. Rep. ECRC-93-6, ECRC (European Computer-Industry Research Centre), Munich, Germany.Google ScholarGoogle Scholar
  24. Merlet, J.-P. 2002. ALIAS: An Algorithms Library of Interval Analysis for Equation Systems. INRIA. http://www-sop.inria.fr/coprin/logiciels/ALIAS/ALIAS.html.Google ScholarGoogle Scholar
  25. Moore, R. E. 1966. Interval Analysis. Prentice-Hall, Englewood Cliffs, N.J.Google ScholarGoogle Scholar
  26. Neumaier, A. 1990. Interval Methods for Systems of Equations. Cambridge University Press, Cambridge, UK.Google ScholarGoogle Scholar
  27. O'Sullivan, B. 1999. Constraint-Aided conceptual design. Ph.D. thesis, University College Cork. Google ScholarGoogle Scholar
  28. PrologIA. 1996. Prolog IV: Constraints inside. Parc Technologique de Luminy---Case 919, 13288 Marseille cedex 09, France. Prolog IV reference manual.Google ScholarGoogle Scholar
  29. Puget, J. and Van Hentenryck, P. 1998. A constraint satisfaction approach to a circuit design problem. J. Global Optimization 13, 1, 75--93. Google ScholarGoogle Scholar
  30. Sam Haroud, D. and Faltings, B. 1996. Consistency techniques for continuous constraints. Constraints 1, 85--118.Google ScholarGoogle Scholar
  31. Schittkowski, K. 2002. Numerical Data Fitting in Dynamical Systems. Kluwer Academic Publishers, Dordrecht, Netherlands. Google ScholarGoogle Scholar
  32. Semenov, A., Kashevarova, T., Leshchenko, A., and Petunin, D. 1997. Combining various techniques with the algorithm of subdefinite calculations. In Proceedings of the International Conference on the Practical Application of Constraint Technology. LNCS, vol. 1277. Springer, Berlin, 287--306.Google ScholarGoogle Scholar
  33. Stewart, D. 1965. A platform with 6 degrees of freedom. In Proceedings of the Institution of Mechanical Engineers 180, 15, 371--386.Google ScholarGoogle Scholar
  34. Van Hentenryck, P., McAllester, D., and Kapur, D. 1997. Solving polynomial systems using a branch and prune approach. SIAM J. Numer. Anal. 34, 2, 797--827. Google ScholarGoogle Scholar
  35. Van Hentenryck, P., Michel, L., and Deville, Y. 1997. Numerica: A Modeling Language for Global Optimization. MIT Press, Cambridge, Mass. Google ScholarGoogle Scholar
  36. Vu, X.-H., Sam-Haroud, D., and Faltings, B. 2002. Approximation techniques for non-linear problems with continuum of solutions. In Proceedings of the Abstraction, Reformulation and Approximation Conference. LNCS, vol. 2371. Springer, Berlin, 224--241. Google ScholarGoogle Scholar
  37. Yamamura, K., Kawata, H., and Tokue, A. 1998. Interval analysis using linear programming. BIT 38, 188--201.Google ScholarGoogle Scholar

Index Terms

  1. Algorithm 852: RealPaver: an interval solver using constraint satisfaction techniques

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in

        Full Access

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader