A Branch and Bound Algorithm for Separable Concave Programming

Abstract

In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision (NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than $w$-subdivision method.