Polytopal Spatial Branch and Bound Global Optimization Algorithm

Casado, L.G.; G.-Tóth, B.; Hendrix, E.M.T.; Messine, F.

doi:10.15388/25-INFOR609

Informatica

Polytopal Spatial Branch and Bound Global Optimization Algorithm^✩

L.G. Casado

B. G.-Tóth

E.M.T. Hendrix

F. Messine

https://doi.org/10.15388/25-INFOR609

Pub. online: 31 October 2025 Type: Research Article

Open Access

^✩ This work has been funded by MCIN/AEI/10.13039/501100011033 and by “ERDF A way of making Europe”, Grant PID2021-123278OB-I00 of the Spanish ministry of Science and Innovation.

Received
1 September 2025

Accepted
1 October 2025

Published
31 October 2025

Abstract

Spatial Global Optimization branch and bound (B&B) methods aim at enclosing global minimum points in a guaranteed way with a certain accuracy. We extend simplicial B&B (sBB) concepts to polytopal B&B (pBB), with polytope subsets. The main challenges are: polytope division and extension of monotonicity tests theoretically and algorithmically. We compare the performance of interval B&B with linear constraints (iBBLC), sBB and pBB algorithms, to determine the most efficient B&B algorithm for different types of instances.

References

Assarf, B., Gawrilow, E., Herr, K., Joswig, M., Lorenz, B., Paffenholz, A., Rehn, T. (2017). Computing convex hulls and counting integer points with polymake. Mathematical Programming Computation , 9(1), 1–38. https://doi.org/10.1007/s12532-016-0104-z.

Casado, L.G., G.-Tóth, B., Messine, F., Hendrix, E.M.T. (2021). Directional derivative bounds and border facets in simplicial B&B monotonicity tests. In: SCAN’20: The 19th International Symposium on Scientific Computing, Computer Airthmetic and Verified Numerical Computations, Szeged, Hungary, pp. 18–19.

Casado, L.G., G.-Tóth, B., Hendrix, E.M.T., Messine, F. (2022). On monotonicity detection in simplicial branch and bound over a simplex. In: Computational Science and Its Applications – ICCSA 2022 Workshops. Springer International Publishing, Cham, pp. 113–126. 978-3-031-10562-3.

Casado, L.G., G.-Tóth, B., Hendrix, E.M.T., Messine, F. (2025). Local search versus linear programming to detect monotonicity in simplicial branch and bound. Journal of Global Optimization, 91, 311–330.

Fernández, J., G.-Tóth, B. (2022). Interval tools in branch-and-bound methods for global optimization. In: The Palgrave Handbook of Operations Research. Springer, pp. 237–267. https://doi.org/10.1007/978-3-030-96935-6_8.

G.-Tóth, B., Casado, L.G., Hendrix, E.M.T., Messine, F. (2021). On new methods to construct lower bounds in simplicial branch and bound based on interval arithmetic. Journal of Global Optimization, 80(4), 779–804.

G.-Tóth, B., Hendrix, E.M.T., Casado, L.G., Messine, F. (2024). On dealing with minima at the border of a simplicial feasible area in simplicial branch and bound. Journal of Optimization Theory and Applications, 203, 1794–1819. https://doi.org/10.1007/s10957-024-02480-9.

Gencsi, M., G.-Tóth, B. (2025). Efficient use of optimality conditions in Interval Branch and Bound methods. EURO Journal on Computational Optimization, 13, 100108. https://doi.org/10.1016/j.ejco.2025.100108.

Hansen, E.R., Walster, G.W. (2004). Global Optimization Using Interval Analysis, 2nd ed. Marcel Dekker Inc., New York.

Hendrix, E.M.T., G.-Tóth, B. (2010). Introduction to Nonlinear and Global Optimization. Springer, New York.

Hendrix, E.M.T., Casado, L.G., G.-Tóth, B., Messine, F. (2024). On Polytopal Branch and Bound with Monotonicity. In: Gervasi, O., Murgante, B., Garau, C., Taniar, D., C. Rocha, A.M.A., Faginas Lago, M.N. (Eds.), Computational Science and Its Applications – ICCSA 2024 Workshops. Springer Nature Switzerland, Cham, pp. 397–414. 978-3-031-65223-3.

Karhbet, S.D., Kearfott, R.B. (2017). Range Bounds of Functions over Simplices, for Branch and Bound Algorithms. Reliable Computing, 25, 53–73. https://interval.louisiana.edu/reliable-computing-journal/volume-25/reliable-computing-25-pp-053-073.pdf.

Kearfott, R.B. (1992). An interval branch and bound algorithm for bound constrained optimization problems. Journal of Global Optimization, 2(3), 259–280. https://doi.org/10.1007/BF00171829.

López, F.J., Duval, A.M. (2012). Algorithms to determine the edges of a convex hull from its vertices. International Journal of Mathematical Modelling and Numerical Optimisation, 3(3), 184–209. https://doi.org/10.1504/IJMMNO.2012.047704.

Moore, R.E., Kearfott, R.B., Cloud, M.J. (2009). Introduction to interval analysis. Society for Industrial and Applied Mathematics, USA. 0898716691. https://doi.org/10.1137/1.9780898717716.

Paulavičius, R., Žilinskas, J. (2014). Simplicial Global Optimization. Springer, New York. 978-1-4614-9092-0.

Rall, L.B. (Ed.) (1981). Examples of Software for Automatic Differentiation and Generation of Taylor Coefficients. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 54–90. 978-3-540-38776-3.

Biographies

Casado L.G.

https://orcid.org/0000-0001-8459-4982

leo@ual.es

L.G. Casado has a PhD from University of Málaga. He is full professor at the University of Almería. His research activities include exhaustive search in global optimization algorithms, parallel computing, network security, etc. See https://sites.google.com/ual.es/leo.

G.-Tóth B.

https://orcid.org/0000-0002-0927-111X

boglarka@inf.szte.hu

B.G.-Tóth is a senior researcher at University of Szeged. Her research interests are rigorous global optimization methods, and their application to facility location problems. She obtained her PhD from the University of Almería.

Hendrix E.M.T.

https://orcid.org/0000-0003-1572-1436

eligius@uma.es

E.M.T. Hendrix is a full professor at the Universidad de Málaga. His research interests are global and dynamic optimization and computational impacts. He obtained his PhD from Wageningen University and his MSc and Bsc from Tilburg University.

Messine F.

https://orcid.org/0000-0002-6457-3321

messine@laplace.univ-tlse.fr

F. Messine is a full professor at the University of Toulouse, specifically at ENSEEIHT and the LAPLACE-CNRS laboratory. His research interests focuses on deterministic global optimization, topology and shape optimization and their applications to optimize the designs of electromechanical actuators such as electrical machines and space thrusters. He obtained his PhD and his Habilitation (accreditation to supervise research) at Toulouse-INP University.

Full article Related articles

Open access article under the CC BY license.

Keywords

polytope branch and bound monotonicity interval arithmetic global optimization

Funding

This work has been funded by Grant PID2021-123278OB-I00 funded by MCIN/AEI/ 10.13039/501100011033 and by “ERDF A way of making Europe”.

Metrics

since January 2020

Article info
views

Full article
views

PDF
downloads

XML
downloads

RSS

Authors

Abstract

References

Biographies

Export citation

Copy and paste formatted citation

Download citation in file