5
$\begingroup$

I know there are ways to handle Knapsack problems with negative weights or cardinality constraints, but I have a problem with also negative values as well as a cardinality constraint: \begin{align} \max & \sum_{i\in N} u_i x_i \\ \text{s.t.} & \sum_{i\in N} w_i x_i \le W \\ & \sum_{i\in N} x_i = C \\ & x_i \in \{0,1\}, \forall i \in N \end{align} where $u_i$ and $w_i$ can both be positive or negative. Wonder if this could be formulated as a standard Knapsack problem?

$\endgroup$
1
  • $\begingroup$ At a minimum, you could solve it as a multiple knapsack problem by setting the weights in the second constraint to one. There might be a better algorithm than this, however. en.m.wikipedia.org/wiki/List_of_knapsack_problems $\endgroup$
    – Max
    May 4, 2022 at 1:19

1 Answer 1

6
$\begingroup$

I assume you have a solver for knapsack problems with cardinality constraints, but it wants only non-negative coefficients.

Let $$\color{darkblue}U_{min} := \min\{0,\color{darkblue}u_1,...,\color{darkblue}u_N\}$$ $$\color{darkblue}W_{min} := \min\{0,\color{darkblue}w_1,...,\color{darkblue}w_N\}$$

Now update: $$ \color{darkblue}u_i := \color{darkblue}u_i - \color{darkblue}U_{min} $$ $$ \color{darkblue}w_i := \color{darkblue}w_i - \color{darkblue}W_{min} $$ $$ \color{darkblue}W := \color{darkblue}W - \color{darkblue}C\cdot \color{darkblue}W_{min} $$

Now you have a problem with all non-negative coefficients that yields the same solution.

If you want the optimal objective value to be the same as for the original problem use: $$ \max \color{darkblue}C\cdot \color{darkblue}U_{min} + \sum_i \color{darkblue}u_i\cdot \color{darkred}x_i $$ This adds a (non-positive) constant term to the objective and will now also replicate the same objective value. You can add this constant term after calling your knapsack solver.

Of course, if you use something like a MIP or CP solver, you can feed it the original problem.

$\endgroup$
4
  • $\begingroup$ Thanks Erwin! I guess yours would still have the cardinality constraint? I thought about “standard knapsack” as without cardinality constraints… Would there be a way then? $\endgroup$
    – Jeffrey
    May 4, 2022 at 19:38
  • $\begingroup$ I used "I know there are ways to handle Knapsack problems with negative weights or cardinality constraints" You say this is not the case? $\endgroup$ May 4, 2022 at 20:23
  • $\begingroup$ Yep, makes sense. Just to confirm that your method still has the cardinatlity constraint. Then it'll work! Thanks again. $\endgroup$
    – Jeffrey
    May 4, 2022 at 20:31
  • 1
    $\begingroup$ Got it. I have added a sentence about my assumptions. Thanks. $\endgroup$ May 4, 2022 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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