- Hard equality constrained integer knapsacks Karen Aardal (aardalisye.gatech.edu) Arjen K. Lenstra (arjen.lenstracitigroup.com) Abstract: 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. Keywords: Lattice basis reduction, branching on hyperplanes, Frobenius number Category 1: Integer Programming Citation: Preprint number 1256, Department of Mathematics, Utrecht University, Utrecht, The Netherlands, 2002. Download: [Postscript]Entry Submitted: 11/03/2002Entry Accepted: 11/03/2002Entry Last Modified: 11/03/2002Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.