### 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 language | English |
---|---|

Title of host publication | Proceedings 9th IPCO (Cambridge MA, USA, May 27-29, 2002) |

Editors | W.J. Cook, A.S. Schulz |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 350-366 |

ISBN (Print) | 3-540-43676-6 |

DOIs | |

Publication status | Published - 2002 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 2337 |

ISSN (Print) | 0302-9743 |

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

## Cite this

Aardal, K. I., & Lenstra, A. K. (2002). Hard equality constrained integer knapsacks. In W. J. Cook, & A. S. Schulz (Eds.),

*Proceedings 9th IPCO (Cambridge MA, USA, May 27-29, 2002)*(pp. 350-366). (Lecture Notes in Computer Science; Vol. 2337). Springer. https://doi.org/10.1007/3-540-47867-1_25