Polytopal Spatial Branch and Bound Global Optimization Algorithm
Open Access
- 1 January 2025
- journal article
- Published by Vilnius University Press in Informatica
- p. 765-795
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.Keywords
This publication has 10 references indexed in Scilit:
- Efficient use of optimality conditions in Interval Branch and Bound methodsEURO Journal on Computational Optimization, 2025
- On Dealing with Minima at the Border of a Simplicial Feasible Area in Simplicial Branch and BoundJournal of Optimization Theory and Applications, 2024
- Local search versus linear programming to detect monotonicity in simplicial branch and boundJournal of Global Optimization, 2023
- Interval Tools in Branch-and-Bound Methods for Global Optimization2022
- On new methods to construct lower bounds in simplicial branch and bound based on interval arithmeticJournal of Global Optimization, 2021
- Computing convex hulls and counting integer points with polymakeMathematical Programming Computation, 2016
- Simplicial Global Optimization2014
- Algorithms to determine the edges of a convex hull from its verticesInternational Journal of Mathematical Modelling and Numerical Optimisation, 2012
- Introduction to Interval Analysis2009
- An interval branch and bound algorithm for bound constrained optimization problemsJournal of Global Optimization, 1992