On the solution of concave knapsack problems (Q2276878)

Local minimizers of some special cases of concave knapsack problem (CKP) \[ \min \{\sum^{n}_{i=1}q_ i(x_ i):\;\ell \leq x\leq u,\quad \sum^{n}_{i=1}a_ ix_ i=\gamma \}, \] where the functions \(q_ i:\) \(R\to R\) are strictly concave differentiable functions, may provide upper bounds and can be good approximations to the solution of the 0-1 knapsack problem, considered in the form: Given n integers \(a_ 1,a_ 2,...,a_ n\), and an integer \(\gamma\), determine if there is a subset \(J\subset \{1,...,n\}\) such that \(\sum_{j\in J}a_ j=\gamma.\) Strict local minimizers of CKP are characterized and an algorithm for their computation is presented. The authors prove that the algorithm requires at most O(n log n) operations and \(1+\lceil \log n\rceil\) evaluations of the function.