[{"language":[{"iso":"eng"}],"keyword":["Dynamic programming","Exact counting","Sampling","Zero-one knapsack problem"],"publication":"Learning and Intelligent Optimization","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."}],"date_created":"2023-11-14T15:58:54Z","publisher":"Springer-Verlag","title":"Exact Counting and~Sampling of Optima for the Knapsack Problem","year":"2021","department":[{"_id":"819"}],"user_id":"102979","_id":"48855","extern":"1","type":"conference","status":"public","author":[{"orcid":"0000-0002-4121-4668","last_name":"Bossek","id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob"},{"full_name":"Neumann, Aneta","last_name":"Neumann","first_name":"Aneta"},{"first_name":"Frank","full_name":"Neumann, Frank","last_name":"Neumann"}],"date_updated":"2023-12-13T10:45:14Z","doi":"10.1007/978-3-030-92121-7_4","publication_identifier":{"isbn":["978-3-030-92120-0"]},"publication_status":"published","page":"40–54","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>","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>.","short":"J. Bossek, A. Neumann, F. Neumann, in: Learning and Intelligent Optimization, Springer-Verlag, Berlin, Heidelberg, 2021, pp. 40–54.","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>.","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} }","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>"},"place":"Berlin, Heidelberg"}]