Hard equality constrained integer knapsacks
We consider the following integer feasibility problem: Given positive integer numbers a<inf>0</inf>, a<inf>1</inf>,&mellip;,a<inf>n</inf> with gcd(a<inf>1</inf>,&mellip;,a<inf>n</inf>) = 1 and a = (a<inf>1</inf>,&mellip;,a<inf>n</inf>), does there exist a vector x Ε &Zdbl;<inf>≥0</inf><sup>n</sup> satisfying a x = a<inf>0</inf>? We prove that if the coefficients a<inf>1</inf>,&mellip;,a<inf>n</inf> have a certain decomposable structure, then the Frobenius number associated with a<inf>1</inf>,&mellip;,a<inf>n</inf>, i.e., the largest value of a<inf>0</inf> for which a x = a<inf>0</inf> does not have a nonnegative integer solution, is close to a known upper bound. In the instances we consider, we take a<inf>0</inf> to be the Frobenius number. Furthermore, we show that the decomposable structure of a<inf>1</inf>,&mellip;,a<inf>n</inf> 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<inf>0</inf>/a<inf>i</inf>, 1 &le i &le n. We illustrate our results by some computational examples. © 2004 INFORMS.
149458.pdf
openaccess
194.5 KB
Adobe PDF
fd9c79dc95a009443ef80e00dc4d09d2