Find minimum values of a linear system over $\mathbb N$

Question

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

Answer 1

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.

Answer 2

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