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>Another tool to solve this type of problems is <a href="http://scip.zib.de" rel="nofollow">SCIP</a>. There is also an easy to use Python interface available on GitHub: <a href="https://github.com/SCIP-Interfaces/PySCIPOpt" rel="nofollow">PySCIPOpt</a>.</p>

<p>In general (mixed) integer programming problems are very hard to solve (NP complexity) and often even simple looking instances with only a few variables and constraints can take hours to prove the optimal solution.</p>

python algorithm linear-programming integer-programming