Hard Equality Constrained Integer Knapsacks

We consider the following integer feasibility problem: Given positive integer numbers a₀, a₁,…,a_n, with gcd(a₁,…,a_n) = 1 and a = (a₁,…,a_n), does there exist a vector x ∈ ℤⁿ_≥0 satisfying a x = a₀? We prove that if the coefficients a₁,…,a_n have a certain decomposable structure, then the Frobenius number associated with a₁,…,a_n, i.e., the largest value of a₀ for which a x = a₀ 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_n 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₀/a_i, 1 ≤ i ≤ n. We illustrate our results by some computational examples.