I've already solved the linear relaxation of the problem and note that a relaxed version of the problem (without integral variables) results in integer solutions.
\begin{matrix}1&1&0&0&0&0&0&0\\0&0&1&1&0&0&0&0\\1&0&0&0&-1&0&-1&0\\0&1&0&0&0&-1&0&-1\\0&0&1&0&-1&0&-1&0\\0&0&0&1&0&-1&0&-1\\0&0&0&0&1&0&1&0\\0&0&0&0&0&1&0&1\\0&0&0&0&1&1&0&0\\0&0&0&0&0&0&1&1\end{matrix}