@inproceedings{1017b495ecb84515937b19f7d8b6a93b,

title = "Hard equality constrained integer knapsacks",

abstract = "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.",

keywords = "Integer Vector, Short Vector, Search Node, Positive Integer Number, Frobenius Number",

author = "Karen Aardal and Lenstra, {Arjen K}",

year = "2002",

doi = "10.1007/3-540-47867-1_25",

language = "English",

isbn = "978-3-540-43676-8",

series = "Lecture Notes in Computer Science",

pages = "350--366",

editor = "Cook, {William J} and Schulz, {Andreas S}",

booktitle = "Integer Programming and Combinatorial Optimization: 9th International IPCO Conference",

}