An algorithm for the minimum of the concave knapsack problem

This paper addresses the problem of resource allocation among activities where the cost of each is described by a concave function. There is a single linear constraint (limited resource) and each activity has an upper and lower bound (maximum and minimum resource allocations). The objective is to minimise the sum of the functions. The problem with convex functions is well-studied and since a local minimum is also global, this problem was tamed early. In contrast the minimisation of a sum of concave functions has received less attention and then the emphasis has often been on an objective function which is nonseparable quadratic, and on the complexity of finding a true local minimiser. We are concerned with the computational problem of finding the global optimum for a (separable) sum of nondecreasing general concave functions and the approach is via the Kuhn–Tucker necessary conditions. These are improved by using the result that a minimiser must be an extreme point, which means that all but one variable (at most) is at an upper or lower bound. The improved necessary conditions form the basis of the method of greatest differences (GVA), our algorithm to improve a feasible soluton. A greedy heuristic to produce a first feasible solution is also proposed.