The classical 0,1 knapsack problem with weights $w$ and unit value for all items $x$:$max \displaystyle\sum_{i} x_i, x_i \in \{0,1\}$subject to$\displaystyle\sum_{i} w_ix_i \leq W$for a maximum weight $W$.Recall that the weights in this version can be negative: we will simply select all items with zero or negative value and then solve for the remaining items with positive weight[1]Now suppose we also want to limit the maximum weight on the negative side:$|\displaystyle\sum_{i} w_ix_i| \leq W$We can quickly see that this problem is still hard when we set $W=0$ as this would answer subset-sum. What is the name of the problem where we have constraints on the absolute weight? As I encounter instances of this problem often I would like to read up on it and possible heuristics. I suspect that it would have long been listed as a variant of subset-sum or knapsack but I fail to find this exact problem.[1].$\displaystyle\sum_{i} \{ w_ix_i | w_i \in w^+ \} \leq W - \displaystyle\sum_{i} \{ w_i | w_i \in w^- \}$
Subset sum with wider constraint
optimization;reference request;knapsack problems;integer programming