TY - GEN

T1 - Hard equality constrained integer knapsacks

AU - Aardal, K.I.

AU - Lenstra, A.K.

PY - 2002

Y1 - 2002

N2 - 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 nonnegative integer vector x satisfying ax = a 0?" Some instances of this type have been found to be extremely hard to solve by standard methods such as branch-and-bound, even if the number of variables is as small as ten. We observe that not only the sizes of the numbers a 0, a 1,..., a n, but also their structure, have a large impact on the difficulty of the instances. Moreover, we demonstrate that the characteristics that make the instances so difficult to solve by branch-and-bound make the solution of a certain reformulation of the problem almost trivial. We accompany our results by a small computational study.

AB - 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 nonnegative integer vector x satisfying ax = a 0?" Some instances of this type have been found to be extremely hard to solve by standard methods such as branch-and-bound, even if the number of variables is as small as ten. We observe that not only the sizes of the numbers a 0, a 1,..., a n, but also their structure, have a large impact on the difficulty of the instances. Moreover, we demonstrate that the characteristics that make the instances so difficult to solve by branch-and-bound make the solution of a certain reformulation of the problem almost trivial. We accompany our results by a small computational study.

U2 - 10.1007/3-540-47867-1_25

DO - 10.1007/3-540-47867-1_25

M3 - Conference contribution

SN - 3-540-43676-6

T3 - Lecture Notes in Computer Science

SP - 350

EP - 366

BT - Proceedings 9th IPCO (Cambridge MA, USA, May 27-29, 2002)

A2 - Cook, W.J.

A2 - Schulz, A.S.

PB - Springer

CY - Berlin

ER -