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 &Epsilon; &Zdbl;<inf>&ge;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. &copy; 2004 INFORMS.


Published in:
Mathematics of Operations Research, 29, 3, 724 - 738
Year:
2004
ISSN:
0364765X
Keywords:
Laboratories:




 Record created 2010-06-24, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)