0-1 knapsack with non-linear objective function

Question

There's efficient algorithms for solving the 0-1 knapsack problems when the objective function is just a sum of profits. I am dealing with the following problem with non-linear objective function:

$$\max_{S \subseteq N} \frac{\left( \sum_{k\in S} a_k \right) \cdot \left(\sum_{k\in S} b_k \right)}{1 + \sum_{k\in S} b_k}\;\;\; \text{subject to}\;\;\; \sum_{k\in S} w_k \leq C,$$

where $a_i, b_i, w_i \geq 0 \;\; \forall \;\; i \in N. $

I can transform this problem into the equivalent MILP formulation using CC transformation, but it cannot be solved in polynomial time if $N$ is large. Is there any technique or developed algorithm to solve this in polynomial time?

Answer 1

Even though knapsack problems are relatively easy to solve in practice, there does not exist a polynomial-time algorithm to solve even the standard knapsack problem, unless $\mathcal{P}=\mathcal{NP}$. The knapsack problem can be solved in pseudo-polynomial time $\mathcal{O}(nC)$. Even when the input length (=number of digits describing the problem) is small, the actual number $C$ may be large (e.g., I only need six digits to write the number 999,999), which is why the complexity is not polynomial.

Let $n$ be the number of items, and let $B = \sum_{k\in N} b_k$. Then I think you can solve your problem in pseudo-polynomial time $\mathcal{O}(nCB^2)$ as follows:

1. Add the constraint $\sum_{k \in S} b_k = D$ for some $D \in \{0,\dots,B\}$.

2. The factor $\frac{\sum_{k\in S} b_k }{1 + \sum_{k\in S} b_k}$ is now a constant and can be removed from the objective. What remains is a multidimensional knapsack problem in dimension two, with one inequality and one equality constraint.

3. Solve the problem with dynamic programming. Let $f_D(k,c,d)$ be the best objective value obtainable after processing the first $k$ items, with a total weight less than or equal to $c$ and for which the current sum of the $b_k$ weights is exactly $d$. To calculate the value of $f_D(k,c,d)$ you pick the best of two options

   1. Not selecting item $k$, which gives you objective $f_D(k-1,c,d)$.
   2. Or selecting item $k$, which gives you objective $f_D(k-1,c-w_k,d-b_k)$.

4. Record the optimal solution for $D$, given by $f_D(n, C, D)$.

5. Repeat 1-4 for all possible values of $D$ and compare the solutions to select the best one.

For a given $D$, the dynamic program calculates $\mathcal{O}(nCB)$ values, each in constant time. Repeating this for all $D\in \{0,\dots,B\}$ and comparing the outcomes puts the complexity in $\mathcal{O}(nCB^2)$.

It should be noted that the multi-dimensional knapsack problem is significantly more difficult than the standard knapsack problem. For example, knapsack allows for a FPTAS, while the multi-dimensional knapsack does not, even in dimension two. Dynamic programming is not necessarily the best approach in practice. This Knapsack Problems book discusses both dynamic programming and other approaches in detail. Finally, a direct method for non-linear knapsack may be better than fixing $D$ and solving the remainder, as I showed here.