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.
Supplemental Material
Available for Download
Software for "RealPaver: an interval solver using constraint satisfaction techniques"
- Alefeld, G. and Herzberger, J. 1983. Introduction to Interval Computations. Academic Press, NY.Google Scholar
- Apt, K. R. 2000. The role of commutativity in constraint propagation algorithms. ACM Trans. Program. Lang. Syst. 22, 6, 1002--1036. Google Scholar
- 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 Scholar
- 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 Scholar
- Benhamou, F. and Older, W. J. 1997. Applying interval arithmetic to real, integer and boolean constraints. J. Logic Program. 32, 1, 1--24.Google Scholar
- Berleant, D. and Kreinovich, V. 2003. cs.utep.edu/interval-comp/main.html.Google Scholar
- Berz, M. and Makino, K. 2002. COSY INFINITY: User's Guide and Reference Manual. Michigan State University. http://cosy.pa.msu.edu/.Google Scholar
- Ceberio, M. and Granvilliers, L. 2002a. Horner's rule for interval evaluation revisited. Comput. 69, 1, 51--81. Google Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- Free Software Foundation 2002. Bison 1.35. Free Software Foundation.Google Scholar
- Granvilliers, L. 2001. On the combination of interval constraint solvers. Reliable Comput. 7, 6, 467--483.Google Scholar
- 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 Scholar
- Granvilliers, L. and Benhamou, F. 2001. Progress in the solving of a circuit design problem. J. Global Optimization 20, 2, 155--168. Google Scholar
- Granvilliers, L., Benhamou, F., and Huens, E. 2001. Nonlinear constraint propagation. Deliverable of the COCONUT Project.Google Scholar
- IEEE. 1985. IEEE Standard for Binary Floating-Point Arithmetic. IEEE Computer Society. Reaffirmed 1990.Google Scholar
- ILOG 2001. Ilog Solver 5.2. ILOG.Google Scholar
- 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 Scholar
- Kearfott, R. B. 1996. Rigorous Global Search: Continuous Problems. Kluwer Academic Publishers, Dordrecht, Netherlands.Google Scholar
- 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 Scholar
- 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 Scholar
- Meier, M. and Schimpf, J. 1993. ECLiPSe User Manual. Tech. Rep. ECRC-93-6, ECRC (European Computer-Industry Research Centre), Munich, Germany.Google Scholar
- 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 Scholar
- Moore, R. E. 1966. Interval Analysis. Prentice-Hall, Englewood Cliffs, N.J.Google Scholar
- Neumaier, A. 1990. Interval Methods for Systems of Equations. Cambridge University Press, Cambridge, UK.Google Scholar
- O'Sullivan, B. 1999. Constraint-Aided conceptual design. Ph.D. thesis, University College Cork. Google Scholar
- PrologIA. 1996. Prolog IV: Constraints inside. Parc Technologique de Luminy---Case 919, 13288 Marseille cedex 09, France. Prolog IV reference manual.Google Scholar
- Puget, J. and Van Hentenryck, P. 1998. A constraint satisfaction approach to a circuit design problem. J. Global Optimization 13, 1, 75--93. Google Scholar
- Sam Haroud, D. and Faltings, B. 1996. Consistency techniques for continuous constraints. Constraints 1, 85--118.Google Scholar
- Schittkowski, K. 2002. Numerical Data Fitting in Dynamical Systems. Kluwer Academic Publishers, Dordrecht, Netherlands. Google Scholar
- 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 Scholar
- Stewart, D. 1965. A platform with 6 degrees of freedom. In Proceedings of the Institution of Mechanical Engineers 180, 15, 371--386.Google Scholar
- 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 Scholar
- Van Hentenryck, P., Michel, L., and Deville, Y. 1997. Numerica: A Modeling Language for Global Optimization. MIT Press, Cambridge, Mass. Google Scholar
- 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 Scholar
- Yamamura, K., Kawata, H., and Tokue, A. 1998. Interval analysis using linear programming. BIT 38, 188--201.Google Scholar
Index Terms
Algorithm 852: RealPaver: an interval solver using constraint satisfaction techniques
Recommendations
Solving weighted CSP by maintaining arc consistency
Recently, a general definition of arc consistency (AC) for soft constraint frameworks has been proposed by T. Schiex [Proc. CP-2000, Singapore, 2000, pp. 411-424]. In this paper we specialize this definition to weighted CSP and introduce two O(ed3) ...
Saving constraint checks in maintaining coarse-grained generalized arc consistency
Constraint check plays a central role in establishing generalized arc consistency which is widely used to solve constraint satisfaction problems. In this paper, we propose a new generalized arc consistency algorithm, called GTR, which ensures that the ...
A pre-processing algorithm for solving constraint satisfaction optimisation problems
SAICSIT '03: Proceedings of the 2003 annual research conference of the South African institute of computer scientists and information technologists on Enablement through technologyA constraint satisfaction problem (CSP) involves finding values, selected from a finite domain, for all variables such that all constraints on the variables are satisfied. A constraint satisfaction optimisation problem (CSOP) is a CSP that has some ...
Comments