5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Would you see this link? I hope it helps. $\endgroup$ – A.Omidi Dec 3 '20 at 8:25
  • $\begingroup$ Could you please let me know how to use this? I see some files, but no algorithms. $\endgroup$ – OR_student Dec 3 '20 at 10:10
  • 2
    $\begingroup$ It is unclear to me what are your variables, and what are your constants ? Are all the coefficients constant, and the binary variables not written ? $\endgroup$ – Kuifje Dec 3 '20 at 13:12
  • 1
    $\begingroup$ This can be solved via dynamic programming $\endgroup$ – Steven01123581321 Dec 3 '20 at 15:26
  • 1
    $\begingroup$ @Steven01123581321 I am not sure about the dynamic programming. You would have to be able to express the cost function $\frac{A_jB_j}{1+B_j}$ in terms of $\frac{A_{j-1}B_{j-1}}{1+B_{j-1}} + ...$. This is not straightforward. $\endgroup$ – Kuifje Dec 3 '20 at 17:45
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.