---
_id: '48855'
abstract:
- lang: eng
  text: 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.
author:
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Aneta
  full_name: Neumann, Aneta
  last_name: Neumann
- first_name: Frank
  full_name: Neumann, Frank
  last_name: Neumann
citation:
  ama: 'Bossek J, Neumann A, Neumann F. Exact Counting and~Sampling of Optima for
    the Knapsack Problem. In: <i>Learning and Intelligent Optimization</i>. Springer-Verlag;
    2021:40–54. doi:<a href="https://doi.org/10.1007/978-3-030-92121-7_4">10.1007/978-3-030-92121-7_4</a>'
  apa: Bossek, J., Neumann, A., &#38; Neumann, F. (2021). Exact Counting and~Sampling
    of Optima for the Knapsack Problem. <i>Learning and Intelligent Optimization</i>,
    40–54. <a href="https://doi.org/10.1007/978-3-030-92121-7_4">https://doi.org/10.1007/978-3-030-92121-7_4</a>
  bibtex: '@inproceedings{Bossek_Neumann_Neumann_2021, place={Berlin, Heidelberg},
    title={Exact Counting and~Sampling of Optima for the Knapsack Problem}, DOI={<a
    href="https://doi.org/10.1007/978-3-030-92121-7_4">10.1007/978-3-030-92121-7_4</a>},
    booktitle={Learning and Intelligent Optimization}, publisher={Springer-Verlag},
    author={Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2021}, pages={40–54}
    }'
  chicago: 'Bossek, Jakob, Aneta Neumann, and Frank Neumann. “Exact Counting And~Sampling
    of Optima for the Knapsack Problem.” In <i>Learning and Intelligent Optimization</i>,
    40–54. Berlin, Heidelberg: Springer-Verlag, 2021. <a href="https://doi.org/10.1007/978-3-030-92121-7_4">https://doi.org/10.1007/978-3-030-92121-7_4</a>.'
  ieee: 'J. Bossek, A. Neumann, and F. Neumann, “Exact Counting and~Sampling of Optima
    for the Knapsack Problem,” in <i>Learning and Intelligent Optimization</i>, 2021,
    pp. 40–54, doi: <a href="https://doi.org/10.1007/978-3-030-92121-7_4">10.1007/978-3-030-92121-7_4</a>.'
  mla: Bossek, Jakob, et al. “Exact Counting And~Sampling of Optima for the Knapsack
    Problem.” <i>Learning and Intelligent Optimization</i>, Springer-Verlag, 2021,
    pp. 40–54, doi:<a href="https://doi.org/10.1007/978-3-030-92121-7_4">10.1007/978-3-030-92121-7_4</a>.
  short: 'J. Bossek, A. Neumann, F. Neumann, in: Learning and Intelligent Optimization,
    Springer-Verlag, Berlin, Heidelberg, 2021, pp. 40–54.'
date_created: 2023-11-14T15:58:54Z
date_updated: 2023-12-13T10:45:14Z
department:
- _id: '819'
doi: 10.1007/978-3-030-92121-7_4
extern: '1'
keyword:
- Dynamic programming
- Exact counting
- Sampling
- Zero-one knapsack problem
language:
- iso: eng
page: 40–54
place: Berlin, Heidelberg
publication: Learning and Intelligent Optimization
publication_identifier:
  isbn:
  - 978-3-030-92120-0
publication_status: published
publisher: Springer-Verlag
status: public
title: Exact Counting and~Sampling of Optima for the Knapsack Problem
type: conference
user_id: '102979'
year: '2021'
...