1
$\begingroup$

I am dealing with a knapsack-like problem with one difference from the conventional problem: the “weights” can be positive or negative and the constraint is $\sum w_i x_i \ge 0$ instead of $\sum w_i x_i \le W$. The "values" can also be positive or negative.

Can this be transformed to a knapsack problem or is it some other type of combinatorial optimization problem?

$\endgroup$
6
  • $\begingroup$ This is better suited to or.stackexchange.com $\endgroup$ Oct 3, 2021 at 15:08
  • $\begingroup$ Are the values all positive? If so, we should certainly take all items with positive weights, and then the question of the best subset of negative-weight items seems to be classical knapsack again. $\endgroup$
    – usul
    Oct 4, 2021 at 2:34
  • $\begingroup$ Good point! Forgot to mention that values can also be negative. $\endgroup$
    – Jeffrey
    Oct 4, 2021 at 11:47
  • $\begingroup$ What type of variable is $x$? $\endgroup$
    – RobPratt
    Oct 4, 2021 at 15:11
  • $\begingroup$ Binary indeed as you noted $\endgroup$
    – Jeffrey
    Oct 5, 2021 at 9:13

1 Answer 1

1
$\begingroup$

Assuming $x_i$ is binary, perform a change of variables $\bar{x}_i:=1-x_i$ where $w_i>0$: \begin{align} \sum_i w_i x_i &= \sum_{i:w_i>0} w_i x_i + \sum_{i:w_i<0} w_i x_i \\ &= \sum_{i:w_i>0} w_i(1-\bar{x}_i) + \sum_{i:w_i<0} w_i x_i \\ &= \sum_{i:w_i>0} w_i + \sum_{i:w_i>0} (-w_i)\bar{x}_i + \sum_{i:w_i<0} w_i x_i \end{align} So $\sum_i w_i x_i \ge 0$ is equivalent to $$\sum_{i:w_i>0} w_i\bar{x}_i + \sum_{i:w_i<0} (-w_i) x_i \le \sum_{i:w_i>0} w_i$$

$\endgroup$

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.