# Non Negative Solutions To a Linear Diophantine?

I have been trying to read a lot of literature concerning the above subject but I've not found anything useful to help my case.

Suppose you're given a linear diophantine in $a_1,a_2,\ldots,a_k$ where $k\leq 10$, and we are asked to tell if $a_1 x_1 + a_2 x_2 + \cdots+a_kx_k = N$ has a non negative solution or not?

We are given many such queries, so I think regular Euclid method wouldn't be sufficient.

Also,since I anyway brought the topic, could we utilise the calculation of the Frobenius Number of the equation to answer the above query.

-

One useful approach is to combine integer linear programming with lattice reduction, e.g. see Lichtblau: Integer Linear Programming, Frobenius Instances, and Frobenius Numbers

-
Thank you for your help.I'd like to also add here another algorithm - "Round Robin Algorithm" which can help answer the MCP(Money Changing Problem) in constant time once we make a precomputation of the residual table.It is effective when the constraints are a little weak. –  Ravi Kiran Feb 2 '11 at 20:49