Find minimum values of a linear system over $\mathbb N$ I have the following linear equations:
\begin{align}
p &= 2(a-c)+b-d\\
q &= 2(e-g)+f-h\\
a+c &= f+h\\
b+d &= e+g\\
\end{align}
where $p$ and $q$ are known, and $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ are unknown. Also $p$, $q$, $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ are all natural numbers (including zeros).
Obviously, this is a linear system with $4$ equations and $8$ unknowns that has infinitely many solutions.
Is there a way to find the minimum values of $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ that solve the system? What I really want is the minimum value of the sum $a+b+c+d$ (which also happens to be equal with $e+f+g+h$).
 A: This isn't a full solution, just an idea to get started.  If we have a solution $(a,b,c,d,e,f,g,h),$ let $$
\begin{align}
m&=\min(a,c,f,h)\\
n&=\min(b,d,e,g)\\
a'&=a-m\\
c'&=c-m\\
f'&=f-m\\
h'&=h-m\\
b'&=b-n\\
d'&=d-n\\
e'&=e-n\\
g'&=g-n\\
\end{align}$$
Then $(a',b',c',d',e',f',g',h')$ is a solution in naturals and  $$a'+b'+c+d'\le a+b+c+d.$$  So, we can assume that one of $a,c,f,h$ is $0$ and one of $b,d,e,g$ is $0$.  This gives $16$ systems of equations, but they only have $6$ variables instead of $8.$
The only other thing I've noticed so far is that we have $$
\begin{align}
p&\equiv b-d\equiv b+d\pmod{2}\\
q&\equiv f-h\equiv f+h\equiv a+c\pmod{2}\\
\end{align}$$
So that
$$a+b+c+d\equiv p+q\pmod{2}$$ 
A possible approach is to try test values of $a+b+c+d$ adding it as another equation.  The above fact eliminates half the test values.  If you get a solution, you have an upper bound on the minimum.  If the system doesn't have a solution, I don't see that you have a lower bound though.
A: Perhaps, at first, it would be useful to consider the relaxation of this problem, i.e. all variables are non-negative real! numbers. Then it is possible to use the simplex method with some kind of caution because $p,q$ are not given explicitly. For example, If I did not make a mistake then the solution of the relaxation LP problem is something like
$$
 a=f=\frac{2p-q}3,\ \ e=b=\frac{2q-p}3,\ \ c=d=g=h=0
$$
and the corresponding minimum is
$$
 \frac{p+q}3.
$$
This looks true if $2p-q$ and $2q-p$ are both non-negative (if they also are divided by 3 then they are solutions of the original integer programming problem). if $2p-q$ or $2q-p$ can be negative then the solution is different...
Another idea is to try to rewrite it as a binary integer programming problem...
