Hard equality constrained integer knapsacks

Karen Aardal, Arjen K Lenstra

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

15 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization: 9th International IPCO Conference
EditorsWilliam J Cook, Andreas S Schulz
Place of PublicationSpringer
Pages350-366
Number of pages17
ISBN (Electronic)978-3-540-47867-6
DOIs
Publication statusPublished - 2002
Externally publishedYes

Publication series

NameLecture Notes in Computer Science
Volume2337

Keywords

  • Integer Vector
  • Short Vector
  • Search Node
  • Positive Integer Number
  • Frobenius Number

Fingerprint Dive into the research topics of 'Hard equality constrained integer knapsacks'. Together they form a unique fingerprint.

Cite this