[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Interval Branch-and-Bound algorithms for optimization and constraint satisfaction: a survey and prospects

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

Interval Branch and Bound algorithms are used to solve rigorously continuous constraint satisfaction and constrained global optimization problems. In this paper, we explain the basic principles behind interval Branch and Bound algorithms. We detail the main components and describe issues that should be considered to improve the efficiency of the algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. or an atomic box containing a feasible point.

  2. By using appropriate preconditioners, the contractor can be used for contracting certain coordinates, even for some large boxes and in some singular cases [56].

  3. Actually, 3BCID enforces CID consistency [119], a slightly stronger one.

  4. Example from  [61].

References

  1. Araya, I., Neveu, B., Trombettoni, G.: Exploiting common subexpressions in numerical CSPs. In: Principles and Practice of Constraint Programming (CP 2008), pp. 342–357. Springer (2008)

  2. Araya, I., Neveu, B., Trombettoni, G.: An interval extension based on occurrence grouping. Computing 94(2–4), 173–188 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  3. Araya, I., Reyes, V., Oreallana, C.: More smear-based variable selection heuristics for NCSPs. In: International Conference on Tools with Artificial Intelligence (ICTAI 2013), pp. 1004–1011. IEEE (2013)

  4. Araya, I., Trombettoni, G., Neveu, B.: A contractor based on convex interval Taylor. In: Proceedings of CPAIOR, LNCS 7298, pp. 1–16 (2012)

  5. Araya, I., Trombettoni, G., Neveu, B., Chabert, G.: Upper bounding in inner regions for global optimization under inequality constraints. J. Glob. Optim. 60, 145–164 (2014). doi:10.1007/s10898-014-0145-7

  6. Araya, I., Trombettoni, G., Neveu, B., et al.: Exploiting monotonicity in interval constraint propagation. In: AAAI (2010)

  7. Baharev, A., Achterberg, T., Rév, E.: Computation of an extractive distillation column with affine arithmetic. AIChE J. 55(7), 1695–1704 (2009)

    Article  Google Scholar 

  8. Beck, J.C., Prosser, P., Wallace, R.J.: Trying again to fail-first. In: Recent Advances in Constraints, pp. 41–55. Springer (2005)

  9. Belotti, P.: Couenne, a users manual (2013). http://www.coin-or.org/Couenne/

  10. Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24(4–5), 597–634 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.F.: Revising hull and box consistency. In: International Conference on Logic Programming. Citeseer (1999)

  12. Bessiere, C., Régin, J.C.: MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In: Principles and Practice of Constraint Programming (CP96), pp. 61–75. Springer (1996)

  13. Bliek, C.: Computer methods for design automation. Ph.D. thesis, Massachusetts Institute of Technology (1992)

  14. Bournez, O., Maler, O., Pnueli, A.: Orthogonal polyhedra: Representation and computation. In: Hybrid Systems: Computation and Control, pp. 46–60. Springer (1999)

  15. Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: ECAI, vol. 16, p. 146 (2004)

  16. Brélaz, D.: New methods to color the vertices of a graph. Commun. ACM 22(4), 251–256 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  17. Carrizosa, E., Hansen, P., Messine, F.: Improving interval analysis bounds by translations. J. Glob. Optim. 29(2), 157–172 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  18. Casado, L., Martinez, J., García, I.: Experiments with a new selection criterion in a fast interval optimization algorithm. J. Glob. Optim. 19(3), 247–264 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  19. Cauchy, A.: Méthode générale pour la résolution des systemes déquations simultanées. C. R. Sci. Paris 25(1847), 536–538 (1847)

    Google Scholar 

  20. Ceberio, M., Granvilliers, L.: Horner’s rule for interval evaluation revisited. Computing 69(1), 51–81 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  21. Ceberio, M., Granvilliers, L.: Solving nonlinear equations by abstraction, Gaussian elimination, and interval methods. In: Frontiers of Combining Systems, pp. 117–131. Springer (2002)

  22. Ceberio, M., Kreinovich, V.: Greedy algorithms for optimizing multivariate Horner schemes. ACM SIGSAM Bull. 38(1), 8–15 (2004)

    Article  Google Scholar 

  23. Chabert, G., Jaulin, L.: Contractor programming. Artif. Intell. 173(11), 1079–1100 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  24. Chenouard, R., Goldsztejn, A., Jermann, C., et al.: Search strategies for an anytime usage of the branch and prune algorithm. In: IJCAI, pp. 468–473 (2009)

  25. Comba, J., Stolfi, J.: Affine arithmetic and its applications to computer graphics. In: Proceedings of SIBGRAPI’93—VI Simpósio Brasileiro de Computação Gráfica e Processamento de Imagens, pp. 9–18 (1993)

  26. Csendes, T., Ratz, D.: Subdivision direction selection in interval methods for global optimization. SIAM J. Numer. Anal. 34(3), 922–938 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  27. De Figueiredo, L.H., Stolfi, J.: Affine arithmetic: concepts and applications. Numer. Algorithms 37(1–4), 147–158 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  28. Demidovitch, B., Maron, I., Polonski, V.: Eléments de calcul numérique. Mir (1973)

  29. Drud, A.S.: CONOPT: a large-scale GRG code. ORSA J. Comput. 6(2), 207–216 (1994)

    Article  MATH  Google Scholar 

  30. Du, K., Kearfott, R.B.: The cluster problem in multivariate global optimization. J. Glob. Optim. 5(3), 253–265 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  31. Duran, M.A., Grossmann, I.E.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Program. 36(3), 307–339 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  32. Eldon, H., William, W.: Global optimization using interval analysis (1992)

  33. Faltings, B.V., Lottaz, C., et al.: Collaborative design using solution spaces (2000)

  34. Felner, A., Kraus, S., Korf, R.E.: KBFS: K-best-first search. Ann. Math. Artif. Intell. 39(1–2), 19–39 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  35. Floudas, C.A., Pardalos, P.M.: Encyclopedia of Optimization, vol. 1. Springer Science & Business Media, Berlin (2008)

    MATH  Google Scholar 

  36. Frank, M., Wolfe, P.: An algorithm for quadratic programming. Nav. Res. Logist. Q. 3(1–2), 95–110 (1956)

    Article  MathSciNet  Google Scholar 

  37. Frommer, A., Lang, B.: Existence tests for solutions of nonlinear equations using Borsuk’s theorem. SIAM J. Numer. Anal. 43(3), 1348–1361 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  38. Fünfzig, C., Michelucci, D., Foufou, S.: Nonlinear systems solver in floating-point arithmetic using LP reduction. In: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling, pp. 123–134. ACM (2009)

  39. Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM J. Optim. 12(4), 979–1006 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  40. Goldsztejn, A., Granvilliers, L.: A new framework for sharp and efficient resolution of NCSP with manifolds of solutions. Constraints 15(2), 190–212 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  41. Goldsztejn, A., Lebbah, Y., Michel, C., Rueher, M.: Revisiting the upper bounding process in a safe branch and bound algorithm. In: Principles and Practice of Constraint Programming (CP 2008), pp. 598–602. Springer (2008)

  42. Golomb, S.W., Baumert, L.D.: Backtrack programming. J. ACM (JACM) 12(4), 516–524 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  43. Granvilliers, L.: Adaptive bisection of numerical CSPs. In: Principles and Practice of Constraint Programming (2012), pp. 290–298. Springer (2012)

  44. Granvilliers, L., Goldsztejn, A.: A branch-and-bound algorithm for unconstrained global optimization. In: Proceedings of the 14th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (SCAN) (2010)

  45. Hammer, R., Hocks, M., Kulisch, U., Ratz, D.: Numerical toolbox for verified computing I (1993)

  46. Hansen, E.: Interval arithmetic in matrix computations, Part I. J Soc Ind. Appl. Math. Ser. B Numer. Anal. 2(2), 308–320 (1965)

    Article  MATH  Google Scholar 

  47. Hansen, E.: Global optimization using interval analysis: the multi-dimensional case. Numer. Math. 34(3), 247–270 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  48. Hansen, E.: Bounding the solution of interval linear equations. SIAM J. Numer. Anal. 29(5), 1493–1503 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  49. Hansen, E.: Global Optimization Using Interval Analysis. Marcel Dekker, New York (1992)

    MATH  Google Scholar 

  50. Hansen, E., Walster, G.W.: Global Optimization Using Interval Analysis: Revised and Expanded, vol. 264. CRC Press, Boca Raton (2003)

    Google Scholar 

  51. Ishii, D., Goldsztejn, A., Jermann, C.: Interval-based projection method for under-constrained numerical systems. Constraints 17(4), 432–460 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  52. Jaggi, M.: Revisiting Frank–Wolfe: projection-free sparse convex optimization. In: Proceedings of the 30th International Conference on Machine Learning (ICML-13), pp. 427–435 (2013)

  53. Jaulin, L.: Localization of an underwater robot using interval constraint propagation. In: Principles and Practice of Constraint Programming (CP 2006), pp. 244–255. Springer (2006)

  54. John, F.: Extremum problems with inequalities as subsidiary conditions. In: Studies and Essays Presented to R. Courant on his 60th Birthday (Jan. 8, 1948), pp. 187–204. Interscience, New York (1948)

  55. Karush, W.: Minima of functions of several variables with inequalities as side constraints. Ph.D. thesis, Masters thesis, Dept. of Mathematics, University of Chicago (1939)

  56. Kearfott, R.B.: Preconditioners for the interval Gauss–Seidel method. SIAM J. Numer. Anal. 27(3), 804–822 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  57. Kearfott, R.B.: An interval branch and bound algorithm for bound constrained optimization problems. J. Glob. Optim. 2(3), 259–280 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  58. Kearfott, R.B.: Discussion and empirical comparisons of linear relaxations and alternate techniques in validated deterministic global optimization. Optim. Methods Softw. 21(5), 715–731 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  59. Kearfott, R.B.: GlobSol user guide. Optim. Methods Softw. 24(4–5), 687–708 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  60. Kearfott, R.B.: On rigorous upper bounds to a global optimum. J. Glob. Optim. 59(2–3), 459–476 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  61. Kearfott, R.B., Hongthong, S.: Validated linear relaxations and preprocessing: some experiments. SIAM J. Optim. 16(2), 418–433 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  62. Kearfott, R.B., Novoa III, M.: Algorithm 681: INTBIS, a portable interval Newton/bisection package. ACM Trans. Math. Softw. (TOMS) 16(2), 152–157 (1990)

    Article  MATH  Google Scholar 

  63. Kearfott, R.B., Walster, G.W.: Symbolic preconditioning with Taylor models: some examples. Reliab. Comput. 8(6), 453–468 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  64. Kieffer, M.: Distributed bounded-error parameter and state estimation in networks of sensors. In: Numerical Validation in Current Hardware Architectures, pp. 189–202. Springer (2009)

  65. Kieffer, M., Walter, E.: Centralized and distributed source localization by a network of sensors using guaranteed set estimation. In: 2006 IEEE International Conference on Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings, vol. 4, pp. IV–IV. IEEE (2006)

  66. Kolev, L.V.: Use of interval slopes for the irrational part of factorable functions. Reliab. Comput. 3(1), 83–93 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  67. Krawczyk, R.: Newton-algorithmen zur bestimmung von nullstellen mit fehlerschranken. Computing 4(3), 187–201 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  68. Kueviakoe, I., Lambert, A., Tarroux, P.: Comparison of interval constraint propagation algorithms for vehicle localization. J. Softw. Eng. Appl. 5, 157 (2013)

    Article  Google Scholar 

  69. Lagouanelle, J.L., Soubry, G.: Optimal multisections in interval branch-and-bound methods of global optimization. J. Glob. Optim. 30(1), 23–38 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  70. Lebbah, Y.: Icos: a branch and bound based solver for rigorous global optimization. Optim. Methods Softw. 24(4–5), 709–726 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  71. Lebbah, Y., Michel, C., Rueher, M.: An efficient and safe framework for solving optimization problems. J. Comput. Appl. Math. 199(2), 372–377 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  72. Lhomme, O.: Consistency techniques for numeric CSPs. In: IJCAI, vol. 93, pp. 232–238. Citeseer (1993)

  73. Liberti, L.: Writing global optimization software. In: Global Optimization, pp. 211–262. Springer (2006)

  74. Mackworth, A.K.: Consistency in networks of relations. Artif. Intell. 8(1), 99–118 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  75. Makino, K., Berz, M.: Taylor models and other validated functional inclusion methods. Int. J. Pure Appl. Math. 4(4), 379–456 (2003)

    MathSciNet  MATH  Google Scholar 

  76. Maranas, C.D., Floudas, C.A.: Finding all solutions of nonlinearly constrained systems of equations. J. Glob. Optim. 7(2), 143–182 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  77. Markót, M.C., Fernandez, J., Casado, L.G., Csendes, T.: New interval methods for constrained global optimization. Math. Program. 106(2), 287–318 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  78. Markót, M.C., Schichl, H.: Bound constrained interval global optimization in the COCONUT environment. J. Glob. Optim. 60(4), 751–776 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  79. McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems. Math. Program. 10(1), 147–175 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  80. Merlet, J.P.: Optimal design for the micro parallel robot MIPS. In: IEEE International Conference on Robotics and Automation, 2002. Proceedings of ICRA’02, vol. 2, pp. 1149–1154. IEEE (2002)

  81. Merlet, J.P.: Interval analysis for certified numerical solution of problems in robotics. Int. J. Appl. Math. Comput. Sci. 19(3), 399–412 (2009)

    Article  MATH  Google Scholar 

  82. Messine, F.: Extentions of affine arithmetic: application to unconstrained global optimization. J. Univers. Comput. Sci. 8(11), 992–1015 (2002)

    MathSciNet  MATH  Google Scholar 

  83. Messine, F.: Deterministic global optimization using interval constraint propagation techniques. RAIRO Oper. Res. 38(04), 277–293 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  84. Messine, F.: A deterministic global optimization algorithm for design problems. In: Essays and Surveys in Global Optimization, pp. 267–294. Springer (2005)

  85. Messine, F., Nogarede, B., Lagouanelle, J.L.: Optimal design of electromechanical actuators: a new method based on global optimization. IEEE Trans. Magn. 34(1), 299–308 (1998)

    Article  Google Scholar 

  86. Messine, F., Touhami, A.: A general reliable quadratic form: an extension of affine arithmetic. Reliab. Comput. 12(3), 171–192 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  87. Meyer, C.A., Floudas, C.A.: Convex envelopes for edge-concave functions. Math. Program. 103(2), 207–224 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  88. Michel, L., Van Hentenryck, P.: Activity-based search for black-box constraint programming solvers. In: Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems, pp. 228–243. Springer (2012)

  89. Misener, R., Floudas, C.A.: ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations. J. Glob. Optim. 59(2–3), 503–526 (2013)

    MathSciNet  MATH  Google Scholar 

  90. Moore, R.: Interval Analysis, vol. 60 (1966)

  91. Mourad, F., Snoussi, H., Abdallah, F., Richard, C.: Anchor-based localization via interval analysis for mobile ad-hoc sensor networks. IEEE Trans. Signal Process. 57(8), 3226–3239 (2009)

    Article  MathSciNet  Google Scholar 

  92. Nataraj, P., Patil, M.D.: Reliable and robust automated synthesis of QFT controller for nonlinear magnetic levitation system using interval constraint satisfaction techniques. In: Constraint Programming and Decision Making, pp. 131–135. Springer (2014)

  93. Nataraj, P., Tharewal, S.: An interval analysis algorithm for automated controller synthesis in QFT designs. J. Dyn. Syst. Meas. Contr. 129(3), 311–321 (2007)

    Article  Google Scholar 

  94. Neumaier, A., Shcherbina, O.: Safe bounds in linear and mixed-integer linear programming. Math. Program. 99(2), 283–296 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  95. Neveu, B., Trombettoni, G., et al.: Adaptive constructive interval disjunction. In: International Conference on Tools with Artificial Intelligence (ICTAI), pp. 900–906 (2013)

  96. Ninin, J., Messine, F., Hansen, P.: A reliable affine relaxation method for global optimization. 4OR (2014). doi:10.1007/s10288-014-0269-0

  97. Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables, vol. 30. Siam, Philadelphia (2000)

    Book  MATH  Google Scholar 

  98. Patil, M.D., Nataraj, P.: QFT prefilter design for multivariable systems using interval constraint satisfaction technique. J. Control Theory Appl. 11(4), 529–537 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  99. Ramdani, N., Meslem, N., Candau, Y.: Reachability of uncertain nonlinear systems using a nonlinear hybridization. In: Hybrid Systems: Computation and Control, pp. 415–428. Springer, Berlin (2008)

  100. Ramdani, N., Nedialkov, N.S.: Computing reachable sets for uncertain nonlinear hybrid systems using interval constraint-propagation techniques. Nonlinear Anal. Hybrid Syst. 5(2), 149–162 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  101. Ratschek, H., Rokne, J.: New Computer Methods for Global Optimization. Horwood, Chichester (1988)

    MATH  Google Scholar 

  102. Ratz, D.: Automatische ergebnisveri kation bei globalen optimierungsproblemen. Ph.D. thesis, Dissertation, Universit at Karlsruhe (1992)

  103. Refalo, P.: Impact-based search strategies for constraint programming. In: Principles and Practice of Constraint Programming (CP 2004), pp. 557–571. Springer (2004)

  104. Reynet, O., Voisin, O., Jaulin, L.: Anchor-based localization using distributed interval contractors (2011)

  105. Roy, J.M.: Singularities in Deterministic Global Optimization. University of Louisiana at Lafayette (2010)

  106. Ryoo, H.S., Sahinidis, N.V.: A branch-and-reduce approach to global optimization. J. Glob. Optim. 8(2), 107–138 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  107. Sahinidis, N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8(2), 201–205 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  108. Sam-Haroud, D., Faltings, B.: Consistency techniques for continuous constraints. Constraints 1(1–2), 85–118 (1996)

    Article  MathSciNet  Google Scholar 

  109. Schichl, H., Neumaier, A.: Exclusion regions for systems of equations. SIAM J. Numer. Anal. 42(1), 383–408 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  110. Schichl, H., Neumaier, A.: Interval analysis on directed acyclic graphs for global optimization. J. Glob. Optim. 33(4), 541–562 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  111. Shectman, J.P., Sahinidis, N.V.: A finite algorithm for global minimization of separable concave programs. J. Glob. Optim. 12(1), 1–36 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  112. Smith, B.M., Grant, S.A.: Trying harder to fail first. Research report series/University of Leeds, School of Computer Studies LU SCS RR (1997)

  113. Soares, R.D.P.: Finding all real solutions of nonlinear systems of equations with discontinuities by a modified affine arithmetic. Comput. Chem. Eng. 48, 48–57 (2013)

    Article  Google Scholar 

  114. Stamatatos, E., Stergiou, K.: Learning how to propagate using random probing. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pp. 263–278. Springer (2009)

  115. Stergiou, K.: Heuristics for dynamically adapting propagation in constraint satisfaction problems. AI Commun. 22(3), 125–141 (2009)

    MathSciNet  MATH  Google Scholar 

  116. Tapia, R.: The Kantorovich theorem for Newton’s method. Am. Math. Mon. 78(4), 389–392 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  117. Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, vol. 65. Springer, Berlin (2002)

    MATH  Google Scholar 

  118. Trombettoni, G., Araya, I., Neveu, B., Chabert, G.: Inner regions and interval linearizations for global optimization. In: AAAI, pp. 99–104 (2011)

  119. Trombettoni, G., Chabert, G.: Constructive interval disjunction. In: Principles and Practice of Constraint Programming (CP 2007), pp. 635–650. Springer (2007)

  120. Van Hentenryck, P., Michel, L., Deville, Y.: Numerica: A Modeling Language for Global Optimization. MIT Press, Cambridge (2003)

    Google Scholar 

  121. Vu, X.H., Sam-Haroud, D., Faltings, B.: Combining multiple inclusion representations in numerical constraint propagation. In: International Conference on Tools with Artificial Intelligence (ICTAI 2004), pp. 458–467. IEEE (2004)

  122. Vu, X.H., Sam-Haroud, D., Silaghi, M.C.: Approximation techniques for non-linear problems with continuum of solutions. In: Abstraction, Reformulation, and Approximation, pp. 224–241. Springer (2002)

  123. Vu, X.H., Schichl, H., Sam-Haroud, D.: Using directed acyclic graphs to coordinate propagation and search for numerical constraint satisfaction problems. In: International Conference on Tools with Artificial Intelligence (ICTAI 2004), pp. 72–81. IEEE (2004)

  124. Yamamura, K., Kawata, H., Tokue, A.: Interval solution of nonlinear equations using linear programming. BIT Numer. Math. 38(1), 186–199 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  125. Yannou, B., Simpson, T.W., Barton, R.R.: Towards a conceptual design explorer using metamodeling approaches and constraint programming. In: ASME 2003 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, pp. 605–614. American Society of Mechanical Engineers (2003)

Download references

Acknowledgments

This work is supported by the Fondecyt Project 1120781.

Author information

Authors and Affiliations

  1. Escuela Informática, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2950, V Región, Chile

    Ignacio Araya

  2. Depto. Informática, Universidad Técnica Federico Santa María, Avenida España, 1680, V Región, Chile

    Victor Reyes

Authors
  1. Ignacio Araya
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Victor Reyes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ignacio Araya.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Araya, I., Reyes, V. Interval Branch-and-Bound algorithms for optimization and constraint satisfaction: a survey and prospects. J Glob Optim 65, 837–866 (2016). https://doi.org/10.1007/s10898-015-0390-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-015-0390-4

Keywords

Search

Navigation