Find the integral solution of a given equation while minimizing the integral sum of solution

Question

Suppose we are given a linear equation in $n$ dimensions:

$$Ax+By+Cz=S\,\,\,\,\,\, (n\text{ is }3)$$

with constraints on $x$, $y$ and $z$ as :

$$0\le x\le p,$$

$$ 0\le y\le q,$$

$$ 0\le z\le r.$$

We have to find the integral solution of this equation such that $x+y+z$ is minimum.

For example:

$$ 678 x+ 123 y+ 12 z=996$$

where

$$ 0\le x,$$

$$ 0\le y,$$

$$ 0\le z.$$

The solution which minimizes $x+y+z$ are $(1,2,6)$ and $(0,8,1)$.

What general methods can be applied to solve such a problem where we have constraint on all dimensions that they are greater than zero ?

Answer 1

This is the type of problems that can be solved by the Simplex algorithm combined by the Cutting plane method.

In general is hard to solve efficiently.

---

The feasible set (the set of points that satisfies the restrictions) lie on the portion of the plane $P=\{Ax+By+Cz=S\}$ that is inside the parallelogram defined by the inequalities. The intersection is a convex polygon. I think at most it is a hexagon but most of the time it has smaller number of sides.

The objective function $x+y+z$ gets smaller when you move in the direction of the vector $(-1,-1,-1)$. You can project this vector onto the plane $P$. That tells you in what direction to move inside the feasible set.

But you first need to find a feasible solution.

Answer 2

This first stage is to look for, and remove, any common factor.

For your example, $gcd=3$ giving $226x+41y+4z=332$

With $n=3$, find the variable with the second smallest range of values, and isolate it to the LHS. In your example, $$41y=332-226x-4z$$

Now substitute the numerical values for the variable with the smallest range of values, then solve the resulting equations. Note, start with small values and stop at the first solution in each group.

In this case, $x$.

When $x=0$, we have $41y=106-4z$ and a few trials give $z=6$, so $y=2$.

When $x=1$, we have $41y=332-4z$ and a few trials give $z=1$, so $y=8$. If you were to continue to find more solutions, that must be larger (eg $z=42,y=4$).

When $n>3$, its much the same idea, just working down the substitutions until you have a set of two-variable equations.

Please let me know if you need elaboration.