4
$\begingroup$

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.

2 Answers 2

2

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

  • 0
    Tha$n$k 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.2011-02-02
0

Concerning the number of solutions of your equation of interest please read Mahmoudvand et al. (2010) The exact number of nonnegative integer solutions for a linear Diophantine inequality. IAENG Int. J. of Appl. Math.,40:1_01. Concerning the enumeration of all those solutions themselves please read Voinov V. (2018) A note on the intractability of partitions, knapsack, subset sum and related problems. Math. J. ISSN 1682-0525, Vol. 17:13-24 (available at Researchgate for free). In those papers you'll find out answers on all your questions. Prof. Vassilly Voinov.