We consider the following integer feasibility problem: ``Given positive integer numbers $a_0,a_1,\dots,a_n,$ with $\gcd(a_1,\dots,a_n)=1$ and $\va=(a_1,\dots,a_n)$, does there exist a vector $\vx\in\bbbz^n_{\ge \zero}$ satisfying $\va\vx = 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,\dots,a_n,$ but also their structure, have a large impact on the difficulty of the instances. This particular structure enables us to derive a strong lower bound on the Frobenius number for these instances. Moreover, we demonstrate that the same structural 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.
Citation
Preprint number 1256, Department of Mathematics, Utrecht University, Utrecht, The Netherlands, 2002.