@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",
}