article

Contractor programming

Authors:

Gilles Chabert,

Luc JaulinAuthors Info & Claims

Artificial Intelligence, Volume 173, Issue 11

Pages 1079 - 1100

https://doi.org/10.1016/j.artint.2009.03.002

Published: 01 July 2009 Publication History

Abstract

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.

References

[1]

Batnini, H. and Rueher, M., Décomposition sémantique pour la résolution de systèmes d'equations de distance. JEDAI, Journal Electronique d'Intelligence Artificielle. v2 i1.

[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

Digital Library

[3]

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. and Van Hentenryck, P., CLP(intervals) revisited. In: International Symposium on Logic Programming, MIT Press. pp. 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

Digital Library

[6]

Bliek, C., Neveu, B. and Trombettoni, G., Using graph decomposition for solving continuous CSPs. In: CP'98: 4th International Conference on Principles and Practice of Constraint Programming, Springer. pp. 102-116.

[7]

http://www.ibex-lib.org

[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

[9]

Davis, E., Constraint propagation with interval labels. Artificial Intelligence. v32 i3. 281-331.

[10]

Dechter, R., Constraint Processing. 2003. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

[11]

Delobel, F., Collavizza, H. and Rueher, M., Comparing partial consistencies. Reliable Computing. v5 i3. 213-228.

[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

Digital Library

[13]

Goldsztejn, A. and Jaulin, L., Inner and outer approximations of existentially quantified equality constraints. In: CP'06: 12th International Conference on Principles and Practice of Constraint Programming, Springer. pp. 198-212.

[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

[15]

Granvilliers, L. and Benhamou, F., Algorithm 852: RealPaver: An interval solver using constraint satisfaction techniques. ACM Transactions on Mathematical Software. v32 i1.

[16]

Hansen, E., Global Optimization Using Interval Analysis. 2003. second ed. Dekker.

[17]

Hansen, E.R. and Sengupta, S., Bounding solutions of systems of equations using interval analysis. BIT Numerical Mathematics. v21 i2. 203-211.

[18]

Herrero, P., Sainz, M.A., Vehí, J. and Jaulin, L., Quantified set inversion algorithm with applications to control. Reliable Computing. v11 i5. 369-382.

[19]

Hyvönen, E., Constraint reasoning based on interval arithmetic: The tolerance propagation approach. Artificial Intelligence. v58 i1--3. 71-112.

[20]

http://www.ilog.com/products/cp/

[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

[22]

Jaulin, L., Kieffer, M., Didrit, O. and Walter, E., Applied Interval Analysis. 2001. Springer.

[23]

Jaulin, L. and Walter, E., Guaranteed bounded-error parameter estimation for nonlinear models with uncertain experimental factors. Automatica. v35 i5. 849-856.

[24]

Jermann, C., Trombettoni, G., Neveu, B. and Mathis, P., Decomposition of geometric constraint systems: A survey. IJCGA, International Journal of Computational Geometry and Applications. v16 i5--6. 479-511.

[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

[26]

http://interval.louisiana.edu/GlobSol

[27]

Kearfott, R.B., Rigorous Global Search: Continuous Problems. 1996. Springer.

[28]

http://www.ti3.tu-harburg.de/Software/PROFILEnglisch.html

[29]

Lagerkvist, M.Z. and Schulte, C., Advisors for incremental propagation. In: CP'07: 13th International Conference on Principles and Practice of Constraint Programming, 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

[31]

O. Lhomme, Consistency techniques for numeric CSPs, in: IJCAI, 13th International Joint Conference on Artificial Intelligence, 1993, pp. 232--238

Digital Library

[32]

http://www-sop.inria.fr/coprin/logiciels/ALIAS

[33]

Merlet, J.-P., Solving the forward kinematics of a gough-type parallel manipulator with interval analysis. International Journal of Robotics Research. v23 i3. 221-236.

[34]

Moore, R., Interval Analysis. 1966. Prentice-Hall.

[35]

Neumaier, A., Interval Methods for Systems of Equations. 1990. Cambridge University Press.

[36]

Neveu, B., Chabert, G. and Trombettoni, G., When interval analysis helps inter-block backtracking. In: CP'06: 12th International Conference on Principles and Practice of Constraint Programming, Springer.

[37]

Ning, S. and Kearfott, R.B., A comparison of some methods for solving linear interval equations. SIAM Journal of Numerical Analysis. v34 i1. 1289-1305.

[38]

http://rsolver.sourceforge.net

[39]

Ratschan, S., Quantified constraints under perturbation. Journal of Symbolic Computation. v33 i4.

[40]

Rossi, F., van Beek, P. and Walsh, T., Handbook of Constraint Programming (Foundations of Artificial Intelligence). 2006. Elsevier Science Inc.

[41]

http://www.andrew.cmu.edu/user/ns1b/baron/baron.html

[42]

Sam-Haroud, D. and Faltings, B., Consistency techniques for continuous constraints. Constraints. v1. 85-118.

[43]

http://www.gecode.org/

[44]

Van Hentenryck, P., The OPL Optimization Programming Language. 1999. MIT Press, Cambridge.

[45]

Van Hentenryck, P., McAllester, D. and Kapur, D., Solving polynomial systems using a branch and prune approach. SIAM Journal of Numerical Analysis. v34 i2. 797-827.

[46]

Van Hentenryck, P. and Michel, L., Constraint-Based Local Search. 2005. The MIT Press.

[47]

Van Hentenryck, P., Michel, L. and Deville, Y., Numerica: A Modeling Language for Global Optimization. 1997. 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

Cited By

Alexandre dit Sandretto J(2024)Validated B-series and Runge-Kutta pairsNumerical Algorithms10.1007/s11075-023-01697-596:3(1045-1062)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11075-023-01697-5
Vanaret C(2024)Interval constraint programming for globally solving catalog-based categorical optimizationJournal of Global Optimization10.1007/s10898-023-01362-089:2(457-476)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10898-023-01362-0
Moroz G(2024)Sparse Tensors and Subdivision Methods for Finding the Zero Set of Polynomial EquationsComputer Algebra in Scientific Computing10.1007/978-3-031-69070-9_14(236-251)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-69070-9_14
Show More Cited By

Recommendations

CHR++: An efficient CHR system in C++ with don’t know non-determinism▪
Abstract
This article introduces CHR++, an implementation of CHR (Constraint Handling Rules) in C++. CHR++ has been designed to be efficient, user-friendly, and to make it easier to model problems of NP (Non-deterministic Polynomial time) complexity class ...
Highlights
- CHR++ is a powerful implementation of CHR on top of the C++ language.
- CHR++ allows to model and solve decision and optimisation problems.
- CHR is a CHR extension which adds the don’t know non-determinism, to gives the ability to ...
Constraint-Based Object-Oriented Programming

Constraint programming (CP) is a young but rapidly developing technology that supports the modeling and solution of a wide range of planning, scheduling, search, and optimization problems. The integration of CP concepts into languages from other ...
A translational approach to constraint answer set solving

We present a new approach to enhancing Answer Set Programming (ASP) with Constraint Processing techniques which allows for solving interesting Constraint Satisfaction Problems in ASP. We show how constraints on finite domains can be decomposed into ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence

Artificial Intelligence Volume 173, Issue 11

July, 2009

93 pages

ISSN:0004-3702

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2009.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 July 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alexandre dit Sandretto J(2024)Validated B-series and Runge-Kutta pairsNumerical Algorithms10.1007/s11075-023-01697-596:3(1045-1062)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11075-023-01697-5
Vanaret C(2024)Interval constraint programming for globally solving catalog-based categorical optimizationJournal of Global Optimization10.1007/s10898-023-01362-089:2(457-476)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10898-023-01362-0
Moroz G(2024)Sparse Tensors and Subdivision Methods for Finding the Zero Set of Polynomial EquationsComputer Algebra in Scientific Computing10.1007/978-3-031-69070-9_14(236-251)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-69070-9_14
Jazar KKry P(2023)Temporal Set Inversion for Animated ImplicitsACM Transactions on Graphics10.1145/359244842:4(1-18)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592448
Forets MSchilling C(2023)The Inverse Problem for Neural NetworksBridging the Gap Between AI and Reality10.1007/978-3-031-46002-9_14(241-255)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-46002-9_14
Rutenkolk K(2023)Extending Modelchecking with ProB to Floating-Point Numbers and Hybrid SystemsRigorous State-Based Methods10.1007/978-3-031-33163-3_27(366-370)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-33163-3_27
Araya ICampusano JAliquintui D(2022)Nonlinear biobjective optimization: improvements to interval branch & bound algorithmsJournal of Global Optimization10.1007/s10898-019-00768-z75:1(91-110)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s10898-019-00768-z
Jeangoudoux CDarulova ELauter CCadar CZhang X(2021)Interval constraint-based mutation testing of numerical specificationsProceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3460319.3464808(388-399)Online publication date: 11-Jul-2021
https://dl.acm.org/doi/10.1145/3460319.3464808
Araya IAliquintui DArdiles FLobo B(2021)Nonlinear biobjective optimization: improving the upper envelope using feasible line segmentsJournal of Global Optimization10.1007/s10898-021-00991-779:2(503-520)Online publication date: 5-Feb-2021
https://dl.acm.org/doi/10.1007/s10898-021-00991-7
Kochdumper NAlthoff MAmes ASeshia SDeshmukh J(2020)Reachability analysis for hybrid systems with nonlinear guard setsProceedings of the 23rd International Conference on Hybrid Systems: Computation and Control10.1145/3365365.3382194(1-10)Online publication date: 22-Apr-2020
https://dl.acm.org/doi/10.1145/3365365.3382194
Show More Cited By

View Options

View options

Get Access

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents