Minimizing the sum of 3 variables subject to equality and integrality constraints
<p>I am working on a programming (using Python) problem where I have to solve the following type of linear equation in 3 variables:</p>

<p>x, y, z are all integers.</p>

<p>Equation example:  <code>2x + 5y + 8z = 14</code></p>

<p>Condition: <code>Minimize x + y + z</code></p>

<p>I have been trying to search for an algorithm for finding a solution to this, in an optimum way. If anybody has any idea please guide me through algorithm or code-sources.</p>

<p>I am just curious, what can be done if this problem is extrapolated to n variables? </p>

<p>I don't want to use hit &amp; trial loops to keep checking for values. Also, there may be a scenario that equation has no solution. </p>

<p><strong>UPDATE</strong></p>

<p>Adding lower bounds condition:</p>

<pre><code>x, y, z &gt;= 0
x, y, z are natural
</code></pre>

<p>I do not know any general fast solution for n variables, or not using hit &amp; trail loops. But for the given specific equation  <code>2x + 5y + 8z = 14</code>, there maybe some shortcut based on observation.</p>

<p>Notice that the range is very small for any possible solutions:  </p>

<p><code>0&lt;=x&lt;=7</code>,  <code>0&lt;=y&lt;=2</code>,  <code>0&lt;=z&lt;=1</code></p>

<p>Also other than x = 7, you have at least to use 2 variables.
<strong>(x+y+z = 7 for this case)</strong></p>

<hr>

<p>Let's find what we got if using only 2 variables:</p>

<p>If you choose to use (x,z) or (y,z), as <code>z</code> can only be 1, <code>x</code> or <code>y</code> is trivial. </p>

<p><strong>(x+y+z = 4 for (x,z),  no solution for (y,z))</strong></p>

<p>If you choose to use (x,y), as <code>x</code>'s coefficient is even and <code>y</code>'s coefficient is odd,  you must choose even number of <code>y</code> to achieve an even R.H.S. (14). Which means <code>y</code> must be 2, <code>x</code> is then trivial.</p>

<p><strong>(x+y+z = 4 for this case)</strong></p>

<hr>

<p>Let's find what we got if using all 3 variables:</p>

<p>Similarly, <code>z</code> must be 1, so basically it's using 2 variables (x,y) to achieve 14-8 = 6 which is even.</p>

<p>Again we use similar argument, so we must choose even number of <code>y</code> which is 2, however at this point 2y + 1z > 14 already, which means there is <strong>no solution using all 3 variables</strong>.</p>

<hr>

<p>Therefore simply by logic, reduce the equation by using 1 or 2 variables, we can find that <strong>minimum x+y+z is 4</strong> to achieve 14 <strong>(x=3,y=0,z=1  or x=2,y=2,z=0)</strong></p>

python algorithm linear-programming integer-programming