Nonnegative Solutions to Linear Diophantine Equations in 2 Variables with Constraints I suppose this is more of an algorithms question, but given a linear Diophantine equation in 2 variables, how do I find a solution pair $(x, y)$ such that $x \geq 0, y \geq 0$, and $x + y$ is minimum of all possible nonnegative solutions?
I realize variations of this question have been asked before, but they either deal with the general case of the $n$ variable equations, or just wish to know if a solution exists, etc.
I want to know if there's an algorithmic way of computing such minimum nonnegative solutions?
EDIT: In fact, all I really want is the sum $x + y$ of these two nonnegative $x$ & $y$ if they exist; and the sum to be minimum.
Here's what I got:
$x = x_1 - \frac{rb}{d}$, and $y = y_1 + \frac{ra}{d}$, where $r \in \mathbb{Z}, \;\text{and}\; d = gcd(a, b)$.
This gives us the general solution. We want $x$, and $y$ to be nonnegative, so:
$$r \leq \frac{x_1d}{b},\;\; r \geq \frac{-y_1d}{a}$$
$$\lceil \frac{-y_1d}{a} \rceil \leq r \leq \lfloor \frac{x_1d}{b} \rfloor.$$
Also,
$$x + y = x_1 - rb/d + y_1 + ra/d = \frac{r}{d}(a - b) + (x_1 + y_1).$$
Combining the two,
$$\lceil \frac{-y_1d}{a} \rceil \frac{(a - b)}{d} + (x_1 + y_1) \leq x + y \leq \dots.$$
So the minimum sum is equal to $\lceil \frac{-y_1d}{a} \rceil \frac{(a - b)}{d} + (x_1 + y_1)$?
Unfortunately, it's not giving the correct answer on all tests.
EDIT 2: Big mistake on my part!!! I didn't check if $(a - b)$ is negative when multiplying!! It's correct now, apologies.
 A: Suppose your linear diophantine equation is $ax+by=c$
Case 1: $a, b$ are both positive and are relatively prime.
If a particular solution of the equation is given by $(x_0,y_0)$, then the general solution is $x=x_0-bt, y=y_0+at$.
This means that you can go from a solution to another solution either by  decreasing the $x$-value by $b$ and increasing the $y$-value by $a$ (good for your optimization if $a<b$); or by increasing the $x$ value by $b$ and decreasing the $y$-value by $a$ (good if $a>b$).
So you should take the variable with the smaller coefficient to be as small as possible. 
Other cases: If $a,b$ are positive and not relatively prime, divide the equation through by $\gcd(a,b)$ (assuming $c$ is divisible by this value--if not the equation has no solutions) and proceed as in case 1.
If $a$ and $b$ are of opposite signs, the solutions lie on a positive sloped line.  Take the lowest point in the first quadrant (or on a nonnegative axis) that lands on the integer grid.
If $a$ and $b$ are both negative and $c$ is positive, there are no nonnegative integer solutions.  If $a$ and $b$ are both negative and $c$ is negative, multiply the equation by $-1$ and proceed as in earlier cases.
