# How do you solve a general linear diophantine equation in polynomial time (with minimization constraint)?

Given

$$a_1 X_1 + \dots + a_n X_n = b$$

where $$a_i, b \in \Bbb{Z}$$. How do you come up with a clearer picture of the solution set in polynomial time.

Also, what I really want is to do the above, but under the minimization of:

$$X_1 + \dots + X_n, \ X_i \in \Bbb{N}$$

All my $$X_i$$ are bounded with small sets such as $$\{0, 2\}$$ for small input instances of my certain problem, however I can't very well try $$2^n$$ or more possibilities, now can I! That would not be polynomial time.

• @Apass.Jack that will not work. I tried it in numerous posts on MSE. The fact is no one has interest in the problem I'm working on. So I present the abstraction only, which clearly has applications in many problems (see "integer programming"). Keeps the post elegant and simple enough to understand. It's really annoying that I cannot find any accessible research on the web for this long solved constraint problem. I don't care about the $n = 2$ case, I can write the formula from memory. I am interested in only the general case. Apparently most writers plaigiarize since 99% content is n=2! – Shine On You Crazy Diamond Aug 1 at 16:13