Transforming a $0$-$1$ knapsack problem into the standard form

Question

I have the following $0$-$1$knapsack problem:

$$\begin{align*} &\mathrm{Max} : \quad z= 3x_1 -4x_2+5x_3+7x_4-6x_5+x_6\\ & \mathrm{subject\ to}: -2x_1 +x_2 +10x_3 +3x_4 -5x_5+12x_6 \leq 4 \\ \end{align*}$$ $$x_1, \dots,x_6 \in \{0,1\}$$

The general form of this problem is

$$\begin{align*} & \mathrm{Max} \quad z=\sum_{j=1}^n c_jx_j\\ & \mathrm{subject \ to}:\ \sum_{j=1}^na_jx_j \leq b \end{align*}$$

where $x_j \in \{0,\}$ and $c_j \gt 0 \ \forall j \in \{1,\dots,n\} $, $0 \lt a_j \leq b \ \forall j \in \{1,\dots,n\}$ and $\sum_{j=1}^na_j \gt b$.

However, in my case, not all $c_j$ are greater than $0$ and not all $a_j$ satisfy $0 \lt a_j \leq b$, so I can't use the algorithm I know to solve this. My question is, then

How can I transform the problem in the general form?

Thanks in advance.

Answer 1

If an item $j$ satisfies $c_j\ge0$ and $a_j\le0$, take it ($x_j=1$). If $c_j\le 0$ and $a_j\ge 0$, reject it ($x_j=0$). If $a_j<0$ and $c_j<0$, use the change of variables $x_j'=1-x_j$, $a_j'=-a_j$, $c_j'=-c_j$, $b'=b-a_j$.