Separable concave minimization via partial outer approximation and branch and bound (Q2277369)

The paper presents an algorithm for globally minimizing a separable, concave function over a compact convex set. The algorithm combines partial outer approximation and branch-and-bound in a manner specifically designed to exploit the separability of the objective function. The major computational effort required is to solve linear programming problems at some nodes of the branch-and-bound tree, and to solve simple univariate minimization problems in some iterations. The outer approximation used in the algorithm is partial in the sense that many of the cutting planes that it creates are not added as constraints in a number of the linear programming subproblems solved during the branch-and-bound search.