Exact Counting and Sampling of Optima for the Knapsack Problem

Bossek Jakob, Neumann Aneta, Neumann Frank


Abstract
Computing sets of high quality solutions has gained increasing interest in recent years. In this paper, we investigate how to obtain sets of optimal solutions for the classical knapsack problem. We present an algorithm to count exactly the number of optima to a zero-one knapsack problem instance. In addition, we show how to efficiently sample uniformly at random from the set of all global optima. In our experimental study, we investigate how the number of optima develops for classical random benchmark instances dependent on their generator parameters. We find that the number of global optima can increase exponentially for practically relevant classes of instances with correlated weights and profits which poses a justification for the considered exact counting problem.

Keywords
Zero-one knapsack problem; exact counting; sampling; dynamic programming



Publication type
Forschungsartikel in Sammelband (Konferenz)

Peer reviewed
Yes

Publication status
accepted / in press (not yet published)

Year
2021

Conference
Learning and Intelligent Optimization

Venue
Athens, Greece

Book title
Proceedings of the 15th Learning and Intelligent Optimization (LION) conference

Publisher
Springer

Language
English