An application of Gomory cuts in number theory (Q580401)

Suppose that \(a_ 1,a_ 2,\ldots,a_ n\) are given positive integers and \(\gcd (a_ 1,\ldots,a_ n)=1\), then the Frobenius problem is to determine the greatest positive integer \(g\) so that \(\sum^{n}_{i=1}a_ ix_ i=g\) has no nonnegative integer solution. The author gives lower bounds for \(g\) by applying Gomory's cutting plane method of integer programming to a certain knapsack problem. There are special examples for which these lower bounds equal the exact solution of the Frobenius problem, and in this sense the bounds are sharp.