An introduction to interval-based constraint processing

• Autorzy: Renker G. , Ahriz H.
• Języki publikacji: EN

Abstrakty

EN

Constraint programming is often associated with solving problems over finite domains.Many applications in engineering, CAD and design, however, require solving problems over continuous domains. While simple constraint solvers can solve linear constraintswith the inaccuracy of floating-point arithmetic, methods based on interval arithmetic allow exact solutions over a much wider range of problems. applications of interval-based programming extend the range of solvable problems from non-linear polynomials up to those involving ordinary differential equations. In this text, we give an introduction to current approaches, metchods and implementations of interval-based constraint programming and solving. Special care is taken to provide a uniform and consistent notation, since the literature in this field employs many seemingly different, but yet conceptually related, notations and terminology.

Słowa kluczowe

EN

constraint programming; interval-based computation; interval consistency techniques

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2006
• Tom: Vol. 16, no. 2
• Strony: 161--190
• Opis fizyczny: Bibliogr. 53 poz., rys., tab., wzory

Twórcy

autor

Renker G.

autor

Ahriz H.

• School of computing, The Robert Gordon University, Aberdeen, UK,

Bibliografia

• [1] K. R. APT: From Chaotic Iteration to Constraint propagation. Proc.24th Int.Colloquium on Automata, Languages and Programming (ICALP’97), P. Degano, R. Gorrieri, and A. Marchetti-Spaccamela, (Eds), 1256 LNCS, Springer-Verlag, (1997), 36-55.
• [2] K. R. APT: Principles of Constraint Programming. Cambridge Univ. Press, 2003.
• [3] R. BARTÁK: Constraint Programming: In Pursuit of the Holy Grail. Proc. WDS99 (invited lecture), Prague, (1999).
• [4] F. BENHAMOU: Interval Constraint Logic Programming. Constraint Programming: Basics and Trends, Châtillon Spring School, Chatillon-sur-Seine, France, 1994, Selected Papers, A. Podelski, (Ed), 910 LNCS, Springer, (1995), 1-21.
• [5] F. BENHAMOU Heterogeneous Constraint Solving. Proc. ALP'96, Algebraic and Logic Programming, 5th Int. Cant. Aachen, Germany, M. Harms and M. Rodriquez-Artalejo, (Eds), 1139 LNCS, Springer, (1996), 62-76.
• [6] F. BENHAMOU, P. CODOGNET, D. DIAZ, F. GOUALARD, and L. GRANVILLIERS: DecLIC 1.1b: User's Guide and Reference Manual. INRIA-Rocquencourt / LIFO-Orleans / IRIN-Nantes, 2003.
• [7] F. BENHAMOU, F. GOUALARD, L. GRANVILLIERS, and J.-F. PUGET: Revising Hull and Box Consistency. Proc. ICLP'99, D. D. Schreye, (Ed), MIT Press, (1999), 230-244.
• [8] F. BENHAMOU, D. MCALLESTER and P. V. HENTENRYCK: CLP(Intervals) Revisited. Proc. 1994 Int. Symp. on Logic Programming (ILPS-94), M. Bruynooghe, (Ed), MIT Press, (1994), 124-138.
• [9] F. BENHAMOU and W. J. OLDER, Applying Interval Arithmetic to Real, Integer, and Boolean Constraints. J. Logic Programming, 32(1) (1997), 1-24.
• [10] C. BLIEK, P. SPELLUCCI, L. N. VICENTE, A. NEUMAIER, L. GRANVILLIERS, E. MONFROY, F. BENHAMOU, E. HUENS, P. V. HENTENRYCK, D. SAMHAROUD and B. FALTINGS: Algorithms for Solving Nonlinear Constrained and Optimization Problems: The State of the Art. Project Report DI, COCONUT Project, 2001.
• [11] P. BRISSET, H. E. SAKKOUT, T. FRUHWIRTH, C. GERVET, W. HARVEY, M. MEIER, S. NOVELLO, T. L. PROVOST, J. SCHIMPF, K. SHEN, and M. WALLACE: ECLiPSe Constraint Library Manual, release 5.8 ed. International Computers Limited and Imperial College, London, October 2004.
• [12] B. D. BUNDAY: Basic Linear Programming. Edward Arnold Publishers Ltd., 1984.
• [13] P. CODOGNHT and D. DIAZ: Compiling Constraints in clp(FD). J. Logic Progmmining, 27(3) (1996), 185-226.
• [14] H. COLLAVIZZA, F. DELOBEL and M. RUEHER: Comparing Partial Consistencies. Reliable Computing, 5(3) (1999), 213-228.
• [15] A. COLMERAUER: An Introduction to Prolog III. CACM 33, (1990), 69-90.
• [16] A. COLMERAUER: Naive Solving of Non-Linear Constraints. Constraint Logic Programming: Selected Research, F. Benhamou and A. Colmerauer, (Eds), MIT Press, (1993), 89-112.
• [17] D. DIAZ: GNU Prolog 1.2.16 User Manual, 1.7 ed. Free Software Foundation, (2002).
• [18] E. C. FREUDER: Synthesizing Constraint Expressions. Communications of the ACM, 21(11) (1978), 958-966.
• [19] D. GOLDBERG: What Every Computer Scientist Should Know About Floating-Point Arithmetic. ACM Computing Surveys (CSUR), 23(1) (1991), 5-48.
• [20] F. GOUALARD: Towards Good C++ Interval Libraries: Tricks and Traits. Proc. 4th Asian Symposium on Computer Mathematics (ASCM), Thailand, (2000).
• [21] F. GOUALARD, F. BENHAMOU and L. GRANVILLIERS: An Extension of the WAM for Hybrid Interval Solvers. J. Functional and Logic Programming, (1999).
• [22] L. GRANVILLIERS: On the Combination of Interval Constraint Solvers. Reliable Computing, 7(6) (2001), 467-483.
• [23] L. GRANVILLIERS: RealPaver User's Manual: Solving Nonlinear Constraints by Interval Computations, for RealPaver Version 0.3. Institut de Recherche en Informatique de Nantes, France, 2003.
• [24] L. GRANVILLIERS and E. MONFROY: Declarative Modelling of Constraint Propagation Strategies. Proc. First Biennial Int. Conf. on Advances in Information Systems, Turkey, T. M. Yakhno, (Ed), 1909 LNCS, Springer, (2000), 201-215.
• [25] L. GRANVILLIERS, E. MONFROY and F. BENHAMOU: Symbolic-Interval Cooperation in Constraint Programming. Proc. Int. SyI71. Symbolic and Algebraic Computation (ISSAC'2001), ACM Press, (2001), 150-166.
• [26] N. C. HEINTZE, J. JAFFAR, S. MICHAYLOV, P. J. STUCKEY and R. H. C. YAP: The CLP(R) Programmer's Manual, Version 1.2. IBM Thomas J. Watson Research Center (Yorktown Heights, NY, USA), 1992.
• [27] P. V. HENTENRYCK, D. MCALLESTER and D. KAPUR: Solving Polynomial Sys- Morgan Kartems Using a Branch and Prune Approach. SIAM J. Numerical Analysis, 34(2) (1997), 797-827.
• [28] P. V. HENTENRYCK, L. MICHEL and F. BENHAMOU: Newton - Constraint Programming over Nonlinear Constraints. Science of Computer Programming, 30(1-2) (1998), 83-118.
• [29] P. V. HENTENRYCK, L. MICHEL and Y. DEVILLE: A Modeling Language for Global Optimization. MIT Press, 1997.
• [30] T. HICKEY, Q. JU and M. H. VAN EMDEN: Interval Arithmetic: From Principles to Implementation. Journal of the ACM (JACM), 48(5) (2001), 1038-1068.
• [31] T. J. HICKEY: Analytic Constraint Solving and Interval Arithmetic. Proc. 27th ACM SIGPLAN-SIGACT Symp. Principles Of Programming Languages, (2000), 338-351.
• [32] T. J. HICKEY: CLIP: A CLP(Intervals) Dialect for Metalevel Constraint Solving. Proc. Second Int. Workshop on Practical Aspects of Declarative Languages, Boston, MA, USA, E. Pontelli and V. S. Costa, (Eds), 1753 LNCS, Springer, (2000), 200-214.
• [331 T. J. HICKEY, M. H. VAN EMDEN and H. WU: A Unified Framework for Interval Constraints and Interval Arithmetic. Proc. Principles and Practice of Constraint Programming - CP98, 4th Int. Conf, Pisa, Italy, M. J. Maher and J.-F. Puget, (Eds), 1520 LNCS, Springer, (1998), 250-264.
• [34] J. HOLLMAN and L. LANGEMYR: Algorithms for Non-linear Algebraic Constraints. Constraint Logic Programming: Selected Research, F. Benhamou and A. Colmerauer, (Eds), MIT Press, (1993), 113-131.
• [35] H. HONG: RISC-CLP(Real): Logic Programming with Non-linear Constraints over the Reals. Constraint Logic Programming: Selected Research, F. Benhamou and A. Colmerauer, (Eds), MIT Press, (1993), 133-159.
• [36] E. HYVONEN: Constraint Reasoning Based on Interval Arithmetic. Proc. 11th Int. Joint Conf on Artificial Intelligence (IJCAI-89), (1989), N. S. Sridharan, (Ed), 2, Morgan Kaufmann, 1193-1198.
• [37] ILOG. Ilog Solver 6.0, User's Manual. France, 2003.
• [38] J. JAFFAR, S. MICHAYLOV, P. J. STUCKEY and R.H.C. YAP: The CLP(R) Language and System. ACM Trans. Programming Languages and Systems (TOPLAS), 14(3) (1992), 339-395.
• [39] O. LHOMME: Consistency Techniques for Numeric CSPs. Proc. 13th Int. Joint Conf on Artificial Intelligence (IJCAI-93), Chambery, France, R. Bajcsy, (Ed), 1, Morgan Kaufmann, (1993), 232-238.
• [40] A. K. MACKWORTH: Consistency in Networks of Relations. Artificial Intelligence, 8(1) (1977), 99-118.
• [41] L. M ICHEL and P. V. HENTENRYCK: Helios: A modeling language for global optimization and its implementation in Newton. Theoretical Computer Science, 173(1) (1997), 3-48.
• [42] E. MONFROY: Grobner Bases: Strategies and Applications. Proc. First Int. Coq: on Artificial Intelligence and Symbolic Mathematical Computation AISMC- I , Karlsruhe, Germany, (1992), J. Calmet and J. A. Campbell, (Eds), 737 LNCS, Springer, (1993), 133-151.
• [43] E. MONFROY, M. RUSINOWITCH and R. SCHOTT: Implementing Non-Linear Constraints with Cooperative Solvers. Proc. ACM Symposium on Applied Computing (SAC-96), K. M. George, J. H. Carroll, D. Oppenheim, and J. Hightower, (Eds), ACM Press, (1996), 63-72.
• [44] R. E. MOORE: Interval Analysis. Series in Automatic Computation, Prentice-Hall, 1966.
• [45] G. A. NARBONI: From Prolog III to Prolog IV: The Logic of Constraint Programming Revisited. CONSTRAINTS, 4(4) (1999), 313-335.
• [46] A. NEUMAIER: Complete Search In Continuous Global Optimization And Constraint Satisfaction. Acta Numerics, 13 (2004), 271-369.
• [47] A. NEUMAIER and 0. SHCHERBINA: Safe bounds in linear and mixed-integer programming. Mathematical Programming, 99(2) (2004), 283-296.
• [48] W. OLDER and F. BENHAMOU: Programming in CLP(BNR). Proc. PPCP 1993: Newport, Rhode Island, (1993), 228-238.
• [49] J.-F. PUGET and P. V. HENTENRYCK: A Constraint Satisfaction Approach to a Circuit Design Problem. J. Global Optimization, 13(1) (1998), 75-93.
• [50] K. SAKAI and A. AIBA: CAL: A Theoretical Background of Constraint Logic Programming and its Applications. J. Symbolic Computation, 8(6) (1989), 589-603.
• [51] SUN MICROSYSTEMS. Interval Arithmetic Solves Nonlinear Problems While Providing Guaranteed Results. Sun Feature Stories, April 2001. http://wwws.sun.com/software/sundev/news/features/intervals .html.
• [52] A. TARSKI: A Decision Method for Elementary Algebra and Geometry. Second revised ed. University of California Press: Berkeley & Los Angeles, (1951), p. iii. 63ff.
• [53] M. H. VAN EMDEN: Algorithmic Power from Declarative Use of Redundant Constraints. CONSTRAINTS, 4(4) (1999), 363-381.