A COMPOSITE BRANCH-AND-BOUND, CUTTING PLANE ALGORITHM FOR CONCAVE MINIMIZATION OVER A POLYHEDRON

We present an algorithm that combines branch and bound with cutting pl anes to globally minimize a concave function over a polyhedron. The al gorithm solves a series of linear underestimating subproblems over sub sets of the feasible region, yielding lower and upper bounds on the op timal 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, we construct the cutting planes such that no restrictive nondegeneracy assumptions are required and such that the hyperplanes defining the c uts do not need to be explicitly calculated, eliminating matrix invers ions. An additional advantage of our algorithm is that the cuts cause the linear underestimating functions to more accurately approximate th e concave objective function, yielding tighter lower bounds. Computati onal results with the algorithm are reported.