Finiteness result for the simplicial branch-and-bound algorithm based on \(\omega\)-subdivisions (Q5925735)

For solving a concave minimization problem of the form \(\min_{x \in P } f(x)\) over a polytope \(P\), \textit{R. Horst} [Math. Programming. 10, 312-321 (1976; Zbl 0337.90062)] introduced a simplicial branch and bound method based on \(\omega\)-subdivisions. In \textit{M. Locatelli} and \textit{U. Raber} [see the paper reviewed below)] the convergence of this method has been shown. Here the authors prove that the method is finite under the following two conditions (C1) and (C2) : Let \(v\) be a vertex of the starting simplex which does not belong to \(P\). (C1) \(f(v)\) is smaller than the optimal value \(f^*\) over \(P\). (C2) \(v\) violates one and only one of the constraints defining \(P\). Condition (C2) holds, e.g., if \(P\) is a hypercube.