×

zbMATH — the first resource for mathematics

Interval branch-and-bound algorithms for optimization and constraint satisfaction: a survey and prospects. (English) Zbl 1353.90113
Summary: 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.

MSC:
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
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) · Zbl 1136.90521
[2] Araya, I; Neveu, B; Trombettoni, G, An interval extension based on occurrence grouping, Computing, 94, 173-188, (2012) · Zbl 1238.65039
[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) · Zbl 0841.90115
[4] Araya, I., Trombettoni, G., Neveu, B.: A contractor based on convex interval Taylor. In: Proceedings of CPAIOR, LNCS 7298, pp. 1-16 (2012) · Zbl 1180.90314
[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 · Zbl 1312.90057
[6] Araya, I., Trombettoni, G., Neveu, B., et al.: Exploiting monotonicity in interval constraint propagation. In: AAAI (2010) · Zbl 1301.90075
[7] Baharev, A; Achterberg, T; Rév, E, Computation of an extractive distillation column with affine arithmetic, AIChE J., 55, 1695-1704, (2009)
[8] Beck, J.C., Prosser, P., Wallace, R.J.: Trying again to fail-first. In: Recent Advances in Constraints, pp. 41-55. Springer (2005) · Zbl 1078.68743
[9] Belotti, P.: Couenne, a users manual (2013). http://www.coin-or.org/Couenne/ · Zbl 0341.68061
[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, 597-634, (2009) · Zbl 1179.90237
[11] Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.F.: Revising hull and box consistency. In: International Conference on Logic Programming. Citeseer (1999) · Zbl 1309.90101
[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) · Zbl 0442.65052
[13] Bliek, C.: Computer methods for design automation. Ph.D. thesis, Massachusetts Institute of Technology (1992) · Zbl 0908.65038
[14] Bournez, O., Maler, O., Pnueli, A.: Orthogonal polyhedra: Representation and computation. In: Hybrid Systems: Computation and Control, pp. 46-60. Springer (1999) · Zbl 0947.68154
[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, 251-256, (1979) · Zbl 0394.05022
[17] Carrizosa, E; Hansen, P; Messine, F, Improving interval analysis bounds by translations, J. Glob. Optim., 29, 157-172, (2004) · Zbl 1116.90388
[18] Casado, L; Martinez, J; García, I, Experiments with a new selection criterion in a fast interval optimization algorithm, J. Glob. Optim., 19, 247-264, (2001) · Zbl 0976.90079
[19] Cauchy, A, Méthode générale pour la résolution des systemes déquations simultanées, C. R. Sci. Paris, 25, 536-538, (1847)
[20] Ceberio, M; Granvilliers, L, Horner’s rule for interval evaluation revisited, Computing, 69, 51-81, (2002) · Zbl 1017.65013
[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) · Zbl 1057.68110
[22] Ceberio, M; Kreinovich, V, Greedy algorithms for optimizing multivariate horner schemes, ACM SIGSAM Bull., 38, 8-15, (2004) · Zbl 1343.65049
[23] Chabert, G; Jaulin, L, Contractor programming, Artif. Intell., 173, 1079-1100, (2009) · Zbl 1191.68628
[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) · Zbl 1080.65041
[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) · Zbl 1203.65086
[26] Csendes, T; Ratz, D, Subdivision direction selection in interval methods for global optimization, SIAM J. Numer. Anal., 34, 922-938, (1997) · Zbl 0873.65063
[27] Figueiredo, LH; Stolfi, J, Affine arithmetic: concepts and applications, Numer. Algorithms, 37, 147-158, (2004) · Zbl 1074.65050
[28] Demidovitch, B., Maron, I., Polonski, V.: Eléments de calcul numérique. Mir (1973) · Zbl 1179.90265
[29] Drud, AS, CONOPT: a large-scale GRG code, ORSA J. Comput., 6, 207-216, (1994) · Zbl 0806.90113
[30] Du, K; Kearfott, RB, The cluster problem in multivariate global optimization, J. Glob. Optim., 5, 253-265, (1994) · Zbl 0824.90121
[31] Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339, (1986) · Zbl 0619.90052
[32] Eldon, H., William, W.: Global optimization using interval analysis (1992) · Zbl 1103.90092
[33] Faltings, B.V., Lottaz, C., et al.: Collaborative design using solution spaces (2000) · Zbl 0806.90113
[34] Felner, A; Kraus, S; Korf, RE, KBFS: K-best-first search, Ann. Math. Artif. Intell., 39, 19-39, (2003) · Zbl 1045.68046
[35] Floudas, C.A., Pardalos, P.M.: Encyclopedia of Optimization, vol. 1. Springer Science & Business Media, Berlin (2008) · Zbl 1156.90001
[36] Frank, M; Wolfe, P, An algorithm for quadratic programming, Nav. Res. Logist. Q., 3, 95-110, (1956)
[37] Frommer, A; Lang, B, Existence tests for solutions of nonlinear equations using borsuk’s theorem, SIAM J. Numer. Anal., 43, 1348-1361, (2005) · Zbl 1095.47057
[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) · Zbl 1179.90237
[39] Gill, PE; Murray, W; Saunders, MA, SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM J. Optim., 12, 979-1006, (2002) · Zbl 1027.90111
[40] Goldsztejn, A; Granvilliers, L, A new framework for sharp and efficient resolution of NCSP with manifolds of solutions, Constraints, 15, 190-212, (2010) · Zbl 1203.65086
[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) · Zbl 1343.65049
[42] Golomb, SW; Baumert, LD, Backtrack programming, J. ACM (JACM), 12, 516-524, (1965) · Zbl 0139.12305
[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) · Zbl 1203.65086
[45] Hammer, R., Hocks, M., Kulisch, U., Ratz, D.: Numerical toolbox for verified computing I (1993) · Zbl 0796.65001
[46] Hansen, E, Interval arithmetic in matrix computations, part I, J Soc Ind. Appl. Math. Ser. B Numer. Anal., 2, 308-320, (1965) · Zbl 0135.37303
[47] Hansen, E, Global optimization using interval analysis: the multi-dimensional case, Numer. Math., 34, 247-270, (1980) · Zbl 0442.65052
[48] Hansen, E, Bounding the solution of interval linear equations, SIAM J. Numer. Anal., 29, 1493-1503, (1992) · Zbl 0756.65035
[49] Hansen, E.: Global Optimization Using Interval Analysis. Marcel Dekker, New York (1992) · Zbl 0762.90069
[50] Hansen, E., Walster, G.W.: Global Optimization Using Interval Analysis: Revised and Expanded, vol. 264. CRC Press, Boca Raton (2003)
[51] Ishii, D; Goldsztejn, A; Jermann, C, Interval-based projection method for under-constrained numerical systems, Constraints, 17, 432-460, (2012) · Zbl 1309.90101
[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) · Zbl 1225.93026
[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) · Zbl 1022.65051
[56] Kearfott, RB, Preconditioners for the interval Gauss-Seidel method, SIAM J. Numer. Anal., 27, 804-822, (1990) · Zbl 0713.65037
[57] Kearfott, RB, An interval branch and bound algorithm for bound constrained optimization problems, J. Glob. Optim., 2, 259-280, (1992) · Zbl 0760.90085
[58] Kearfott, RB, Discussion and empirical comparisons of linear relaxations and alternate techniques in validated deterministic global optimization, Optim. Methods Softw., 21, 715-731, (2006) · Zbl 1112.90080
[59] Kearfott, RB, Globsol user guide, Optim. Methods Softw., 24, 687-708, (2009) · Zbl 1180.90314
[60] Kearfott, RB, On rigorous upper bounds to a global optimum, J. Glob. Optim., 59, 459-476, (2014) · Zbl 1301.90075
[61] Kearfott, RB; Hongthong, S, Validated linear relaxations and preprocessing: some experiments, SIAM J. Optim., 16, 418-433, (2005) · Zbl 1122.90075
[62] Kearfott, RB; Novoa, M, Algorithm 681: INTBIS, a portable interval Newton/bisection package, ACM Trans. Math. Softw. (TOMS), 16, 152-157, (1990) · Zbl 0900.65152
[63] Kearfott, RB; Walster, GW, Symbolic preconditioning with Taylor models: some examples, Reliab. Comput., 8, 453-468, (2002) · Zbl 1016.65041
[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) · Zbl 1299.93265
[66] Kolev, LV, Use of interval slopes for the irrational part of factorable functions, Reliab. Comput., 3, 83-93, (1997) · Zbl 0878.65036
[67] Krawczyk, R, Newton-algorithmen zur bestimmung von nullstellen mit fehlerschranken, Computing, 4, 187-201, (1969) · Zbl 0187.10001
[68] Kueviakoe, I; Lambert, A; Tarroux, P, Comparison of interval constraint propagation algorithms for vehicle localization, J. Softw. Eng. Appl., 5, 157, (2013)
[69] Lagouanelle, JL; Soubry, G, Optimal multisections in interval branch-and-bound methods of global optimization, J. Glob. Optim., 30, 23-38, (2004) · Zbl 1136.90521
[70] Lebbah, Y, Icos: a branch and bound based solver for rigorous global optimization, Optim. Methods Softw., 24, 709-726, (2009) · Zbl 1179.90265
[71] Lebbah, Y; Michel, C; Rueher, M, An efficient and safe framework for solving optimization problems, J. Comput. Appl. Math., 199, 372-377, (2007) · Zbl 1108.65065
[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) · Zbl 1100.90004
[74] Mackworth, AK, Consistency in networks of relations, Artif. Intell., 8, 99-118, (1977) · Zbl 0341.68061
[75] Makino, K; Berz, M, Taylor models and other validated functional inclusion methods, Int. J. Pure Appl. Math., 4, 379-456, (2003) · Zbl 1022.65051
[76] Maranas, CD; Floudas, CA, Finding all solutions of nonlinearly constrained systems of equations, J. Glob. Optim., 7, 143-182, (1995) · Zbl 0841.90115
[77] Markót, MC; Fernandez, J; Casado, LG; Csendes, T, New interval methods for constrained global optimization, Math. Program., 106, 287-318, (2006) · Zbl 1134.90497
[78] Markót, MC; Schichl, H, Bound constrained interval global optimization in the COCONUT environment, J. Glob. Optim., 60, 751-776, (2014) · Zbl 1302.90152
[79] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100
[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) · Zbl 1391.94333
[81] Merlet, JP, Interval analysis for certified numerical solution of problems in robotics, Int. J. Appl. Math. Comput. Sci., 19, 399-412, (2009) · Zbl 1300.93120
[82] Messine, F, Extentions of affine arithmetic: application to unconstrained global optimization, J. Univers. Comput. Sci., 8, 992-1015, (2002) · Zbl 1274.65184
[83] Messine, F, Deterministic global optimization using interval constraint propagation techniques, RAIRO Oper. Res., 38, 277-293, (2004) · Zbl 1114.90156
[84] Messine, F.: A deterministic global optimization algorithm for design problems. In: Essays and Surveys in Global Optimization, pp. 267-294. Springer (2005) · Zbl 1136.90524
[85] Messine, F; Nogarede, B; Lagouanelle, JL, Optimal design of electromechanical actuators: a new method based on global optimization, IEEE Trans. Magn., 34, 299-308, (1998)
[86] Messine, F; Touhami, A, A general reliable quadratic form: an extension of affine arithmetic, Reliab. Comput., 12, 171-192, (2006) · Zbl 1106.65042
[87] Meyer, CA; Floudas, CA, Convex envelopes for edge-concave functions, Math. Program., 103, 207-224, (2005) · Zbl 1099.90045
[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) · Zbl 1099.90045
[89] Misener, R; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2013) · Zbl 1301.90063
[90] Moore, R.: Interval Analysis, vol. 60 (1966) · Zbl 0176.13301
[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, 3226-3239, (2009) · Zbl 1391.94333
[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, 311-321, (2007)
[94] Neumaier, A; Shcherbina, O, Safe bounds in linear and mixed-integer linear programming, Math. Program., 99, 283-296, (2004) · Zbl 1098.90043
[95] Neveu, B., Trombettoni, G., et al.: Adaptive constructive interval disjunction. In: International Conference on Tools with Artificial Intelligence (ICTAI), pp. 900-906 (2013) · Zbl 0349.90100
[96] Ninin, J., Messine, F., Hansen, P.: A reliable affine relaxation method for global optimization. 4OR (2014). doi:10.1007/s10288-014-0269-0 · Zbl 1320.90065
[97] Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables, vol. 30. Siam, Philadelphia (2000) · Zbl 0949.65053
[98] Patil, MD; Nataraj, P, QFT prefilter design for multivariable systems using interval constraint satisfaction technique, J. Control Theory Appl., 11, 529-537, (2013) · Zbl 1299.93265
[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) · Zbl 1144.93303
[100] Ramdani, N; Nedialkov, NS, Computing reachable sets for uncertain nonlinear hybrid systems using interval constraint-propagation techniques, Nonlinear Anal. Hybrid Syst., 5, 149-162, (2011) · Zbl 1225.93026
[101] Ratschek, H., Rokne, J.: New Computer Methods for Global Optimization. Horwood, Chichester (1988) · Zbl 0648.65049
[102] Ratz, D.: Automatische ergebnisveri kation bei globalen optimierungsproblemen. Ph.D. thesis, Dissertation, Universit at Karlsruhe (1992) · Zbl 0831.65068
[103] Refalo, P.: Impact-based search strategies for constraint programming. In: Principles and Practice of Constraint Programming (CP 2004), pp. 557-571. Springer (2004) · Zbl 1152.68577
[104] Reynet, O., Voisin, O., Jaulin, L.: Anchor-based localization using distributed interval contractors (2011) · Zbl 1016.65041
[105] Roy, J.M.: Singularities in Deterministic Global Optimization. University of Louisiana at Lafayette (2010) · Zbl 1180.90314
[106] Ryoo, HS; Sahinidis, NV, A branch-and-reduce approach to global optimization, J. Glob. Optim., 8, 107-138, (1996) · Zbl 0856.90103
[107] Sahinidis, NV, BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104
[108] Sam-Haroud, D; Faltings, B, Consistency techniques for continuous constraints, Constraints, 1, 85-118, (1996)
[109] Schichl, H; Neumaier, A, Exclusion regions for systems of equations, SIAM J. Numer. Anal., 42, 383-408, (2004) · Zbl 1080.65041
[110] Schichl, H; Neumaier, A, Interval analysis on directed acyclic graphs for global optimization, J. Glob. Optim., 33, 541-562, (2005) · Zbl 1094.65061
[111] Shectman, JP; Sahinidis, NV, A finite algorithm for global minimization of separable concave programs, J. Glob. Optim., 12, 1-36, (1998) · Zbl 0906.90159
[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, RDP, Finding all real solutions of nonlinear systems of equations with discontinuities by a modified affine arithmetic, Comput. Chem. Eng., 48, 48-57, (2013)
[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) · Zbl 1114.90156
[115] Stergiou, K, Heuristics for dynamically adapting propagation in constraint satisfaction problems, AI Commun., 22, 125-141, (2009) · Zbl 1185.90191
[116] Tapia, R, The Kantorovich theorem for newton’s method, Am. Math. Mon., 78, 389-392, (1971) · Zbl 0215.27404
[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) · Zbl 1031.90022
[118] Trombettoni, G., Araya, I., Neveu, B., Chabert, G.: Inner regions and interval linearizations for global optimization. In: AAAI, pp. 99-104 (2011) · Zbl 1108.65065
[119] Trombettoni, G., Chabert, G.: Constructive interval disjunction. In: Principles and Practice of Constraint Programming (CP 2007), pp. 635-650. Springer (2007) · Zbl 1145.68530
[120] Van Hentenryck, P., Michel, L., Deville, Y.: Numerica: A Modeling Language for Global Optimization. MIT Press, Cambridge (2003)
[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) · Zbl 0760.90085
[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) · Zbl 1077.68844
[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, 186-199, (1998) · Zbl 0908.65038
[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) · Zbl 1134.90497
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.