Making coefficients positive in a linear inequality constraint.

Question

Suppose with have linear inequality constraints $q_i^Tx \leq c_i$ with $q_i \in \mathbb{Z}^n$ for $i=1,\ldots,m$ and $x \in \{0,1\}^n$.

I would like to know if it is possible to reformulate $q_i^Tx \leq c_i$ into something like $p_i^T y \leq c'_i$ where $p_i \geq 0$ (all coefficients are positive or zero) and $y \in \{0,1\}^n$. If yes, how would one do that?

I suspect it is not possible... but maybe there are some tricks or workarounds to address this issue at least partially.

Answer 1

If $q_{ij}<0$, replace $x_j$ with $1-y_j$, take $p_{ij}=-q_{ij}$, and adjust $c_i$ by subtracting $q_{ij}$.