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/2002
Entry Accepted: 11/03/2002
Entry Last Modified: 11/03/2002

Modify/Update this entry