A composite branch and bound, cutting plane algorithm for concave minimization over a polyhedron

The authors present an algorithm that combines branch and bound with cutting planes to globally minimize a concave function over a polyhedron. The algorithm solves a series of linear underestimating subproblems over subsets of the feasible region, yielding lower and upper bounds on the optimal objective value of the original problem. The algorithm also uses a form of the Tuy cutting plane in the subproblems of the branch and bound tree. As in cone splitting algorithms for concave minimization, the authors construct the cutting planes such that no restrictive nondegeneracy assumptions are required and such that the hyperplanes defining the cuts do not need to be explicitly calculated, eliminating matrix inversions. An additional advantage of the present algorithm is that the cuts cause the linear underestimating functions to more accurately approximate the concave objective function, yielding tighter lower bounds. Computational results with the algorithm are reported.