Constraint propagation on quadratic constraints. (English) Zbl 1208.68200
Summary: This paper considers constraint propagation methods for continuous constraint satisfaction problems consisting of linear and quadratic constraints. All methods can be applied after suitable preprocessing to arbitrary algebraic constraints. The basic new techniques consist in eliminating bilinear entries from a quadratic constraint, and solving the resulting separable quadratic constraints by means of a sequence of univariate quadratic problems. Care is taken to ensure that all methods correctly account for rounding errors in the computations. Various tests and examples illustrate the advantage of the presented method.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 90C20 | Quadratic programming |
Keywords:
constraint propagation; constraint programming; continuous constraints; quadratic constraint satisfaction problems; rounding error control; verified computation; quadratic programming; constrained optimizationReferences:
| [1] | Anderson, E. D., & Anderson, K. D. (1995). PresGolving in linear programming. Mathematical Programming, 71, 221–245. |
| [2] | Apt, K. R. (1999). The essence of constraint propagation. Theoretical Computer Science, 221(1), 179–210. · Zbl 0930.68164 · doi:10.1016/S0304-3975(99)00032-8 |
| [3] | Babichev, A. B., Kadyrova, O. B., Kashevarova, T. P., Leshchenko, A. S., & Semenov, A. L. (1993). UniCalc, a novel approach to solving systems of algebraic equations. Interval Computations, 3, 29–47. · Zbl 0829.65067 |
| [4] | Benhamou, F. (1996). Heterogeneous constraint solving. In M. Hanus & M. Rodríguez-Artalejo (Eds.), Proceedings of ALP’96, 5th international conference on algebraic and logic programming. Lecture notes in computer science (Vol. 1139, pp. 62–76). Aachen: Springer. · Zbl 1355.68030 |
| [5] | Benhamou, F., Goualard, F., Granvilliers, L., & Puget, J. F. (1999). Revising hull and box consistency. In International conference on logic programming (pp. 230–244). citeseer.ist.psu.edu/benhamou99revising.html . |
| [6] | Benhamou, F., Granvilliers, L., & Goualard, F. (1999). Interval constraints: Results and perspectives. In New Trends in constraints (pp. 1–16). citeseer.ist.psu.edu/benhamou99interval.html . |
| [7] | Benhamou, F., McAllister, D., & Van Hentenryck, P. (1994). CLP(intervals) revisited. In Proc. international symposium on logic programming (pp. 124–138). Cambridge: MIT. |
| [8] | Benhamou, F., & Older, W. J. (1997). Applying interval arithmetic to real, integer, and Boolean constraints. Journal of Logic Programming, 32, 1–24. · Zbl 0882.68032 · doi:10.1016/S0743-1066(96)00142-2 |
| [9] | Bliek, C., Spelucci, P., Vicente, L. N., Neumaier, A., Granvilliers, L., Monfro, E., et al. (2000). Algorithms for solving nonlinear constrained and optimization problems: The state of the art. http://www.mat.univie.ac.at/\(\sim\)neum/ms/StArt.pdf . |
| [10] | Ceberio, M., & Granvilliers, L. (2000). Solving nonlinear systems by constraint inversion and interval arithmetic. In AISC (pp. 127–141). http://link.springer.de/link/service/series/0558/bibs/1930/19300127.htm . · Zbl 1042.68127 |
| [11] | Chen, H. M., & van Emden, M. H. (1995). Adding interval constraints to the Moore–Skelboe global optimization algorithm. In V. Kreinovich (Ed.), Extended abstracts of APIC’95 of the international workshop on applications of interval computations (pp. 54–57). |
| [12] | Cleary, J. G. (1987). Logical arithmetic. Future Computing Systems, 2, 125–149. |
| [13] | Cruz, J., & Barahona, P. (2005). Constraint reasoning in deep biomedical models. Journal of Artificial Intelligence in Medicine, 34, 77–88. http://ssdi.di.fct.unl.pt/\(\sim\)pb/papers/ludi_constraints.pdf . · doi:10.1016/j.artmed.2004.07.013 |
| [14] | Dallwig, S., Neumaier, A., & Schichl, H. (1997). GLOPT–a program for constrained global optimization (pp. 19–36). Dordrecht: Kluwer. · Zbl 0886.90119 |
| [15] | Dallwig, S., Neumaier, A., & Schichl, H. (1997). GLOPT–a program for constrained global optimization. In I. Bomze, et al. (Ed.), Developments in global optimization (pp. 19–36). Dordrecht: Kluwer. · Zbl 0886.90119 |
| [16] | Daney, D., Grandon, C., & Papegay, Y. (2006). Combining CP and interval methods for solving the direct kinematic of a parallel robot under uncertainties. In IntCP 06 workshop. ftp://ftp-sop.inria.fr/coprin/daney/articles/intcp06.pdf . |
| [17] | Dimitrova, N. S., & Markov, S. M. (1981). Über die intervall-arithmetische Berechnung des Wertebereichs einer Funktion mit Anwendungen, Freiburger Intervall-Berichte. University of Freiburg, 81, 1–22. |
| [18] | Domes, F. (2009). GloptLab–a configurable framework for the rigorous global solution of quadratic constraint satisfaction problems. Optimization Methods and Software, 24(4 & 5), 727–747. http://www.mat.univie.ac.at/\(\sim\)dferi/publ/Gloptlab.pdf . · Zbl 1180.90217 · doi:10.1080/10556780902917701 |
| [19] | Domes, F., & Neumaier, A. (2009). Directed Cholesky factorizations and applications. http://www.mat.univie.ac.at/\(\sim\)dferi/publ/Cholesky.pdf . · Zbl 1242.90152 |
| [20] | Domes, F., & Neumaier, A. (2009). Linear methods for quadratic constraint satisfaction problems. http://www.mat.univie.ac.at/\(\sim\)dferi/publ/ . · Zbl 1151.90549 |
| [21] | Granvilliers, L., & Benhamou, F. (2006). Realpaver: An interval solver using constraint satisfaction techniques. ACM Transactions on Mathematical Software, 32, 38–156. http://www.sciences.univ-nantes.fr/info/perso/permanents/granvil/realpaver/ . · Zbl 1346.65020 · doi:10.1145/1132973.1132980 |
| [22] | Hager, G. D. (1993). Solving large systems of nonlinear constraints with application to data modeling. Interval Computations, 3, 169–200. · Zbl 0829.65007 |
| [23] | Hansen, R. E., & Walster, W. G. (2002). Sharp bounds on interval polynomial roots. Reliable Computing, 8, 115–122. · Zbl 0994.65053 · doi:10.1023/A:1014797921296 |
| [24] | Hyvönen, E., & De Pascale, S. (1996). Interval computations on the spreadsheet. In R. B. Kearfott, & V. Kreinovich (Eds.), Applications of interval computations (pp. 169–209). Dordrecht: Kluwer. · Zbl 0841.65032 |
| [25] | Jaulin, L. (2000). Interval constraint propagation with application to bounded-error estimation. Automatica, 36, 1547–1552. https://www.ensieta.fr/e3i2/Jaulin/hull.pdf . · Zbl 0959.93501 · doi:10.1016/S0005-1098(00)00068-6 |
| [26] | Jaulin, L. (2006). Interval constraints propagation techniques for the simultaneous localization and map building of an underwater robot. http://www.mat.univie.ac.at/\(\sim\)neum/glopt/gicolag/talks/jaulin.pdf . |
| [27] | Jaulin, L., Kieffer, M., Braems, I., & Walter, E. (1999). Guaranteed nonlinear estimation using constraint propagation on sets. International Journal of Control, 74, 1772–1782. https://www.ensieta.fr/e3i2/Jaulin/observer.pdf . · Zbl 1023.93020 · doi:10.1080/00207170110090642 |
| [28] | Jermann, C., Lebbah, Y., & Sam-Haroud, D. (2007). Interval analysis, constraint propagation and applications. In F. Benhamou, N. Jussien, & B. O’Sullivan (Eds.), Trends in constraint programming (chapter 4, pp. 223–259). ISTE. |
| [29] | Kearfott, R. B. (1991). Decomposition of arithmetic expressions to improve the behavior of interval iteration for nonlinear systems. Computing, 47, 169–191. · Zbl 0739.65049 · doi:10.1007/BF02253433 |
| [30] | Krippahl, L., & Barahona, P. (2002). PSICO: Solving protein structures with constraint programming and optimization. Constraints, 7, 317–331. http://ssdi.di.fct.unl.pt/\(\sim\)pb/papers/ludi_constraints.pdf . · Zbl 1028.68026 · doi:10.1023/A:1020577603762 |
| [31] | Lebbah, Y. (2003). iCOs – Interval COnstraints Solver. http://ylebbah.googlepages.com/icos . |
| [32] | Lebbah, Y., Michel, C., & Rueher, M. (2005). A rigorous global filtering algorithm for quadratic constraints. Constraints, 10, 47–65. http://ylebbah.googlepages.com/research . · Zbl 1066.90090 · doi:10.1007/s10601-004-5307-7 |
| [33] | Lodwick, A. W. (1989). Constraint propagation, relational arithmetic in ai systems and mathematical programs. Annals of Operation Research, 21, 143–148. · Zbl 0705.90056 · doi:10.1007/BF02022097 |
| [34] | Merlet, J-P. (2004). Solving the forward kinematics of a Gough-type parallel manipulator with interval analysis. International Journal of Robotics Research, 23, 221–235. http://www-sop.inria.fr/coprin/equipe/merlet/Papers/IJRR2004.pdf . · doi:10.1177/0278364904039806 |
| [35] | Neumaier, A. (1990). Interval methods for systems of equations. In Encyclopedia of mathematics and its applications (Vol. 37). Cambridge: Cambridge University Press. · Zbl 0715.65030 |
| [36] | Neumaier, A. (2003). Enclosing clusters of zeros of polynomials. Journal of Computational and Applied Mathematics, 156, 389–401. · Zbl 1029.65050 · doi:10.1016/S0377-0427(03)00380-7 |
| [37] | Neumaier, A. (2004). Complete search in continuous global optimization and constraint satisfaction. Acta Numerica, 1004, 271–369. · Zbl 1113.90124 |
| [38] | Older, W., & Vellino, A. (1993). Constraint arithmetic on real intervals. In F. Benhameou & A. Colmerauer (Eds.), Constrained logic programming: Selected research. Cambridge: MIT. |
| [39] | Sahinidis, N., & Tawarmalani, M. (2003). Convexification and global optimization in continuous and mixed–integer nonlinear programming: Theory, algorithms, software, and applications. Dordrecht: Kluwer. · Zbl 1031.90022 |
| [40] | Sahinidis, V. N., & Tawarmalani, M. (2005). BARON 7.2.5: Global optimization of mixed-integer nonlinear programs. User’s manual. http://www.gams.com/dd/docs/solvers/baron.pdf . |
| [41] | Schichl, H. (2003). Mathematical modeling and global optimization, habilitation thesis. http://www.mat.univie.ac.at/\(\sim\)herman/papers/habil.pdf . |
| [42] | Schichl, H., & Neumaier, A. (2005). Interval analysis on directed acyclic graphs for global optimization. Journal of Global Optimization, 33(4), 541–562. · Zbl 1094.65061 · doi:10.1007/s10898-005-0937-x |
| [43] | Schichl, H., et al. (2000–2008). The COCONUT environment. Software. http://www.mat.univie.ac.at/coconut-environment . |
| [44] | van Emden, H. M. (2001). Computing functional and relational box consistency by structured propagation in atomic constraint systems. CoRR, cs.PL/0106008. |
| [45] | Van Hentenryck, P. (1998). A gentle introduction to numerica. Artifical Intelligence, 103, 209–235. · Zbl 0910.68095 · doi:10.1016/S0004-3702(98)00053-8 |
| [46] | Van Hentenryck, P., Michel, L., & Benhamou, F. (1997). Newton: Constraint programming over non-linear constraints. Scientific Programming, 30, 83–118. · Zbl 0891.68015 |
| [47] | Van Hentenryck, P., Michel, L., & Deville, Y. (1997). Numerica. A modeling language for global optimization. Cambridge: MIT. |
| [48] | Vu, X.-H., Schichl, H., & Sam-Haroud, D. (2004). Using directed acyclic graphs to coordinate propagation and search for numerical constraint satisfaction problems. In Proceedings of the 16th IEEE international conference on tools with artificial intelligence (ICTAI 2004) (pp. 72–81). http://www.mat.univie.ac.at/\(\sim\)herman/papers/ICTAI2004.pdf . |
| [49] | Vu, X.-H., Schichl, H., & Sam-Haroud, D. (2007). Interval propagation and search on directed acyclic graphs for numerical constraint solving. Journal of Global Optimization, 39. http://www.mat.univie.ac.at/\(\sim\)herman/papers/FBPD-Hermann.pdf . · Zbl 1179.90267 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
