×

Contractor programming. (English) Zbl 1191.68628

Summary: This paper describes a solver programming method, called contractor programming, that copes with two issues related to constraint processing over the reals. First, continuous constraints involve an inevitable step of solver design. Existing softwares provide an insufficient answer by restricting users to choose among a list of fixed strategies. Our first contribution is to give more freedom in solver design by introducing programming concepts where only configuration parameters were previously available. Programming consists in applying operators (intersection, composition, etc.) on algorithms called contractors that are somehow similar to propagators.Second, many problems with real variables cannot be cast as the search for vectors simultaneously satisfying the set of constraints, but a large variety of different outputs may be demanded from a set of constraints (e.g., a paving with boxes inside and outside of the solution set). These outputs can actually be viewed as the result of different contractors working concurrently on the same search space, with a bisection procedure intervening in case of deadlock. Such algorithms (which are not strictly speaking solvers) will be made easy to build thanks to a new branch & prune system, called paver.
Thus, this paper gives a way to deal harmoniously with a larger set of problems while giving a fine control on the solving mechanisms. The contractor formalism and the paver system are the two contributions. The approach is motivated and justified through different cases of study. An implementation of this framework named Quimper is also presented.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68N15 Theory of programming languages
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Batnini, H.; Rueher, M., Décomposition sémantique pour la résolution de systèmes d’equations de distance, JEDAI, Journal Electronique d’Intelligence Artificielle, 2, 1 (2004)
[2] F. Benhamou, F. Goualard, Universally quantified interval constraints, in: CP’00: 6th International Conference on Principles and Practice of Constraint Programming, 2000, pp. 67-82; F. Benhamou, F. Goualard, Universally quantified interval constraints, in: CP’00: 6th International Conference on Principles and Practice of Constraint Programming, 2000, pp. 67-82
[3] F. Benhamou, F. Goualard, L. Granvilliers, J.-F. Puget, Revising hull and box consistency, in: ICLP, 1999, pp. 230-244; F. Benhamou, F. Goualard, L. Granvilliers, J.-F. Puget, Revising hull and box consistency, in: ICLP, 1999, pp. 230-244
[4] Benhamou, F.; McAllester, D.; Van Hentenryck, P., CLP(intervals) revisited, (International Symposium on Logic Programming (1994), MIT Press), 124-138
[5] C. Bessière, R. Debruyne, Optimal and suboptimal singleton arc consistency algorithms, in: IJCAI, 19th International Joint Conference on Artificial Intelligence, 2005, pp. 54-59; C. Bessière, R. Debruyne, Optimal and suboptimal singleton arc consistency algorithms, in: IJCAI, 19th International Joint Conference on Artificial Intelligence, 2005, pp. 54-59
[6] Bliek, C.; Neveu, B.; Trombettoni, G., Using graph decomposition for solving continuous CSPs, (CP’98: 4th International Conference on Principles and Practice of Constraint Programming (1998), Springer), 102-116
[7] Chabert, G., IBEX, an Interval-Based EXplorer
[8] H. Collavizza, F. Delobel, M. Rueher, Extending consistent domains of numeric CSP, in: IJCAI, Sixteenth International Joint Conference on Artificial Intelligence, 1999, pp. 406-413; H. Collavizza, F. Delobel, M. Rueher, Extending consistent domains of numeric CSP, in: IJCAI, Sixteenth International Joint Conference on Artificial Intelligence, 1999, pp. 406-413
[9] Davis, E., Constraint propagation with interval labels, Artificial Intelligence, 32, 3, 281-331 (1987) · Zbl 0642.68176
[10] Dechter, R., Constraint Processing (2003), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA
[11] Delobel, F.; Collavizza, H.; Rueher, M., Comparing partial consistencies, Reliable Computing, 5, 3, 213-228 (1999) · Zbl 1130.65310
[12] A. Goldsztejn, A branch and prune algorithm for the approximation of non-linear AE-solution sets, in: SAC’06: Proceedings of the 2006 ACM Symposium on Applied Computing, 2006, pp. 1650-1654; A. Goldsztejn, A branch and prune algorithm for the approximation of non-linear AE-solution sets, in: SAC’06: Proceedings of the 2006 ACM Symposium on Applied Computing, 2006, pp. 1650-1654
[13] Goldsztejn, A.; Jaulin, L., Inner and outer approximations of existentially quantified equality constraints, (CP’06: 12th International Conference on Principles and Practice of Constraint Programming (2006), Springer), 198-212 · Zbl 1160.68546
[14] C. Grandón, G. Chabert, B. Neveu, Generalized interval projection: A new technique for consistent domain extension, in: IJCAI, 20th International Joint Conference on Artificial Intelligence, 2007, pp. 94-99; C. Grandón, G. Chabert, B. Neveu, Generalized interval projection: A new technique for consistent domain extension, in: IJCAI, 20th International Joint Conference on Artificial Intelligence, 2007, pp. 94-99
[15] Granvilliers, L.; Benhamou, F., Algorithm 852: RealPaver: An interval solver using constraint satisfaction techniques, ACM Transactions on Mathematical Software, 32, 1 (2006) · Zbl 1346.65020
[16] Hansen, E., Global Optimization Using Interval Analysis (2003), Dekker
[17] Hansen, E. R.; Sengupta, S., Bounding solutions of systems of equations using interval analysis, BIT Numerical Mathematics, 21, 2, 203-211 (1980) · Zbl 0455.65037
[18] Herrero, P.; Sainz, M. A.; Vehí, J.; Jaulin, L., Quantified set inversion algorithm with applications to control, Reliable Computing, 11, 5, 369-382 (2005) · Zbl 1081.65519
[19] Hyvönen, E., Constraint reasoning based on interval arithmetic: The tolerance propagation approach, Artificial Intelligence, 58, 1-3, 71-112 (1992) · Zbl 0782.68102
[20] ILOG, ILOG Solver
[21] L. Jaulin, Localization of an underwater robot using interval constraint propagation, in: CP’06: 12th International Conference on Principles and Practice of Constraint Programming, 2006; L. Jaulin, Localization of an underwater robot using interval constraint propagation, in: CP’06: 12th International Conference on Principles and Practice of Constraint Programming, 2006
[22] Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E., Applied Interval Analysis (2001), Springer
[23] Jaulin, L.; Walter, E., Guaranteed bounded-error parameter estimation for nonlinear models with uncertain experimental factors, Automatica, 35, 5, 849-856 (1999) · Zbl 0945.93526
[24] Jermann, C.; Trombettoni, G.; Neveu, B.; Mathis, P., Decomposition of geometric constraint systems: A survey, IJCGA, International Journal of Computational Geometry and Applications, 16, 5-6, 479-511 (2006)
[25] N. Jussien, G. Rochart, X. Lorca, The CHOCO constraint programming solver, in: CPAIOR’08 Workshop on Open-Source Software for Integer and Constraint Programming (OSSICP’08), 2008; N. Jussien, G. Rochart, X. Lorca, The CHOCO constraint programming solver, in: CPAIOR’08 Workshop on Open-Source Software for Integer and Constraint Programming (OSSICP’08), 2008
[26] Kearfott, R. B., GlobSol · Zbl 1180.90314
[27] Kearfott, R. B., Rigorous Global Search: Continuous Problems (1996), Springer · Zbl 0876.90082
[28] Knüppel, O., Profil/Bias · Zbl 0850.65086
[29] Lagerkvist, M. Z.; Schulte, C., Advisors for incremental propagation, (CP’07: 13th International Conference on Principles and Practice of Constraint Programming (2007), Springer)
[30] Y. Lebbah, C. Michel, M. Rueher, Efficient pruning technique based on linear relaxations, in: COCOS, in: Lecture Notes in Computer Science, vol. 3478, 2003, pp. 1-14; Y. Lebbah, C. Michel, M. Rueher, Efficient pruning technique based on linear relaxations, in: COCOS, in: Lecture Notes in Computer Science, vol. 3478, 2003, pp. 1-14
[31] O. Lhomme, Consistency techniques for numeric CSPs, in: IJCAI, 13th International Joint Conference on Artificial Intelligence, 1993, pp. 232-238; O. Lhomme, Consistency techniques for numeric CSPs, in: IJCAI, 13th International Joint Conference on Artificial Intelligence, 1993, pp. 232-238
[32] Merlet, J.-P., Alias
[33] Merlet, J.-P., Solving the forward kinematics of a gough-type parallel manipulator with interval analysis, International Journal of Robotics Research, 23, 3, 221-236 (2004)
[34] Moore, R., Interval Analysis (1966), Prentice-Hall · Zbl 0176.13301
[35] Neumaier, A., Interval Methods for Systems of Equations (1990), Cambridge University Press · Zbl 0706.15009
[36] Neveu, B.; Chabert, G.; Trombettoni, G., When interval analysis helps inter-block backtracking, (CP’06: 12th International Conference on Principles and Practice of Constraint Programming (2006), Springer) · Zbl 1160.68557
[37] Ning, S.; Kearfott, R. B., A comparison of some methods for solving linear interval equations, SIAM Journal of Numerical Analysis, 34, 1, 1289-1305 (1997) · Zbl 0889.65022
[38] Ratschan, S., RSolver
[39] Ratschan, S., Quantified constraints under perturbation, Journal of Symbolic Computation, 33, 4 (2002) · Zbl 1017.68161
[40] Rossi, F.; van Beek, P.; Walsh, T., Handbook of Constraint Programming (Foundations of Artificial Intelligence) (2006), Elsevier Science Inc.
[41] Sahinidis, N., BARON, Branch-And-Reduce Optimization Navigator
[42] Sam-Haroud, D.; Faltings, B., Consistency techniques for continuous constraints, Constraints, 1, 85-118 (1996)
[43] Schulte, C.; Lagerkvist, M.; Tack, G., Gecode
[44] Van Hentenryck, P., The OPL Optimization Programming Language (1999), MIT Press: MIT Press Cambridge
[45] Van Hentenryck, P.; McAllester, D.; Kapur, D., Solving polynomial systems using a branch and prune approach, SIAM Journal of Numerical Analysis, 34, 2, 797-827 (1997) · Zbl 0874.65039
[46] Van Hentenryck, P.; Michel, L., Constraint-Based Local Search (2005), The MIT Press
[47] Van Hentenryck, P.; Michel, L.; Deville, Y., Numerica: A Modeling Language for Global Optimization (1997), MIT Press: MIT Press Cambridge
[48] X-H. Vu, Rigorous solution techniques for numerical constraint satisfaction problems, PhD Thesis, Swiss Federal Institute of Technology in Lausanne, 2005; X-H. Vu, Rigorous solution techniques for numerical constraint satisfaction problems, PhD Thesis, Swiss Federal Institute of Technology in Lausanne, 2005
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.