Hard equality constrained integer knapsacks

We consider the following integer feasibility problem: Given positive integer numbers a(0), a(1),..., a(n), with gcd(a(1),...,a(n)) = 1 and a = (a(1),...,a(n)), does there exist a vector x is an element of Z(greater than or equal to0)(n) satisfying ax.= a(0)? We prove that if the coefficients a(1),..., a(n) have a certain decomposable structure, then the Frobenius number associated with a(1),..., a(n), i.e., the largest value of a(0) for which ax = a(0) does not have a nonnegative integer solution, is close to a known upper bound. In the instances we consider, we take a. to be the Frobenius number. Furthermore, we show that the decomposable structure of a,,..., a. makes the solution of a lattice reformulation of our problem almost trivial, since the number of lattice hyperplanes that intersect the polytope resulting. from the reformulation in the direction of the last coordinate is going to be very small. For branch-and-bound such instances are difficult to solve, since they are infeasible and have large values of a(0)/a(i), 1 less than or equal to i less than or equal to n. We illustrate our results by some computational examples.