Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds. (English) Zbl 1189.90203

Summary: Speed and memory requirements of branch and bound algorithms depend on the selection strategy of which candidate node to process next. The goal of this paper is to experimentally investigate this influence to the performance of sequential and parallel branch and bound algorithms. The experiments have been performed solving a number of multidimensional test problems for global optimization. Branch and bound algorithm using simplicial partitions and combination of Lipschitz bounds has been investigated. Similar results may be expected for other branch and bound algorithms.


90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C26 Nonconvex programming, global optimization
Full Text: DOI Link


[1] Baravykait\.e M., Čiegis R., Žilinskas J.: Template realization of generalized branch and bound algorithm. Math. Model. Anal. 10(3), 217–236 (2005) · Zbl 1138.90501
[2] Čiegis, R., Henty, D., Kågström, B., Žilinskas, J. (eds.): Parallel Scientific Computing and Optimization, Springer Optimization and Its Applications, vol. 27. Springer (2009) · Zbl 1151.65001
[3] Csendes T.: Generalized subinterval selection criteria for interval global optimization. Numer. Algorithms 37(1/4), 93–100 (2004) · Zbl 1090.90177 · doi:10.1023/B:NUMA.0000049489.44154.02
[4] D’Apuzzo M., Marino M., Migdalas A., Pardalos P.M., Toraldo G.: Parallel computing in global optimization. In: Kontoghiorghes, E.J. (eds) Handbook of Parallel Computing and Statistics, pp. 225–258. Chapman & Hall/CRC, London (2006)
[5] Dür M., Stix V.: Probabilistic subproblem selection in branch-and-bound algorithms. J. Comput. Appl. Math. 182(1), 67–80 (2005) · Zbl 1078.65050 · doi:10.1016/j.cam.2004.10.019
[6] Ferreira, A., Pardalos, P.M. (eds.): Solving Combinatorial Optimization Problems in Parallel: Methods and Techniques, Lecture Notes in Computer Science, vol. 1054. Springer (1996) · Zbl 0847.00057
[7] Hansen P., Jaumard B.: Lipshitz optimization. In: Horst, R., Pardalos, P.M. (eds) Handbook of Global Optimization, pp. 407–493. Kluwer, Dordrecht (1995) · Zbl 0833.90105
[8] Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. Kluwer, Dordrecht (1995) · Zbl 0836.90134
[9] Jansson, C., Knüppel, O.: A global minimization method: The multi-dimensional case. Tech. rep., TU Hamburg-Harburg (1992) · Zbl 0802.65078
[10] Kreinovich V., Csendes T.: Theoretical justification of a heuristic subbox selection criterion for interval global optimization. Central Eur. J. Oper. Res. 9(3), 255–265 (2001) · Zbl 1002.90093
[11] Madsen, K., Žilinskas, J.: Testing branch-and-bound methods for global optimization. Tech. Rep. IMM-REP-2000-05, Technical University of Denmark (2000)
[12] Migdalas, A., Pardalos, P.M., Storøy, S. (eds): Parallel Computing in Optimization, Applied Optimization, vol. 7. Kluwer, (1997) · Zbl 0881.00047
[13] Pardalos, P.M. (ed.): Parallel Processing of Discrete Problems, IMA Volumes in Mathematics and its Applications, vol. 106. Springer (1999)
[14] Paulavičius R., Žilinskas J.: Analysis of different norms and corresponding Lipschitz constants for global optimization in multidimensional case. Inf. Technol. Control 36(4), 383–387 (2007)
[15] Paulavičius R., Žilinskas J.: Improved Lipschitz bounds with the first norm for function values over multidimensional simplex. Math. Model. Anal. 13(4), 553–563 (2008) · Zbl 1182.90073 · doi:10.3846/1392-6292.2008.13.553-563
[16] Paulavičius R., Žilinskas J.: Global optimization using the branch-and-bound algorithm with a combination of Lipschitz bounds over simplices. Technol. Econ. Dev. Econ. 15(2), 310–325 (2009) · doi:10.3846/1392-8619.2009.15.310-325
[17] Sergeyev Y.D., Kvasov D.E.: Global search based on efficient diagonal partitions and a set of Lipschitz constants. SIAM J. Optim. 16(3), 910–937 (2006) · Zbl 1097.65068 · doi:10.1137/040621132
[18] Žilinskas A., Žilinskas J.: Global optimization based on a statistical model and simplicial partitioning. Comput. Math. Appl. 44(7), 957–967 (2002) · Zbl 1047.90036 · doi:10.1016/S0898-1221(02)00206-7
[19] Žilinskas A., Žilinskas J.: Branch and bound algorithm for multidimensional scaling with city-block metric. J. Glob. Optim. 43(2/3), 357–372 (2009) · Zbl 1179.90250 · doi:10.1007/s10898-008-9306-x
[20] Žilinskas, A., Žilinskas, J.: P-algorithm based on a simplicial statistical model of multimodal functions. TOP (submitted) (2009) · Zbl 1206.90131
[21] Žilinskas J.: Branch and bound with simplicial partitions for global optimization. Math. Model. Anal. 13(1), 145–159 (2008) · Zbl 1146.49029 · doi:10.3846/1392-6292.2008.13.145-159
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.