Optimization Online


Hard equality constrained integer knapsacks

Karen Aardal (aardal***at***isye.gatech.edu)
Arjen K. Lenstra (arjen.lenstra***at***citigroup.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society