Polytopal Spatial Branch and Bound Global Optimization Algorithm

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.