On the use of restriction of the right-hand side in spatial branch-and-bound algorithms to ensure termination

Abstract Spatial branch-and-bound algorithms for global minimization of non-convex problems require both lower and upper bounding procedures that finally converge to a globally optimal value in order to ensure termination of these methods. Whereas convergence of lower bounds is commonly guaranteed for standard approaches in the literature, this does not always hold for upper bounds. For this reason, different so-called convergent upper bounding procedures are proposed. These methods are not always used in practice, possibly due to their additional complexity or possibly due to increasing runtimes on average problems. For that reason, in this article we propose a refinement of classical branch-and-bound methods that is simple to implement and comes with marginal overhead. We prove that this small improvement already leads to convergent upper bounds, and thus show that termination of spatial branch-and-bound methods is ensured under mild assumptions.