Exact Counting and Sampling of Optima for the Knapsack Problem

Bossek Jakob, Neumann Aneta, Neumann Frank


Zusammenfassung
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.

Schlüsselwörter
Zero-one knapsack problem; exact counting; sampling; dynamic programming



Publikationstyp
Forschungsartikel in Sammelband (Konferenz)

Begutachtet
Ja

Publikationsstatus
accepted / in press (not yet published)

Jahr
2021

Konferenz
Learning and Intelligent Optimization

Konferenzort
Athens, Greece

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

Verlag
Springer

Sprache
Englisch