Return to Revisions

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$$