Knapsack problem with negative value and weights and cardinality constraint

Question

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?

Answer 1

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.