An application of gomory cuts in number theory

Frobenius has stated the following problem. Suppose thata ₁, a₂, ?, a_n are given positive integers and g.c.d. (a ₁, ? , a_n) = 1. The problem is to determine the greatest positive integerg so that the equation $$sumlimits_{i = 1}^n {a_i x_i = g} $$ has no nonnegative integer solution. Showing the interrelation of the original problem and discrete optimization we give lower bounds for this number using Gomory cuts which are tools for solving discrete programming problems. In the first section an important theorem is cited after some remarks. In Section 2 we state a parametric knapsack problem. The Frobenius problem is equivalent with finding the value of the parameter where the optimal objective function value is maximal. The basis of this reformulation is the above mentioned theorem. Gomory's cutting plane method is applied for the knapsack problem in Section 3. Only one cut is generated and we make one dual simplex step after cutting the linear programming optimum of the knapsack problem. Applying this result we gain lower bounds for the Frobenius problem in Section 4. In the last section we show that the bounds are sharp in the sense that there are examples with arbitrary many coefficients where the lower bounds and the exact solution of the Frobenius problem coincide.